最小化陣列中相關項目之間的距離

C是依賴於A. d依賴於B和C

所以，我計算在這個置換爲之間的距離之和項之間的總距離： C和A（2）， D和B（2）， D和C（1）。所以，我們總共有5個這個排列組合。

然而，最優化的解決方案將是{A，C，d，B}，其具有3

的總距離我具有約200項的（複雜得多）列表，我希望儘可能地進行優化，而且我不知道任何以這種方式排序的排序算法 - 任何人都可以指向現有算法的方向嗎？

從評論：數據的曲線看起來像如下─（道歉格式化！）

#Dependencies #Items 
      0  9 
      1  27 
      2  57 
      3  55 
      4  11 
      5  3 
      6  1

目前還不清楚你與什麼比較。 –

距離排序的值最近的是比較距離上游和下游依存關係的距離，交換項目，然後查看這兩個項目是否具有比以前更大的總距離。即便如此，它並不是特別有效！ –

這個解釋並沒有幫助我理解你到底想要做什麼 –

我相信你在找什麼是拓撲排序。

該算法用於有向圖。這裏的字母表形成圖的節點，並且依賴關係形成單向邊。該算法是深度優先搜索的應用程序，用於排序作業。

This是一個非常簡潔的解釋。

2016-04-25 19:26:55 chatuur

所提供的例子有一個最佳的解決方案，在依賴性「C」之後和依賴性「B」之前放置'D'。這不是一種拓撲排序！即使他對拓撲類型感興趣，他仍然希望爲距離函數提供最小值的那個。 – btilly

回答