5
Zainspirowany tym komiksie http://xkcd.com/173/Algorytm znajdowania "minimalnej ścieżki oparcia"?
wiem, że istnieje wiele algorytmów do znalezienia minimalnego drzewa rozpinającego o ważonej wykresu, jednak ja już stara się znaleźć żadnego, które można znaleźć minimalne Spanning „path”.
Dla komiksu, jeśli ważymy każdą krawędź w oparciu o relacje z każdą parą, wówczas optymalnym społecznie układem będzie minimalna rozpinająca się "ścieżka", tj. Ścieżka obejmująca wszystkie wierzchołki. Czy ktoś może pomóc?
Czy różni się to od znalezienia minimalnej [ścieżki Hamiltona] (http://en.wikipedia.org/wiki/Hamiltonian_path)? –
Właściwa obserwacja oczywiście. Inny ciekawy przypadek, w którym pokrewne problemy różnią się złożonością: MST = easy, MSP/HP = hard. –
Jeśli możesz przyjąć pewne założenia dotyczące ograniczeń społecznych, możesz rozwiązać ten problem za pomocą zmodyfikowanego algorytmu Huffmana. –