Problem komiwojażera (TSP) — minimalny cykl Hamiltona w grafie ważonym

Definicja i model matematyczny

Standardowe sformułowanie TSP wykorzystuje wykres ważony: wierzchołki odpowiadają punktom do odwiedzenia, a krawędzie mają przypisaną wartość kosztu przejścia między punktami. Szukamy cyklu przechodzącego przez każdy wierzchołek dokładnie raz — to właśnie cykl Hamiltona w sensie grafowym — o najmniejszym możliwym sumarycznym koszcie.

Krótka historia

• W XIX wieku pojawiły się zagadki związane z odwiedzaniem punktów, m.in. problem cyklu Hamiltona, znany z rekreacyjnych gier i łamigłówek.
• W XX wieku matematycy i ekonomiści sformalizowali warianty problemu i rozważyli algorytmiczne podejścia; Hans Menger opisał problem i zwrócił uwagę, że jedynym oczywistym podejściem gwarantującym dokładne rozwiązanie jest przegląd wszystkich permutacji punktów.
• Menger zauważył również, że tzw. strategia „przechodź zawsze do najbliższego punktu” — czyli heurystyka najbliższego otoczenia — nie gwarantuje rozwiązania optymalnego; tę uwagę formułowano także w odniesieniu do heurystyk heurystycznych ogólnie.
• Nazewnictwo „problem podróżującego sprzedawcy” rozpowszechnił m.in. Hassler Whitney z Princeton University.

Złożoność obliczeniowa

TSP jest problemem trudnym obliczeniowo. Decyzyjna wersja problemu (czy istnieje trasa krótsza niż zadana granica) jest jednym z problemów NP‑zupełnych, a znalezienie optymalnej trasy należy do klasy problemów NP‑trudnych. W praktyce dla n punktów przegląd wszystkich możliwych tras wymaga rozważenia n! możliwości, co szybko staje się niepraktyczne.

Algorytmy i podejścia

W literaturze i praktycznych zastosowaniach rozróżnia się kilka grup metod:

• Algorytmy dokładne
  • Brute force — sprawdzenie wszystkich permutacji (gwarantowana optymalność, złożoność czynnikowa).
  • Programowanie dynamiczne (algorytm Held–Karp) — złożoność O(n^2 2^n), stosowany do umiarkowanych n.
  • Metody branch and bound i programowanie całkowite — praktyczne do średnich instancji, gdy zastosuje się silne ograniczenia i cięcia.
• Algorytmy przybliżone i aproksymacyjne
  • Wersje metryczne (spełniające nierówność trójkąta) pozwalają na aproksymacje z gwarancją błędu; przykładem jest algorytm Christofides dający aproksymację 1.5.
  • Algorytmy heurystyczne bez formalnych gwarancji, ale efektywne w praktyce (opisane poniżej).
• Heurystyki i algorytmy lokalnego przeszukiwania
  • Heurystyka najbliższego sąsiada — szybka, lecz nieskuteczna w najgorszym wypadku (Menger i inni wskazywali na jej ograniczenia).
  • Operacje poprawiające trasę: 2‑opt, 3‑opt, heurystyka Lin–Kernighan — polepszają istniejące rozwiązania przez lokalne modyfikacje.
  • Metaheurystyki: algorytmy genetyczne, symulowane wyżarzanie, algorytmy mrówkowe — znajdują dobre rozwiązania dla dużych instancji.

Warianty i zastosowania

Istnieje wiele wariantów TSP, dostosowanych do różnych ograniczeń i zastosowań:

• Symetryczny i asymetryczny TSP (koszty mogą zależeć od kierunku).
• Euclidean TSP — wierzchołki w przestrzeni euklidesowej, koszty równają się odległościom geometrycznym.
• Warianty z dodatkowymi ograniczeniami: okna czasowe, wielokrotni komiwojażerowie, koszty związane z ładunkiem, zadania typu „prize‑collecting”.

Praktyczne zastosowania obejmują optymalizację tras w logistyce i transporcie, planowanie produkcji i montażu (np. obróbka ścieżek w maszynach CNC), projektowanie obwodów drukowanych, a także zadania w bioinformatyce (np. porównywanie sekwencji genetycznych). W każdej z tych dziedzin wybór metody zależy od wielkości problemu i wymagań dotyczących jakości rozwiązania.

Uwagi końcowe

• Pomimo prostego sformułowania, Problem komiwojażera pozostaje jednym z najważniejszych i najczęściej badanych problemów w teorii algorytmów i optymalizacji.
• W praktyce łączy się teorię (klasyczna analiza złożoności) z inżynierskimi praktykami (heurystyki, metaheurystyki oraz specjalistyczne implementacje algorytmów dokładnych).
• Historyczne uwagi o trudnościach rozwiązania i zawodności prostych reguł, jak przechodzenie „do najbliższego sąsiada”, można znaleźć w pracach klasycznych autorów i komentarzach Mengera.