Algorytm Dijsktry zastosowany do problemu sprzedawcy podróżującego

Jestem nowicjuszem (całkowicie początkującym w teorii złożoności obliczeniowej) i mam pytanie.

Powiedzmy, że mamy „problem sprzedawcy podróży”, czy poniższe zastosowanie algorytmów Dijkstry rozwiąże ten problem?

Od punktu początkowego obliczamy najkrótszą odległość między dwoma punktami. Idziemy do rzeczy. Usuwamy punkt źródłowy. Następnie obliczamy następny najkrótszy punkt odległości od bieżącego punktu i tak dalej ...

Z każdym krokiem zmniejszamy wykres, a my przesuwamy następny dostępny najkrótszy punkt odległości. Dopóki nie odwiedzimy wszystkich punktów.

Czy to rozwiąże problem podróżnego sprzedawcy?

Algorytm Dijkstry zwraca drzewo najkrótszej ścieżki, zawierające najkrótszą ścieżkę od początkowego wierzchołka do siebie, ale niekoniecznie najkrótsze ścieżki między pozostałymi wierzchołkami lub najkrótszą trasę, która odwiedza wszystkie wierzchołki.

Oto przeciwny przykład, w którym opisany przez ciebie chciwy algorytm nie zadziała:

Zaczynając od , chciwy algorytm wybierze trasę , ale najkrótsza trasa rozpoczynająca się i kończąca na to . Ponieważ trasa TSP nie może powtarzać wierzchołków, gdy tylko chciwy algorytm wybierze , zmuszony jest wziąć najdłuższą krawędź aby powrócić do miasta początkowego.[ a , b , c , d , a ] a [ a , b , d , c , a ] a , b , c , d d , $a$$[a,b,c,d,a]$$a$$[a,b,d,c,a]$$a,b,c,d$$d,a$

Jak już okazało się w innych odpowiedziach, twoja sugestia nie rozwiązuje skutecznie problemu podróżującego sprzedawcy, pozwól mi wskazać najlepszy znany sposób w dziedzinie wyszukiwania heurystycznego (ponieważ widzę algorytm Dijkstry nieco związany z tym obszarem sztucznej inteligencji) .

Algorytm heurystyczny może zwrócić optymalne rozwiązania (chociaż rozmiary, którymi może zarządzać, są w rzeczywistości stosunkowo niewielkie), a następującą metodę zasugerował Richard Korf w latach 90. Wprawdzie działa idealnie w przypadku problemu z symetrycznym podróżnym sprzedawcą (gdzie koszt krawędzi równa się kosztowi tej samej krawędzi, po przejściu w przeciwnym kierunku ), można go łatwo dostosować do alternatywy przypadek wersji asymetrycznej.( v , u $(u,v)$$(v,u)$

Najlepszym rozwiązaniem (jestem świadomy) składa się z prowadzeniem Depth-First-Branch i związana heurystycznego algorytmu wyszukiwania, heurystyczna jest koszt Minimum Spanning Tree (MST). Ponieważ MST można obliczyć w czasie wielomianowym za pomocą algorytmu Prim lub algorytmu Kruskala , można oczekiwać, że zwróci rozwiązania w rozsądnym czasie. Aby uzyskać wspaniałą dyskusję na temat tych dwóch algorytmów, zdecydowanie zalecamy zapoznanie się z instrukcją projektowania algorytmów

W rzeczywistości chciałbym podkreślić, że skoro zasugerowano to podejście, nie odnotowano znacznego postępu w zakresie ustalenia optymalnych granic tego problemu, dlatego uważam, że jest to gorące pytanie w dziedzinie poszukiwań kombinatorycznych.

Mam nadzieję że to pomoże,

Nie mam pojęcia, jak ktoś tutaj nie zauważył, że zastosowanie algorytmu Dijkstry byłoby w tym przypadku zupełnie niepotrzebne? Możesz zaimplementować ten zachłanny algorytm, po prostu wybierając najbliższy węzeł, który jest znany jako apriori. Algorytm Dijkstry służy do odkrywania ścieżek, ale za każdym razem robisz tylko jeden krok. To oczywiście nie znajduje optymalnego rozwiązania dla TSP, ale wiele bardzo dobrych podejść również go nie znajduje. Wszystkie wyszukiwarki optymalnych rozwiązań dla TSP są bardzo wymagające obliczeniowo.

Odpowiedź brzmi: nie, to nie jest dobry sposób na rozwiązanie problemu TSP. Dobrym przykładem jest sytuacja, w której wszystkie punkty znajdują się na linii, jak poniżej:

--5 ------------------ 3 ----- 1--0 --- 2 ---------- 4

użycie algorytmu Dijsktry sprawiłoby, że biedny sprzedawca zaczynałby od punktu 0, najpierw przechodził do 1, potem do 2, a potem do 3 ect. co nie jest optymalne.

Mam nadzieję, że to pomaga. Spójrz na pierwszy rozdział doskonałej książki Stevena S. Skieny zatytułowany „Projekt algorytmu”, który wyjaśnia ten przykład bardziej szczegółowo.

Problemem TSP nie jest znalezienie najkrótszej drogi między dwoma punktami, ale wyznaczenie trasy między wszystkimi punktami, które są optymalne. Gdy znajdziesz optymalną trasę, możesz użyć Dijsktra, aby znaleźć najkrótszą ścieżkę między poszczególnymi punktami na trasie.