Znajdź najkrótszą ścieżkę na wykresie, która odwiedza określone węzły

84

Mam wykres nieukierunkowany z około 100 węzłami i około 200 krawędziami. Jeden węzeł jest oznaczony jako „początek”, jeden to „koniec”, a kilkanaście jest oznaczonych jako „mustpass”.

Muszę znaleźć najkrótszą ścieżkę na tym wykresie, która zaczyna się na „początku”, kończy na „końcu” i przechodzi przez wszystkie węzły „mustpass” (w dowolnej kolejności).

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt to wykres o którym mowa - przedstawia labirynt kukurydzy w Lancaster w Pensylwanii)

Daniel
źródło

Odpowiedzi:

78

Wszyscy inni porównujący to do Problemu komiwojażera prawdopodobnie nie przeczytali uważnie twojego pytania. W TSP celem jest znalezienie najkrótszego cyklu, który odwiedza wszystkie wierzchołki (cykl Hamiltona) - odpowiada to oznaczeniu każdego węzła jako „mustpass”.

W twoim przypadku, biorąc pod uwagę, że masz tylko kilkanaście oznaczonych jako „mustpass” i biorąc pod uwagę, że 12! jest raczej mały (479001600), możesz po prostu wypróbować wszystkie permutacje tylko węzłów „mustpass” i spojrzeć na najkrótszą ścieżkę od „początku” do „końca”, która odwiedza węzły „mustpass” w tej kolejności - po prostu być konkatenacją najkrótszych ścieżek między każdymi dwoma kolejnymi węzłami na tej liście.

Innymi słowy, najpierw znajdź najkrótszą odległość między każdą parą wierzchołków (możesz użyć algorytmu Dijkstry lub innego, ale przy tych małych liczbach (100 węzłów) nawet najprostszy do zakodowania algorytm Floyda-Warshalla zadziała w czasie). Następnie, gdy już masz to w tabeli, wypróbuj wszystkie permutacje węzłów „mustpass” i resztę.

Coś takiego:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

(Oczywiście to nie jest prawdziwy kod, a jeśli chcesz rzeczywistą ścieżkę, musisz śledzić, która permutacja daje najkrótszą odległość, a także jakie są najkrótsze ścieżki wszystkich par, ale masz pomysł).

Będzie działać najwyżej przez kilka sekund w dowolnym rozsądnym języku :)
[Jeśli masz n węzłów i k węzłów 'mustpass', jego czas wykonania wynosi O (n 3 ) dla części Floyd-Warshall i O (k! N ) dla wszystkich permutacji, a 100 ^ 3 + (12!) (100) to praktycznie orzeszki ziemne, chyba że masz naprawdę restrykcyjne ograniczenia.]

