alt=Rozwiązanie przykładowego problemu komiwojażera|mały|Rozwiązanie przykładowego problemu komiwojażera: najkrótszą ścieżką przechodzącą przez wszystkie czerwone punkty jest czarna pętla.
Problem komiwojażera () – 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.
Główną trudnością problemu jest duża liczba danych do analizy. W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi , tak więc dla 20 miast uzyskujemy wynik
Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
Przykładowe algorytmy znajdujące przybliżone rozwiązania problemu komiwojażera to algorytm najbliższego sąsiada i algorytm Christofidesa.
Historia Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832Oryginalny tytuł: Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur, który zawiera przykładową trasę po Niemczech i Szwajcarii, lecz nie zawiera żadnych matematycznych uzasadnień.
W 1859 irlandzki matematyk William Rowan Hamilton sformułował problem istnienia cyklu o długości n w grafie n-wierzchołkowym.
Za pierwszego autora, który sformalizował matematycznie problem komiwojażera uznaje się austriackiego matematyka Karla Mengera, który zdefiniował go w 1930 zwracając szczególną uwagę na trudność w obliczeniu rozwiązania. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University. 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