Otwórz menu główne

Zmiany

m
drobne red.
{{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.
 
== Historia ==
Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832<ref group="uwaga">Oryginalny 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''</ref>, 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{{odn|Sysło|Deo|Kowalik|1995|s=283}}.
 
Za faktycznego twórcę problemu komiwojażera uznaje się austriackiego matematyka [[Karl Menger|Karla Mengera]], który go zdefiniował w 1930{{odn|Sysło|Deo|Kowalik|1995|s=314}}, zwracając szczególną uwagę na stopień jego skomplikowania<ref>{{Cytuj | autor = Alexander Schrijver | rozdział = The traveling salesman and the assignement problem | url = https://books.google.pl/books?id=mqGeSQ6dJycC&pg=PA50&lpg=PA50&dq=Botenproblem&source=bl&ots=xQLOOZfpNf&sig=Q4GV-PhBgjRtatHa5A3IgoVhmpk&hl=pl&sa=X&ved=0ahUKEwiBp_Xiie7MAhWMFJoKHb3SBBEQ6AEIKDAB#v=onepage&q=Botenproblem&f=false | tytuł = Combinatorial Optimization: Polyhedra and Efficiency | s = 51 | język = en }}</ref>. Niezależnie od niego ten sam problem poruszył w 1934 [[Hassler Witney]] na wykładzie w [[Princeton University]]{{odn|Sysło|Deo|Kowalik|1995|s=314}}. Natomiast pierwsze praktyczne zastosowanie problemu miało miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych{{odn|Sysło|Deo|Kowalik|1995|s=314}}.
 
Z uwagi na bardzo prosty opis problemu oraz opinii o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny{{odn|Sysło|Deo|Kowalik|1995|s=314}}. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów{{odn|Sysło|Deo|Kowalik|1995|s=314}}.
 
== Przykład ==
'''Miasta:''' Kutno, Warszawa, Poznań, Kraków
 
Tak sformułowany problem jest [[problem NP-zupełny|NP-zupełny]].
 
{{uwagiUwagi}}
 
{{przypisyPrzypisy}}
 
== 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}}
 
== Linki zewnętrzne ==
* {{Cytuj | url = http://www.math.uwaterloo.ca/tsp/index.html | tytuł = Traveling Salesman Problem | język = en | data dostępu = 2016-05-22 | język=en }}
 
[[Kategoria:Teoria grafów]]