Problem handlowca: NP-twardy w praktyce

Problem, który brzmi prosto i nie jest

Zadanie handlowca pyta o najkrótszą ścieżkę, która odwiedza każdy miasto dokładnie raz i zwraca się do punktu wyjścia. Dla n miast istnieje (n−1)!/2 różnych możliwych tur (dzielimy przez 2 dla kierunku, konwencjonalnie ustalając startowe miasto), które rosną tak ekspansywnie, że sprawdzenie wszystkich tur siłą obliczeń jest realistyczne tylko dla kilkunastu miast — już 15 miast oznacza ponad 43 miliardy tur. Zadanie handlowca (TSP) jest NP-twardy: nie znane są algorytmy, które rozwiązywali by każdą instancję z gwarantowaną optymalnością w czasie, który skali się wielomianowo ze względu na n, a większość teoretyków złożoności przypuszcza, że takich nie ma. To nie oznacza, że problem jest bezradny w praktyce — oznacza to, że dokładne rozwiązania stają się drogie, dlatego rzeczywiste rozwiązania traktują małą ilość optymalności za ogromną ilość szybkości.

Najbliższy sasiad: szybki, zaoferowy i dowodowo nieidealny

Najprostsze heurystyka zaczyna się w dowolnym mieście i powtarzająco podróżuje do najbliższego jeszcze niewiedzionego miasta, aż wszystkie zostaną odwiedzone, a następnie wraca do punktu startu. Uruchamia się ona w czasie O(n²) i jest proste do zaimplementowania, ale jest krótkowzroczna: wcześniejsza zaoferowaona decyzja może osadzić turę daleko od miast, które nadal musi odwiedzić później, a można udowodnić, że tury najbliższego sasiada mogą być dowolnie gorsze niż optymalne w najgorszym przypadku. W praktyce dla typowych układów miast osiąga ona długość tur 20–30% powyżej optymalnej — to dobry punkt wyjścia, ale nie końcowe rozwiązanie.

2-opt: rozpuszczanie skrzyżowanych krawędzi

2-opt przyjmuje dowolny tur i powtarzająco szuka dwóch krawędzi, które się skrzyżują lub można wymienić, aby zredukować całkowitą długość: usuwa dwie krawędzie, łączy dwa otrzymane fragmenty ścieżki inaczej i zachowuje zmianę, jeśli zwiększa ona krótkość trasy.

dla każdej pary krawędzi (i, i+1) oraz (j, j+1) w turze, gdzie i < j: newLength = długość z odwróconym segmentem [i+1 .. j] jeśli newLength < currentLength: wykonaj odwrót powtarzaj aż nie będzie już poprawnych wymian (lokalny optimum) Zastosowane na podstawie startu najbliższego sąsiada, 2-opt zwykle zamyka większość tego odcinka 20–30% — często osiągając dystans bliski do idealnego dla małych i średnio wielkich instancji. Jego słabością jest to, że jest szukanie lokalne: zatrzymuje się na pierwszej turze, w której żadna pojedyncza wymiana 2-opt nie pomaga, co niekoniecznie jest globalnym optimum — może być zablokowany w lokalnym minimum otoczonego przez gorsze trasy w każdym kierunku dozwolonym przez 2-opt.

for each pair of edges (i, i+1) and (j, j+1) in the tour, i < j:
  newLength = length with segment [i+1 .. j] reversed
  if newLength < currentLength: apply the reversal
repeat until no improving swap exists (a local optimum)

Zimny odcinek: świadomie ucieczka z lokalnych optymów

Simulated Annealing (Kirkpatrick, Gelatt & Vecchi, 1983) wykorzystuje zasady przyjęcia z mechaniki statystycznej: na każdym kroku propozycja losowego małego zmiany w trasie (na przykład zamiany 2-opt) jest akceptowana, jeśli poprawia trasę — ale także z pewną prawdopodobieństwem, nawet gdy spowolni ona trasę, gdzie to prawdopodobieństwo zależy od tego, jak znacznie spowolni to ruch, oraz od parametru temperatury, który maleje podczas trakcyi.

T = T0 while T > Tmin: kandydat = losowaZamiana(obecnaTrasa) delta = długość(kandydat) - długość(obecnejTrasy) if delta < 0 or random() < exp(-delta / T): obecnaTrasa = kandydat // akceptujemy, nawet jeśli spowolni to trasę T *= prędkośćOchłodzenia // np. 0,995 na każdym kroku Wczesniej, gdy temperatura jest wysoka, algorytm akceptuje wiele ruchów spowalniających i efektywnie eksploruje szersze obszary, skakając z powodu lokalnych optymów, które mogłyby ztrapić 2-opt samodzielnie; przy ochłodzeniu temperatury, akceptuje coraz mniej ruchów spowalniających i ustępuje do refinerii, zachowując się coraz bardziej jak prosty 2-opt na końcu trakcyi. Daje się osiągnąć konieczność dostatecznie wolnego schematu ochłodzenia, aby zasada zimnego odcinka była gwarantowana do zbiegnięcia się w globalny optum — gwarancja, która jest bardziej teoretyczna niż praktyczna, ponieważ dostatecznie wolny schemat może trwać dłużej niż brute force, ale przy praktycznych speedach ochłodzenia zasada zimnego odcinka w praktyce przewyższa 2-opt samodzielnie na tym samym przykładzie.

T = T0
while T > Tmin:
  candidate = randomSwap(currentTour)
  delta = length(candidate) - length(currentTour)
  if delta < 0 or random() < exp(-delta / T):
    currentTour = candidate      // accept, sometimes even if worse
  T *= coolingRate               // e.g. 0.995 per step

Co na tym stronie pokazuje rzeczywista rozgrywka

Obserwacja trzech ruchów na tej samej zestawieniu miast bezpośrednio ukazuje ich kompromisy: najbliższy sąsiad kończy pierwsze i najgorsze, 2-opt kończy drugie i osiąga widocznie rozwiązań bez zmian, podczas gdy anelżenie symulowane nadal widocznie perturbuje swój turę nawet po tym, jak 2-opt zatrzyma się — to stałe przemierzanie się, co czasami sprawia, że turę chwilowo dłuższą, jest exactly mechanizmem, który pozwala mu znaleźć krótsze tury niż 2-opt osiąga sam.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Travelling Salesman — TSP i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.