2B bağımlılıklar tablosu nasıl sipariş edilir/sıralanır

Question

Sahip olduğum bu sorunu çözmek için bazı üst düzey teori/yaklaşım/algoritma olup olmadığını merak ediyorum.

Bir ağ yönlendirmesi sorunu üzerinde çalışıyorum (özel bir radyo ağı). Örnek olarak, 5 cihaz ağım var. Her cihaz için, diğer cihazları ne kadar iyi duyabildiğini ölçebilirim. Orijin kökü, sadece bir kaynak olarak ilginçtir. Her satır söz konusu cihaz, diğer 5 kaynaklardan duymak ne kadar iyi gösterir

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

: Yani tablo şeklinde, ben böyle bir şey ile bitirmek olabilir. Yapmak istediklerim, her aygıtın önceki öğelerin en iyi toplam sinyallerini alması için onları sıralamaktır. Yani bu basit durum için, sipariş 1, 3, 2, 4 olabilir. Ancak 3, 1, 2, 4 da olabilir. Aslında, bu saniye daha iyi olurdu çünkü 1 hem 0 hem de 3'ü duyabilir. 3, 2, 1, 4 da işe yarayacaktır.

Bunları sipariş etmek için kullanabileceğim bir algoritmayı belirlemeye çalışıyorum. Ona biraz seyahat eden satıcı var ve "en iyi" sıralamalara ihtiyacım yok. Sadece oldukça iyi bir sıralama. 10 kaynak ile 9 cihaza kadar ölçeklemem gerekiyor.

Düşünceler, yardımlar, dürtüler, ipuçları, ipuçları takdir edilir.

Answer 1

Bu sorun, NP-zor bir sorun olan minimum feedback arc set problem olarak modellenebilir. Orijinal grafik, (v0, v1)'un her kenarının ağırlığı ile v0 ila v1 arasındaki sinyal gücünün tam bir yönlendirilmiş grafiğidir. Maksimum geribesleme ark kümesi hesaplandıktan sonra, topolojik bir sıralama maksimum toplam sinyale sahip bir sipariş verecektir.