Wie man eine 2D Tabelle der Abhängigkeiten bestellt/sortiert

Question

Ich bin neugierig, wenn es irgendeine höhere Theorie/Annäherung/Algorithmus gibt, um dieses Problem zu lösen, das ich habe.

Ich arbeite an einem Netzwerk-Routing-Problem (ein proprietäres Funknetz). Ich habe zum Beispiel ein Netzwerk von 5 Geräten. Für jedes Gerät kann ich messen, wie gut es andere Geräte hören kann. Der 0. Wurzelknoten ist nur als Quelle interessant. So in Tabellenform, könnte ich am Ende mit etwas wie:

_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 - 

Jede Zeile zeigt an, wie gut das Gerät die anderen fünf Quellen hören. Ich möchte sie so sortieren, dass jedes Gerät die besten Summensignale von vorhergehenden Elementen erhält. Für diesen einfachen Fall könnte die Bestellung 1, 3, 2, 4 sein. Es könnte aber auch 3, 1, 2, 4 sein. Tatsächlich wäre diese Sekunde besser, weil 1 sowohl 0 als auch 3 hören kann. 3, 2, 1, 4 würde auch funktionieren.

Ich versuche zu bestimmen, welche Art von Algorithmus ich verwenden kann, um diese zu bestellen. Es gibt ein paar fahrende Verkäufer, und ich brauche keine "beste" Sorte. Nur eine wahrscheinlich ziemlich gute Sorte. Ich muss bis zu 9 Geräte mit 10 Quellen skalieren.

Alle Gedanken, Hilfe, Nudges, Tipps, Hinweise geschätzt.

Answer 1

Dieses Problem kann als minimum feedback arc set problem modelliert werden, was ein NP-schweres Problem ist. Der ursprüngliche Graph ist ein vollständiger gerichteter Graph, wobei das Gewicht jeder Kante (v0, v1) die Signalstärke von v0 bis v1 ist. Nach dem Berechnen der maximalen Rückkopplungsbogenmenge ergibt eine topologische Sortierung eine Ordnung, die das maximale Gesamtsignal aufweist.