Come ordinare/ordinare una tabella 2D di dipendenze

Question

Sono curioso di sapere se esiste qualche teoria/approccio/algoritmo di livello superiore per risolvere questo problema che ho.

Sto lavorando a un problema di routing di rete (una rete radio proprietaria). A titolo di esempio, ho una rete di 5 dispositivi. Per ogni dispositivo, posso misurare quanto può sentire gli altri dispositivi. Il nodo radice 0 è interessante solo come fonte. Quindi, in forma di tabella, potrei finire con qualcosa di simile:

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

Ogni riga indica quanto bene che il dispositivo può sentire le altre 5 fonti. Quello che voglio fare è ordinarli in modo che ogni dispositivo ottenga i migliori segnali di somma dagli elementi precedenti. Quindi, per questo semplice caso, l'ordine potrebbe essere 1, 3, 2, 4. Ma potrebbe anche essere 3, 1, 2, 4. In effetti, questo secondo sarebbe meglio perché 1 può sentire sia 0 che 3. 3, 2, 1, 4 funzionerebbe pure.

Sto provando a determinare che tipo di algoritmo posso utilizzare per ordinarli. C'è un po 'di venditori ambulanti ad esso, e non ho bisogno di un tipo "migliore". Solo un tipo probabilmente abbastanza buono. Ho bisogno di scalare fino a 9 dispositivi con 10 fonti.

Ogni pensiero, aiuto, spintoni, suggerimenti, suggerimenti apprezzati.

Answer 1

Questo problema può essere modellato come minimum feedback arc set problem, che è un problema NP-difficile. Il grafico originale è un grafico diretto completo, con il peso di ogni spigolo (v0, v1) corrispondente alla potenza del segnale da v0 a v1. Dopo aver calcolato il massimo arco di retroazione, fare un ordinamento topologico darà un ordine che ha il segnale totale massimo.