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

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)

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 ³ ) 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.]

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

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.

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.

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.

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ć )

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

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)

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.

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.