Problem komiwojażera wyjaśniony
Daj komiwojażerowi listę miast i zapytaj o najkrótszą podróż, która odwiedza każde z nich raz i wraca do domu. Każdy może sprawdzić zaproponowaną trasę i każdy może na oko poprawić złą, a jednak nikt nie zna szybkiej metody, która zawsze znajduje najlepszą. Problem komiwojażera stał się standardowym przykładem trudnego problemu, a metody wymyślone, by się z nim zmierzyć, planują dziś dostawy, wiercą płytki drukowane i składają genomy.
Problem
Trasa odwiedza każde miasto dokładnie raz i kończy się tam, gdzie się zaczęła; jej długość to suma odległości po drodze. Zadanie polega na znalezieniu najkrótszej trasy. W wersji przedstawionej tutaj odległości to odcinki prostej na mapie, więc droga z A do C nigdy nie jest dłuższa niż droga przez B: to metryczny problem komiwojażera. Zagadkę omawiał matematyk Karl Menger około 1930 roku, a nazwa upowszechniła się w kolejnych dekadach, gdy zajęli się nią matematycy z RAND Corporation.
Eksplozja liczby tras
Ustal miasto startowe. Jest n − 1 możliwości wyboru następnego miasta, n − 2 dla kolejnego i tak dalej, a każdą trasę można przejechać w dwóch kierunkach, więc tras jest (n − 1)! / 2. Dla 10 miast to 181 440, łatwo dla komputera. Dla 20 to około 6 × 10¹⁶, a dla 70 więcej niż atomów w obserwowalnym Wszechświecie. Szybsze komputery niewiele pomagają: każde dodatkowe miasto mnoży pracę mniej więcej przez n.
NP-trudność
W 1972 roku Richard Karp wykazał, że pytanie, czy graf ma trasę zamkniętą przez każdy wierzchołek, czyli cykl Hamiltona, należy do rodziny problemów NP-zupełnych, które są wszystkie równie trudne. Problem komiwojażera zawiera to pytanie, więc jest NP-trudny. Szybka metoda dla niego dałaby szybkie metody dla tysięcy innych problemów z zakresu harmonogramowania, logistyki i kryptografii. To, czy taka metoda istnieje, jest problemem P vs NP, jednym z problemów milenijnych.
Metoda dokładna: Held–Karp
W 1962 roku Michael Held i Richard Karp, a niezależnie od nich Richard Bellman, zastosowali programowanie dynamiczne. Dla każdego zbioru S miast i każdego miasta j w S oblicza się najkrótszą ścieżkę, która zaczyna się w mieście domowym, odwiedza dokładnie miasta z S i kończy się w j. Każda wartość wynika z wartości dla S bez j, więc tabelę wypełnia się od małych zbiorów do dużych, a na końcu otrzymuje się najkrótszą trasę. Potrzeba około n² · 2ⁿ kroków zamiast n!, co dla 30 miast oznacza różnicę między minutami a wiekiem Wszechświata, ale liczba kroków wciąż rośnie wykładniczo.
Szybkie reguły konstrukcji
Najbliższy sąsiad zawsze jedzie do najbliższego jeszcze nieodwiedzonego miasta. Jest prosty i szybki, ale zwykle zostawia na uboczu kilka miast, po które trzeba na końcu jechać długimi objazdami, więc jego trasy są zwykle o około 25% dłuższe od najlepszej. Metody wstawiania utrzymują natomiast zamkniętą pętlę i dodają pozostałe miasta po jednym tam, gdzie kosztują najmniej. W 1976 roku Nicos Christofides znalazł konstrukcję, która na każdej mapie metrycznej gwarantuje wynik nie gorszy niż 1,5 raza optimum – ograniczenie, które przez ponad czterdzieści lat pozostawało niemal niepobite.
Ulepszanie trasy: 2-opt
Przeszukiwanie lokalne zaczyna od dowolnej trasy i raz po raz wprowadza drobne zmiany, które ją skracają. Klasyczny ruch, 2-opt, usuwa dwie krawędzie i łączy dwa kawałki na odwrót, co odwraca odcinek między nimi. Gdy dwie krawędzie się przecinają, ten ruch je rozplątuje i skraca trasę, więc trasa, której 2-opt nie potrafi ulepszyć, nigdy się nie przecina. Na losowych mapach trasy 2-opt są zwykle około 5% powyżej optimum. Silniejsze ruchy, zamieniające trzy krawędzie, albo metoda Lina i Kernighana o zmiennej głębokości z 1973 roku podchodzą jeszcze bliżej.
Symulowane wyżarzanie
Przeszukiwanie lokalne może utknąć na trasie, przy której każdy pojedynczy ruch ją pogarsza, choć istnieje dużo lepsza trasa. Symulowane wyżarzanie, zastosowane do tego problemu przez Scotta Kirkpatricka, Daniela Gelatta i Maria Vecchiego w 1983 roku, czerpie z metalurgii: przyjmuje gorszy ruch z prawdopodobieństwem zależnym od temperatury, która na początku jest wysoka i powoli spada. Na początku trasa swobodnie błądzi; na końcu przyjmowane są tylko ulepszenia. Przy dostatecznie powolnym chłodzeniu metoda niezawodnie znajduje bardzo dobre trasy.
Wypróbuj
Otwórz demo problemu komiwojażera, aby umieścić do 200 miast losowo, na okręgu, w skupiskach, na siatce albo tam, gdzie klikniesz. Zobacz, jak najbliższy sąsiad zostawia na uboczu ostatnie miasta, jak 2-opt rozplątuje każde skrzyżowanie, śledź temperaturę symulowanego wyżarzania podczas stygnięcia i pozwól algorytmowi Helda–Karpa udowodnić najkrótszą trasę dla maksymalnie 12 miast. Porównaj wszystkie uruchamia każdą metodę na tej samej mapie i pokazuje, o ile każda trasa jest dłuższa od najkrótszej znalezionej.
Często zadawane pytania
Gdzie wykorzystuje się problem komiwojażera?
Wszędzie tam, gdzie coś musi odwiedzić wiele miejsc w wydajnej kolejności: trasy dostaw i odbiorów, ścieżka wiertła lub lasera nad płytką drukowaną, kolejność, w jakiej teleskop obserwuje gwiazdy, kompletacja zamówień w magazynie oraz – przy innych odległościach – kolejność fragmentów podczas składania sekwencji DNA.
Jaki jest największy problem, jaki kiedykolwiek rozwiązano dokładnie?
W 1954 roku George Dantzig, Ray Fulkerson i Selmer Johnson udowodnili najkrótszą trasę przez 49 miast w Stanach Zjednoczonych. W 2006 roku solver Concorde autorstwa Davida Applegate'a, Roberta Bixby'ego, Vaška Chvátala i Williama Cooka po latach obliczeń komputerowych udowodnił optymalność trasy przez 85 900 punktów z projektu układu scalonego.
Czy najkrótsza trasa zawsze jest wolna od skrzyżowań?
Tak, na płaskiej mapie z odległościami w linii prostej. Gdyby dwie krawędzie się przecinały, zamiana ich na dwa boki tworzonego przez nie czworokąta skróciłaby trasę, więc trasa ze skrzyżowaniem nie może być najkrótsza.
Czy heurystyki za każdym razem dają tę samą trasę?
Najbliższy sąsiad, najtańsze wstawianie i 2-opt w użytej tu postaci są deterministyczne: na tych samych miastach dają tę samą trasę. Symulowane wyżarzanie zaczyna od losowej trasy i wykonuje losowe ruchy, więc dwa przebiegi mogą zakończyć się różnymi trasami, zwykle o prawie tej samej długości.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz demo problemu komiwojażera