Najkrótsza ścieżka do odwiedzenia wszystkich węzłów

Question

Szukam algorytmu, który wydaje mi się bardzo typowy dla mnie, ale wydaje się, że wspólne rozwiązania są po prostu trochę inne.

Na nierekrekcyjnym wykresie potrzebuję najkrótszej ścieżki, która odwiedza każdy węzeł. Węzły można ponownie przeglądać i nie muszę wracać do węzła początkowego.

Wydaje się, że Problem z podróżującym sprzedawcą dodaje ograniczenie polegające na tym, że każdy węzeł może być odwiedzany tylko raz i że ścieżka musi powrócić do miejsca rozpoczęcia.

Minimalne drzewa opinające się mogą być częścią rozwiązania, ale takie algorytmy zapewniają tylko drzewo, a nie minimalną ścieżkę. Dodatkowo, ponieważ są to drzewa, a zatem nie mają pętli, zmuszają do cofnięcia się, gdy pętla może być bardziej wydajna.

Answer 1

Możesz zredukować go do normalnego problemu z podróżującym sprzedawcą, zmieniając wykres.

Najpierw należy obliczyć minimalną odległość dla każdej pary węzłów. Możesz użyć do tego algorytmu Floyd-Warshall. Po to, tak skonstruować kompletny wykres, na którym krawędź między węzłami U i V jest minimalne koszty z U do v.

Następnie można zastosować normalny algorytm TSP, ponieważ nie trzeba już ponownie odwiedzać węzłów, co już jest ukryte w kosztach krawędzi.