基于算法的基于允许的对象对对象进行排序/重新排序

我需要开发一种算法，它将采用一组无序对象并基于它们允许进行的对象对它们进行智能重新排序。基于算法的基于允许的对象对对象进行排序/重新排序

我最初的设计/思想是使用Core Data将一对多关系（“canGoTo”）的实体（例如“对象”）存储在自身上，并带有一组可以跟随所选对象的对象*目的。

请考虑以下示例，其中每个对象都有一组对象，可以在该对象中继续进行操作（实际的对象集合要大得多）。

Object A - can go to -> Objects B,C,D 
Object B - can go to -> Objects E,F,G,Y,H 
Object C - can go to -> Objects P,S,Z 
Object D - can go to -> Objects H,J,X 
... 
Object G - can go to -> Objects R,Y,Z 
Object H - can go to -> Objects G,Z 
... 
Object Y - can go to -> Objects Z 
Object Z - can go to -> Objects NULL (no objects follow this object)

如果程序给定一组对象（R，B，H，G，A，Z）的程序需要找到如何重新排列对象以找到可接受结构。因此，这一组的正确结果将是A-> B-> H-> G-> Y-> Z

什么策略是最好的，或最有效率的通过这个问题？我是否应该通过重新订购循环，并在我成功触摸通行证中的所有对象时退出？使用遗传算法产生输出并分析世代（即http://ijoshsmith.com/2012/04/08/simple-genetic-algorithm-in-objective-c/）？或者，我是否使用Insertion Sort来分析所有对象并将对象重新排列到它可以放入序列中的位置？请记住，实际的对象列表将更像30+对象而不是6对象，并且在完美的世界中，程序将选择列表排序的最佳方式（可能基于“canGoTo”优先级）。

任何意见/最佳实践将不胜感激。对不起，没有示例代码，目前处于思考阶段。

来源

2012-11-06 Andrew Robinson

这看起来像你想要[拓扑排序]（http://en.wikipedia.org/wiki/Topological_sorting）。 – Blastfurnace

从我第一眼看到那个链接时，我不得不同意。从来没有听说过拓扑排序，直到现在，谢谢你的头！ –

您可以将您的问题建模为Directed Acyclic Graph，然后对其执行Topological Sorting。这将给出你正在寻找的确切输出。

来源

2012-11-06 14:09:15 alestanis

感谢您的回答！我喜欢拓扑排序的想法。我会进一步调查这个模型，但绝对是一个正确的答案。 –

因此，为了跟进我所做的一些研究，似乎拓扑排序选择了所有对象，并将它们按照有意义的顺序排列（基于设计并始终遵循节点向前）。由于该程序需要评估一系列说100个对象并按顺序提取其中的25-35个（基于规定哪些对象可以跟随给定对象的规则），对于我来说，编程25-35首先对象并担心后来排序？ –

你确定会有通过所有这些对象的路径吗？在这种情况下，您可以尝试构建仅包含与您有关的25-35个对象的DAG，对其进行分类，然后提取给定的路径。在你的例子中，对象B可以进入对象E，F，G，Y，H，但是你只需要对象'（R，B，H，G，A，Z）'，这样你就可以创建一个图与信息'对象B - 可以去 - >对象G，H' – alestanis

基于算法的基于允许的对象对对象进行排序/重新排序

回答

相关问题