Problem komiwojażera

Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość/cena podróży/czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.

Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.

Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.

Przykład

Miasta: Kutno,Warszawa,Poznań,Kraków

Odległości:

	Kutno	Warszawa	Poznań	Kraków
Kutno	0	130	180	300
Warszawa	130	0	320	350
Poznań	180	320	0	360
Kraków	300	350	360	0

Należy znaleźć najkrótszą trasę zaczynającą się np. z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.

Problem ten jest NP-trudny.

Wersja decyzyjna

W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.

Tak sformułowany problem jest NP-zupełny.