🤝 Problem komiwojażera — TSP

Pyta o najkrótszą możliwą trasę, która odwiedza dany zbiór miast dokładnie raz i wraca do punktu wyjścia. Tutaj miasta to punkty na ekranie, a odległość jest prostoliniowa (euklidesowa), więc celem jest zminimalizowanie całkowitej długości trasy. To jeden z najczęściej badanych problemów optymalizacji kombinatorycznej.

TSP jest NP-trudny: żaden znany algorytm nie rozwiązuje go w czasie wielomianowym dla przypadku ogólnego. Liczba różnych tras rośnie jak (n-1)!/2, więc przy 20 miastach istnieje około 1,2 × 10^18 tras. Wyczerpujące sprawdzenie każdej trasy szybko staje się niemożliwe, dlatego stosuje się heurystyki.

Najbliższy sąsiad buduje trasę, zawsze skacząc do najbliższego nieodwiedzonego miasta. 2-opt wielokrotnie odwraca segmenty trasy, aby usunąć skrzyżowania i skrócić trasę. Symulowane wyżarzanie losowo zamienia miasta i czasem akceptuje gorsze trasy, stopniowo się chłodząc, aż osiądzie na dobrym rozwiązaniu.

Dla każdej losowej zamiany oblicza zmianę długości trasy, delta. Jeśli delta jest ujemna, ruch jest zawsze akceptowany. Jeśli delta jest dodatnia, jest akceptowany z prawdopodobieństwem exp(-delta / T), gdzie T to bieżąca temperatura. W miarę chłodzenia T ruchy pod górę stają się rzadsze, więc przeszukiwanie zawęża się od eksploracji do dopracowania.

Temperatura początkowa ustala wartość T0 (wartość suwaka razy 500), decydując, jak chętnie przeszukiwanie akceptuje gorsze trasy na początku. Chłodzenie ustala mnożnik na krok alfa między około 0,9995 a 0,99995; wartości bliższe 1 chłodzą wolniej, dając dłuższe, dokładniejsze przeszukiwanie, zanim temperatura spadnie blisko zera.

2-opt to czyste przeszukiwanie lokalne: akceptuje wyłącznie ulepszające zamiany, więc zbiega szybko, ale może utknąć w optimum lokalnym, z którego nie może uciec. Symulowane wyżarzanie akceptuje okazjonalny gorszy ruch, pozwalając wyskoczyć z takich pułapek. Na niektórych układach wygrywa determinizm 2-opt; na innych losowość wyżarzania znajduje krótszą trasę.

Długość trasy to całkowity dystans bieżącej trasy; Najlepsza znaleziona to najkrótsza dotąd widziana trasa, narysowana blado na zielono. Iteracje liczą kroki algorytmu, Temperatura pokazuje bieżącą wartość T wyżarzania, a Ulepszenia liczą, ile ruchów faktycznie skróciło trasę.

Prędkość wybiera, ile kroków algorytmu wykonuje się na klatkę animacji, od 1 do 20 000 przy najwyższym ustawieniu, dzięki czemu można oglądać powoli lub zbiegać szybko. Przycisk Krok przesuwa dokładnie o jedną iterację naraz, co przydaje się do badania, jak pojedyncza zamiana lub odwrócenie zmienia trasę.

Nie. Wszystkie trzy metody to heurystyki dążące do tras bliskich optymalnym, a nie dowodliwie najkrótszych. Najbliższy sąsiad może być o 25 procent lub więcej gorszy od optimum; 2-opt i symulowane wyżarzanie zwykle radzą sobie znacznie lepiej, ale bez gwarancji. Znalezienie dokładnego optimum dla wielu miast wymaga znacznie cięższych technik dokładnego rozwiązywania.

TSP i jego warianty pojawiają się w trasowaniu przesyłek i dostaw, wierceniu otworów w płytkach drukowanych, planowaniu obserwacji teleskopowych, planowaniu sekwencjonowania DNA i optymalizacji ścieżek narzędzi w produkcji. Te same idee zamiany i ulepszania pokazane tutaj skalują się, z udoskonaleniami, do przemysłowego oprogramowania trasującego obsługującego tysiące przystanków.