ShreevatsaR
źródło
6
Biorąc pod uwagę mały rozmiar danych wejściowych, zgadzam się z odpowiedzią. Ale interesuje mnie, dlaczego odrzucasz twierdzenia innych, że jest to przypadek TSP. Tak jak ja to rozumiem, możesz wyodrębnić wszystkie węzły, które muszą przejść, i użyć ich do utworzenia pod-grafu. Krawędzie między węzłami na pod-grafie mają wagi odpowiadające rozwiązaniu APSP na oryginalnym wykresie. Czy zatem pytanie nie staje się instancją TSP na podgrafie? Twoje rozwiązanie wydaje się być brutalnym rozwiązaniem tego problemu (co jest w porządku).
maditya
7
@maditya: Po pierwsze, mam nadzieję, że zgodzisz się, że (cytując komentarz Stevena A Lowe'a na temat innej odpowiedzi) odpowiedź typu „TSP jest trudna, bwahahaha” nie jest odpowiednią odpowiedzią dla kogoś, kto ma prawdziwy problem do rozwiązania, zwłaszcza taki bardzo łatwy rozwiązany na dowolnym komputerze z ostatnich kilku dekad. Po drugie, nie jest to identyczne z TSP z błahych powodów (inny format wejściowy): maleńka instancja TSP, którą zawiera, dotyczy mniejszego wykresu, a nie rozmiaru wejściowego N. Zatem kompletność NP zależy od tego, ile węzłów „musi przejść”. są asymptotycznie: jeśli zawsze jest 12, lub O (log N), to nie jest NP-zupełne itp.
ShreevatsaR
1
Nie jestem pewien, czy wynikiem będzie ścieżka. Wyobraź sobie, że musisz przejść od ado ckońca b. Może się zdarzyć, że najkrótsze ścieżki od bdo ai będą cmiały wspólną krawędź. W takim przypadku krawędź zostanie powtórzona dwukrotnie. Jedna z dwóch ścieżek musiałaby być gorsza niż optymalna, aby nie generować cykli.
Mów
1
@PietroSaccardi Z opisu w pytaniu wynika, że ​​celem jest po prostu znalezienie najkrótszej „drogi” przejścia przez wszystkie te węzły i może być ok, jeśli jakaś krawędź się powtórzy. Oznacza to, że „ścieżka” jest używana w luźnym znaczeniu. W rzeczywistości, jeśli powtarzające się krawędzie są niedozwolone, może nawet nie być odpowiedzi (np. Rozważ wykres B - A - C, na którym jesteś proszony o przejście od A do C podczas przechodzenia przez B: nie ma sposobu, aby nie powtórzyć B — Krawędź).
ShreevatsaR
Algorytm Floyda-Warshalla nie jest tutaj poprawnie zaimplementowany: ponieważ wszystkie komórki tablicy są inicjalizowane INF, linia d[i][j] = min(d[i][j], d[i][k] + d[k][j])staje się d[i][j] = min(INF, INF + INF)i wszystkie komórki zawsze pozostają równe INF. Musisz dodać krok, aby wypełnić tę tablicę długościami krawędzi z wykresu.
Stef
25

uruchom algorytm Djikstry, aby znaleźć najkrótsze ścieżki między wszystkimi krytycznymi węzłami (początkowy, końcowy i obowiązkowy), a następnie przemierzanie w głąb powinno wskazać najkrótszą ścieżkę przez wynikowy wykres podrzędny, który dotyka wszystkich początkowych węzłów. , wędrówki ... koniec

Steven A. Lowe
źródło
Wydaje się, że może być bardziej wydajne niż wybrane rozwiązanie. Założę się, że gdybyś dopracował go nieco bardziej, uzyskałby wyższy wynik. Najpierw musiałem pomyśleć o tym, czy najkrótsza ścieżka między wszystkimi parami gwarantuje ścieżkę między wszystkimi wymaganymi węzłami .. ale wierzę, że tak (zakładając, że nie jest ukierunkowana).
galactikuh
Myślę, że to nie zadziała, jeśli ścieżka nie może powtarzać krawędzi.
tuket
1
W jaki sposób przemierzanie w głąb znajdowałoby się na najkrótszej ścieżce na przykładzie 24 dnia Adwentu Kodeksu? adventofcode.com/2016/day/24
Erwin Rooijakkers
16

To są dwa problemy ... Steven Lowe zwrócił na to uwagę, ale nie okazał wystarczającego szacunku drugiej połowie problemu.

Najpierw należy odkryć najkrótsze ścieżki między wszystkimi węzłami krytycznymi (początek, koniec, przejście). Po odkryciu tych ścieżek można utworzyć uproszczony wykres, w którym każda krawędź nowego wykresu jest ścieżką od jednego krytycznego węzła do drugiego na oryginalnym wykresie. Istnieje wiele algorytmów znajdowania ścieżki, których można użyć do znalezienia tutaj najkrótszej ścieżki.

Kiedy już masz ten nowy wykres, masz dokładnie problem z podróżującym sprzedawcą (no prawie… Nie ma potrzeby wracać do punktu wyjścia). Wszystkie posty dotyczące tego, o których mowa powyżej, będą miały zastosowanie.

Andrew Top
źródło
14

Właściwie problem, który opublikowałeś, jest podobny do problemu z komiwojażerem, ale myślę, że bliżej mu do prostego problemu ze znajdowaniem ścieżki. Zamiast odwiedzać każdy węzeł, wystarczy odwiedzić określony zestaw węzłów w jak najkrótszym czasie (odległości).

Powodem tego jest to, że w przeciwieństwie do problemu komiwojażera, labirynt kukurydzy nie pozwoli ci podróżować bezpośrednio z jednego punktu do innego punktu na mapie bez konieczności przechodzenia przez inne węzły, aby się tam dostać.

Właściwie poleciłbym A * pathfinding jako technikę do rozważenia. Ustawiasz to, decydując, które węzły mają bezpośredni dostęp do jakich innych węzłów i jaki jest „koszt” każdego przeskoku z określonego węzła. W tym przypadku wygląda na to, że każdy „przeskok” może mieć taki sam koszt, ponieważ węzły wydają się stosunkowo blisko siebie. A * może wykorzystać te informacje, aby znaleźć ścieżkę o najniższych kosztach między dowolnymi dwoma punktami. Ponieważ musisz dostać się z punktu A do punktu B i odwiedzić około 12 w międzyczasie, nawet podejście brutalnej siły z wykorzystaniem pathfindingu w ogóle nie zaszkodzi.

Tylko alternatywa do rozważenia. Wygląda to zadziwiająco jak problem komiwojażera i są to dobre dokumenty do przeczytania, ale przyjrzyj się bliżej, a zobaczysz, że to tylko nadmierna komplikacja. ^ _ ^ To pochodzi z umysłu programisty gier wideo, który zajmował się już wcześniej tego typu rzeczami.

Nicholas Flynt
źródło
2
+1 - to znacznie lepsza odpowiedź niż „problem podróżującego salemana jest trudny, bwahahaha”
Steven A. Lowe
5

Andrew Top ma dobry pomysł:

1) Algorytm Djikstry 2) Niektóre heurystyki TSP.

