Natomiast pierwsza próba rozwiązania problemu miała miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych.
Z uwagi na bardzo prosty opis problemu oraz opinię o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów.
Przykład Miasta: Kutno, Warszawa, Poznań, Kraków
Odległości: {|class="wikitable" ! ! 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.
Uwagi
Przypisy
Bibliografia
Linki zewnętrzne
[dostęp 2025-12-20]. Travelling salesman problem , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-12-20].
K