基於算法的基於允許的對象對對象進行排序/重新排序

我需要開發一種算法，它將採用一組無序對象並基於它們允許進行的對象對它們進行智能重新排序。基於算法的基於允許的對象對對象進行排序/重新排序

我最初的設計/思想是使用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

基於算法的基於允許的對象對對象進行排序/重新排序

回答

相關問題