- Trasa
- Najkrótsza znaleziona
- Start
| Metoda | Długość | Powyżej najkrótszej | Kroki |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
Problem komiwojażera
Komiwojażer musi odwiedzić każde miasto raz i wrócić do domu. W jakiej kolejności podróż będzie najkrótsza? Pytanie łatwo zadać, ale wraz ze wzrostem liczby miast nie ma nadziei na odpowiedź przez sprawdzanie każdej kolejności: już 30 miast daje około 4,4 × 10³⁰ tras zamkniętych. Rozrzuć miasta na mapie albo wyklikaj własne i obserwuj, jak szybkie reguły kciuka, sprytne ulepszenia i jedna metoda dokładna krok po kroku budują swoje trasy – i zobacz, jak blisko podchodzą szybkie metody. Wybierz, jak rozmieszczone są miasta i ile ich jest, wybierz metodę i naciśnij Rozwiąż, aby zobaczyć, jak krok po kroku buduje trasę zamkniętą, albo Krok, aby wykonywać jeden ruch naraz. Kliknij mapę, aby dodać miasto, albo kliknij miasto, aby je usunąć. Porównaj wszystkie uruchamia każdą metodę na tych samych miastach i pokazuje, jak daleko każda z nich jest od najkrótszej znalezionej trasy. Czerwone miasto to punkt startowy podróży.
Jak to działa
- Wybierz układ i liczbę miast albo kliknij mapę, aby postawić własne, a kliknij miasto, aby je usunąć.
- Wybierz metodę i naciśnij Rozwiąż, aby obserwować ją krok po kroku, albo Krok, aby wykonywać jeden ruch naraz.
- Naciśnij Porównaj wszystkie, aby uruchomić każdą metodę na tych samych miastach, i sprawdź, o ile każda trasa jest dłuższa od najkrótszej znalezionej.
Dlaczego to trudne
Przy n miastach istnieje (n − 1)! / 2 różnych tras zamkniętych, bo nie ma znaczenia, gdzie zaczynasz ani w którą stronę jedziesz. To 12 dla 5 miast, 181 440 dla 10 i około 6 × 10¹⁶ dla 20. Nie jest znana żadna metoda, która dla każdej mapy znajduje najkrótszą trasę w czasie rosnącym tylko jak potęga n; problem jest NP-trudny. Najlepsza metoda dokładna w tej aplikacji, programowanie dynamiczne Helda–Karpa z 1962 roku, wciąż wymaga około n² · 2ⁿ kroków, dlatego jest tu ograniczona do 12 miast.
Dobre trasy szybko
W praktyce prawie najkrótsze trasy znajduje się szybko. Najbliższy sąsiad zawsze jedzie do najbliższego nieodwiedzonego miasta i zwykle kończy około 25% powyżej najlepszej trasy. Najtańsze wstawianie rozbudowuje pętlę i dodaje to miasto, które wydłuża ją najmniej. 2-opt bierze dowolną trasę i raz po raz zastępuje dwie krawędzie dwiema krótszymi, co usuwa wszystkie skrzyżowania i zwykle daje wynik w granicach około 5%. Symulowane wyżarzanie wykonuje losowe ruchy 2-opt i, dopóki jest jeszcze „gorąco”, przyjmuje też niektóre ruchy wydłużające trasę, dzięki czemu może wydostać się ze ślepych zaułków, zanim się ustabilizuje.
Często zadawane pytania
Czy istnieje wzór na najkrótszą trasę?
Nie. Najkrótsza trasa zależy od dokładnego położenia wszystkich miast i żadna znana metoda nie znajduje jej dla każdej mapy bez nakładu pracy, który w najgorszym przypadku rośnie wykładniczo. Dla kilkuset czy kilku tysięcy miast wyspecjalizowane solvery dokładne, takie jak Concorde, nadal dowodzą optymalności tras, łącząc programowanie liniowe ze sprytnym odcinaniem, a największa dotąd dokładnie rozwiązana instancja ma 85 900 punktów.
Dlaczego 2-opt usuwa wszystkie skrzyżowania?
Jeśli dwie krawędzie trasy się przecinają, cztery miasta, które łączą, tworzą czworokąt, którego przekątnymi są te dwie krawędzie. Zamiana ich na dwa przeciwległe boki czworokąta jest zawsze krótsza na mocy nierówności trójkąta i odwraca odcinek trasy pomiędzy nimi. 2-opt wykonuje takie zamiany, dopóki żadna nie pomaga, więc jego końcowa trasa nigdy się nie przecina.
Czym jest temperatura w symulowanym wyżarzaniu?
Określa, jak chętnie metoda przyjmuje ruch, który wydłuża trasę. Ruch, który dodaje d do długości, jest przyjmowany z prawdopodobieństwem e^(−d/T). Przy wysokiej temperaturze T dozwolone jest prawie wszystko, co pozwala trasie wyrwać się ze słabego ułożenia; gdy T spada, metoda staje się zachłanna i się stabilizuje. Nazwa pochodzi od powolnego chłodzenia metalu, dzięki któremu jego atomy znajdują ułożenie o niskiej energii.
Dlaczego metoda dokładna jest ograniczona do 12 miast?
Held–Karp przechowuje najkrótszą ścieżkę dla każdego podzbioru miast i każdego możliwego ostatniego miasta, czyli około n · 2ⁿ liczb, i wypełnia każdą z nich za pomocą n porównań. Dla 12 miast to kilkaset tysięcy kroków; dla 25 miast byłyby to miliardy. To wciąż ogromnie szybciej niż sprawdzanie wszystkich (n − 1)! / 2 tras: dla 12 miast byłoby ich prawie 20 milionów.
Czy cokolwiek jest wysyłane na serwer?
Nie. Miasta i wszystkie pięć metod działają w twojej przeglądarce. Miasta, które wyklikasz, pozostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora