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

Uruchom algorytm Djikstry aby znaleźć najkrótsze ścieżki pomiędzy wszystkimi węzłami krytycznymi (start, end I must-pass), następnie przejście na głębokość powinno wskazywać najkrótszą ścieżkę przez wynikowy podgraf, który dotyka wszystkich węzłów start ... mustpasses ... end

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

Powinieneś najpierw odkryć najkrótsze ścieżki pomiędzy wszystkimi krytycznymi węzłami(start, end, mustpass). Po odkryciu tych ścieżek można skonstruować uproszczony wykres, w którym każda krawędź nowego wykresu jest ścieżką od jednego krytycznego węzła do drugiego w oryginalnym wykresie. Istnieje wiele algorytmów wyszukiwania ścieżek, których można użyć do znalezienia najkrótszej ścieżki proszę.

Gdy już masz ten nowy wykres, masz dokładnie problem z podróżującym sprzedawcą (no, prawie... Nie trzeba wracać do punktu wyjścia). Każdy z wyżej wymienionych postów będzie miał zastosowanie.

Właściwie, problem, który napisałeś jest podobny do komiwojażera, ale myślę, że bliżej do prostego problemu wyszukiwania ścieżek. Zamiast odwiedzać każdy węzeł, musisz po prostu odwiedzić określony zestaw węzłów w jak najkrótszym czasie (odległość).

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 idź tam.

Faktycznie polecam * pathfinding jako technikę do rozważenia. Konfigurujesz to, decydując, które węzły mają dostęp do których innych węzłów bezpośrednio i jaki jest" koszt " każdego skoku z danego węzła. W tym przypadku wygląda na to, że każdy "hop" może być równy koszt, ponieważ twoje węzły wydają się stosunkowo blisko siebie. A * może użyć tych informacji, aby znaleźć najniższą ścieżkę kosztów między dowolnymi dwoma punktami. Ponieważ trzeba dostać się z punktu A do punktu B i odwiedzić około 12 nawet brutalne podejście przy użyciu pathfindingu nie zaszkodzi.

Tylko alternatywa do rozważenia. To wygląda niezwykle jak problem podróżnego sprzedawcy, a to są dobre papiery do przeczytania, ale przyjrzyj się bliżej, a zobaczysz, że to tylko zbyt skomplikowane rzeczy. ^ _ ^ To pochodzi z umysłu programisty gier wideo, który zajmował się tego typu sprawami wcześniej.

Andrzej Top ma dobry pomysł:

1) algorytm Djikstry 2) Niektóre heurystyczne TSP.

Polecam heurystykę Lin-Kernighan: jest to jeden z najbardziej znanych problemów z np Complete. Jedyną rzeczą do zapamiętania jest to, że po rozwinięciu wykresu ponownie po kroku 2, możesz mieć pętle w rozszerzonej ścieżce, więc powinieneś je obejść (spójrz na stopień wierzchołków wzdłuż ścieżki).

Nie jestem pewien, jak dobre będzie to rozwiązanie być w stosunku do optimum. Prawdopodobnie są pewne patologiczne przypadki związane ze zwarciem. W końcu ten problem wygląda jak Steiner Tree: http://en.wikipedia.org/wiki/Steiner_tree i na pewno nie możesz przybliżyć drzewa Steinera, po prostu zamawiając swój wykres i uruchamiając na przykład Kruskala.

To jest nie problem TSP i nie np-hard, ponieważ pierwotne pytanie nie wymaga, aby węzły must-pass były odwiedzane tylko raz. To sprawia, że odpowiedź jest znacznie, znacznie prostsza do po prostu brute-force po skompilowaniu listy najkrótszych ścieżek między wszystkimi węzłami must-pass za pomocą algorytmu Dijkstry. Może jest lepszy sposób, ale prostym byłoby po prostu pracować z binarnym drzewem wstecz. Wyobraź sobie listę węzłów [start ,a, b, c, end]. Sum proste odległości [start->a->b->c->end] to to twoja nowa odległość 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). Praca 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ą ' odwiedzane wielokrotności węzły times ' a, jeśli jakieś? Są ukryte w najkrótszym kroku inicjalizacji. Najkrótsza ścieżka między a i b może zawierać c lub nawet punkt końcowy. You don ' t need to care)

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

Ogólnie rzecz biorąc, jest to znany jako problem podróżnego sprzedawcy i ma niedeterministyczny wielomian, bez względu na algorytm, którego używasz.

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

Pytanie mówi o must-pass W dowolnej kolejności . Próbowałem szukać rozwiązania o zdefiniowanej kolejności węzłów must-pass. Znalazłem swoją odpowiedź, ale ponieważ żadne pytanie na StackOverflow nie miało podobnego pytania, zamieszczam tutaj, aby maksymalnie ludzie z niego skorzystali.

Jeśli order lub must-pass jest zdefiniowane , możesz uruchomić algorytm Dijkstry wiele razy. Załóżmy na przykład, że musisz zacząć od s przejść przez k1, k2 oraz k3 (w odpowiedniej kolejności) i zatrzymać się na e. Następnie możesz uruchomić algorytm Dijkstry między każdą kolejną parą węzłów. koszt i ścieżka będą podane przez:

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

Jak o użyciu brute force na tuzin' must visit ' węzłów. Możesz łatwo pokryć wszystkie możliwe kombinacje 12 węzłów, a to pozostawia Ci optymalny obwód, który możesz śledzić, aby je pokryć.

Teraz twój problem jest uproszczony do jednego z znalezienia optymalnych tras od węzła startowego do obwodu, które następnie podążasz, aż je przejedziesz, a następnie znajdź trasę od tego do końca.

Ścieżka końcowa składa się z:

Start - > ścieżka do circuit* - > circuit of must visit nodes -> path to end* - > end

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

Wykonaj wyszukiwanie A* od węzła startowego do każdego punktu na obwodzie dla każdego z nich wykonaj wyszukiwanie A* od następnego i poprzedniego węzła na obwodzie do końca (ponieważ możesz podążać za obwodem w dowolnym kierunku) W końcu masz wiele ścieżek wyszukiwania i możesz wybrać tę o najniższym koszcie.

Jest dużo miejsca na optymalizację buforując wyszukiwania, ale myślę, że to wygeneruje dobre rozwiązania.

Nie chodzi jednak o szukanie optymalnego rozwiązania, ponieważ może to wiązać się z pozostawieniem obwodu must visit w ramach wyszukiwania.

Jedną z rzeczy, o której nigdzie nie wspomniano, jest to, czy jest ok, aby ten sam wierzchołek był odwiedzany więcej niż raz na ścieżce. Większość odpowiedzi tutaj zakłada, że jest ok, aby odwiedzić tę samą krawędź wiele razy, ale moje zdanie biorąc pod uwagę pytanie (ścieżka nie powinna odwiedzić ten sam wierzchołek więcej niż raz!) jest to, że to jest nie w porządku, aby odwiedzić ten sam wierzchołek dwa razy.

Więc podejście brute force nadal będzie stosowane, ale musisz usunąć wierzchołki już używane, gdy próbujesz Oblicz każdy podzbiór ścieżki.