Problem komiwojażera

Cykl Hammiltona Przykładowy cykl Hammiltona
Algorytm najbliższego sąsiada animacja Rozwiązanie problemu komiwojażera za pomocą algorytmu najbliższego sąsiada

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

Wybrane algorytmy

Wybrane algorytmy wykorzystywane do rozwiązywania problemu komiwojażera zaprezentowano w poniższej tabeli. Przez algorytm dokładny rozumiemy algorytm gwarantujący znalezienie rozwiązania optymalnego.

Algorytm Dokładny Złożoność czasowa
Sprawdzenie wszystkich wariantów Tak O(n!)
Algorytm Helda-Karpa Tak O(n22n)
Algorytm najbliższego sąsiada Nie O(n2)
Algorytm najmniejszej krawędzi Nie O(n2log n)
Algorytm RNN Nie O(n3)

Do rozwiązywania problemu komiwojażera można wykorzystać również algorytm genetyczny (przykład). Rozwiązanie uzyskane za pomocą algorytmów niedokładnych można ulepszać korzystając z metod lokalnej optymalizacji. Przykładem takiej metody jest algorytm 2-optymalny będący najprostszym wariantem algorytmu k-optymalnego.

Problemy pokrewne

Problem komiwojażera ma liczne modyfikacje i problemy pokrewne. Jednym z nich jest problem marszrutyzacji, w którym wierzchołki mają znaleźć się nie w jednym cyklu, a w kliku osobnych.

Dodano: 1 października 2016 13:08
Ostatnia edycja: 7 sierpnia 2017 11:23