Problem komiwojażera

Problem komiwojażera jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w grafie.

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ść pomiędzy każdą parą miast.

Przykład:

Miasta={Kutno,Warszawa,Poznań,Kraków},

Odległości={ {Kutno,Kraków}=300, {Kutno,Warszawa}=130, {Kutno,Pozań}=180,

{Warszawa,Poznań}=320, {Warszawa,Kraków}=350, {Poznań,Kraków}=360}

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

Problem ten jest NP zupełny.

Symetryczny problem komiwojażera (STSP) polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. W asymetrycznym problemie komiwojażera (ATSP) odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A.

Linki zewnętrzne

• Algorytmy genetyczne, więcej o algorytmach genetycznych, zastosowanie do rozwiązywania problemu komiwojażera