Polecam heurystykę Lin-Kernighana: jest to jedna z najbardziej znanych dla każdego problemu NP Complete. Jedyną inną rzeczą do zapamiętania jest to, że po ponownym rozwinięciu wykresu po kroku 2, możesz mieć pętle na swojej rozwiniętej ścieżce, więc powinieneś obejść je, skracając je (spójrz na stopień wierzchołków na twojej ścieżce).

Właściwie nie jestem pewien, jak dobre będzie to rozwiązanie w stosunku do optimum. Prawdopodobnie istnieją pewne patologiczne przypadki zwarcia. W końcu ten problem wygląda DUŻO jak Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree i zdecydowanie nie możesz przybliżyć Steiner Tree, po prostu zwężając swój wykres i uruchamiając na przykład Kruskal.

Ying Xiao
źródło
5

To nie problem TSP i nie NP-trudne, ponieważ oryginalne pytanie nie wymaga, że węzły są odwiedził tylko raz must-pass. To sprawia, że ​​odpowiedź jest dużo, dużo prostsza do po prostu brutalnej siły po skompilowaniu listy najkrótszych ścieżek między wszystkimi węzłami, które muszą przejść przez algorytm Dijkstry. Może istnieć lepszy sposób, ale prostym byłoby po prostu odwrócenie drzewa binarnego. Wyobraź sobie listę węzłów [początek, a, b, c, koniec]. Zsumuj proste odległości [start-> a-> b-> c-> end] to jest twój nowy docelowy dystans do pokonania. Teraz spróbuj [start-> a-> c-> b-> end] i jeśli to lepiej, ustaw to jako cel (i pamiętaj, że pochodzi z tego wzorca węzłów). Pracuj wstecz nad permutacjami:

  • [start-> a-> b-> c-> end]
  • [start-> a-> c-> b-> end]
  • [start-> b-> a-> c-> end]
  • [start-> b-> c-> a-> end]
  • [start-> c-> a-> b-> end]
  • [start-> c-> b-> a-> end]

Jeden z nich będzie najkrótszy.

(gdzie są węzły „odwiedzane wielokrotnie”, jeśli w ogóle? Są one po prostu ukryte w kroku inicjalizacji najkrótszej ścieżki. Najkrótsza ścieżka między a i b może zawierać c lub nawet punkt końcowy. Nie musisz się tym przejmować )

