如何訂購/排序依賴性的2D表

Question

我很好奇，如果有一些更高級別的理論/方法/算法來解決我的問題。

我正在處理網絡路由問題（專有無線電網絡）。舉例來說，我有5個設備的網絡。對於每個設備，我都可以測量它聽到其他設備的能力。第0個根節點僅作爲源而感興趣。因此，以表格的形式，這樣我可能會喜歡的東西：

_0_ _1_ _2_ _3_ _4_ 
1 | 21 - 42 55 0 
2 | 0 63 - 18 20 
3 | 20 0 0 - 0 
4 | 0 0 13 0 - 

每行表示該設備能有多好聽到其他5種源。我想要做的是對它們進行排序，以便每個設備從前面的元素中獲得最好的總和信號。所以對於這個簡單的例子，排序可能是1, 3, 2, 4。但它也可能是3, 1, 2, 4。事實上，這一秒會更好，因爲1可以同時聽到0和3. 3, 2, 1, 4也可以。

我想確定我可以使用什麼樣的算法來訂購這些。有一些旅遊推銷員，我不需要「最好」的排序。只是一個很好的排序。我需要擴展到10個來源的9個設備。

任何想法，幫助，輕推，提示，提示讚賞。

Answer 1

此問題可模擬爲minimum feedback arc set problem，這是一個NP難題。原始圖是一個完整的有向圖，每個邊的權重(v0, v1)是從v0到v1的信號強度。在計算最大反饋弧集之後，進行拓撲排序將給出具有最大總信號的排序。