Otwórz menu główne

Zmiany

źródła/przypisy
{{Teoria grafów}}
'''Problem komiwojażera''' ({{ang.|travelling salesman problem, TSP}}) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|pełnym grafie ważonym]]{{odn|Sysło|Deo|Kowalik|1995|s=282}}.
 
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{{odn|Sysło|Deo|Kowalik|1995|s=282}}.
 
'''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.
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 [[Problem NP-trudny|NP-trudny]]{{odn|Sysło|Deo|Kowalik|1995|s=282}}.
 
== Wersja decyzyjna ==
 
Tak sformułowany problem jest [[problem NP-zupełny|NP-zupełny]].
 
{{przypisy}}
 
== Bibliografia ==
* {{Cytuj | autor=[[Maciej Marek Sysło]]; Narsingh Deo; Janusz S. Kowalik | tytuł=Algorytmy optymalizacji dyskretnej | wydawca=[[Wydawnictwo Naukowe PWN]] | miejsce=Warszawa | data=1995 | wydanie=drugie | isbn=83-01-11818-0 | odn=tak}}
 
 
[[Kategoria:Teoria grafów]]