bjorke
źródło
Wizyta tylko raz jest wymagana ze względu na to, że jest to najkrótsza ścieżka.
Aziuth
Huh. Jeszcze minutę temu byłem całkiem pewien, ale tak, masz rację. Oczywiście nie na drzewie z kilkoma gałęziami. Ale rzecz w tym, że jeśli wyabstrahujemy problem do nowego wykresu, który zawiera tylko węzły, które muszą przejść, które są w pełni połączone, a węzły mają odległość najkrótszej ścieżki na oryginalnym wykresie, dochodzimy do TSP. Czy na pewno więc nie jest to NP-trudne? Zakładam, że w ogólnym problemie ilość węzłów mustpass zależy od ilości wszystkich węzłów, a jeśli na przykład suma jest wielomianem mustpass, otrzymujemy NP-hardness, prawda?
Aziuth
Trasa z, powiedzmy, a-> b może przebiegać przez c. Więc żadne ostrze nie zapobiega żadnemu innemu. To tylko permutacja.
bjorke
Tak? Ale permutacja to O (n!), Jeśli założymy, że liczba węzłów, które muszą przejść, ma jakiś związek z liczbą wszystkich węzłów, na przykład „wszystkie węzły są wielomianem węzłów, które muszą przejść”. Właśnie rozwiązałeś TSP brutalną siłą.
Aziuth
2

Biorąc pod uwagę, że liczba węzłów i krawędzi jest stosunkowo ograniczona, prawdopodobnie możesz obliczyć każdą możliwą ścieżkę i wybrać najkrótszą.

Zwykle jest to znane jako problem komiwojażera i ma niedeterministyczny wielomianowy czas wykonywania, niezależnie od używanego algorytmu.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Rafe
źródło
1

Pytanie mówi o obowiązkowym przejściu w DOWOLNEJ kolejności . Próbowałem znaleźć rozwiązanie dotyczące zdefiniowanej kolejności węzłów, które muszą przejść. Znalazłem swoją odpowiedź, ale ponieważ żadne pytanie na StackOverflow nie miało podobnego pytania, publikuję tutaj, aby umożliwić maksymalnym ludziom skorzystanie z tego.

Jeśli zamówienie lub obowiązkowe przejście jest zdefiniowane, możesz wielokrotnie uruchamiać algorytm dijkstry. Na przykład załóżmy, że trzeba zacząć od sprzejściu przez k1, k2i k3(w odpowiedniej kolejności) i stop e. Następnie możesz uruchomić algorytm Dijkstry między każdą kolejną parą węzłów. Koszt i ścieżka będzie dana przez:

dijkstras(s, k1) + dijkstras(k1, k2) + dijkstras(k2, k3) + dijkstras(k3, 3)

Syed Hissaan
źródło
0

Co powiesz na użycie brutalnej siły na kilkunastu węzłach, które muszą odwiedzić. Możesz łatwo pokryć wszystkie możliwe kombinacje 12 węzłów, a to daje Ci optymalny obwód, który możesz śledzić, aby je pokryć.

Teraz twój problem jest uproszczony do jednego polegającego na znalezieniu optymalnych tras od węzła początkowego do toru, którymi następnie podążasz, aż je pokonasz, a następnie znajdź trasę od tego do końca.

Ostateczna ścieżka składa się z:

start -> ścieżka do obwodu * -> obwód musi odwiedzić węzły -> ścieżka do końca * -> koniec

Znajdziesz ścieżki, które oznaczyłem * w ten sposób

Wykonaj wyszukiwanie A * od węzła początkowego do każdego punktu na obwodzie dla każdego z nich wykonaj wyszukiwanie A * od następnego i poprzedniego węzła obwodu do końca (ponieważ możesz podążać po obwodzie w dowolnym kierunku). kończy się na wielu ścieżkach wyszukiwania i możesz wybrać tę o najniższych kosztach.

Jest dużo miejsca na optymalizację poprzez buforowanie wyszukiwań, ale myślę, że wygeneruje to dobre rozwiązania.

Nie zbliża się to jednak do poszukiwania optymalnego rozwiązania, ponieważ może to oznaczać pozostawienie obwodu, który trzeba odwiedzić w ramach wyszukiwania.

justinhj
źródło
0

Jedna rzecz, o której nigdzie nie jest mowa, to czy jest w porządku, aby ten sam wierzchołek był odwiedzany więcej niż raz na ścieżce. Większość odpowiedzi tutaj założyć, że jest ok do odwiedzenia tej samej krawędzi wiele razy, ale moje zdanie podane na pytanie (a ścieżka nie powinni odwiedzić ten sam wierzchołek więcej niż jeden raz!) Jest to, że to nie w porządku, aby odwiedzić ten sam wierzchołek dwukrotnie.

Tak więc podejście brutalnej siły nadal będzie miało zastosowanie, ale będziesz musiał usunąć wierzchołki już używane, gdy będziesz próbować obliczyć każdy podzbiór ścieżki.

wiśniówka
źródło