Problem komiwojażera: Różnice pomiędzy wersjami

[wersja przejrzana][wersja przejrzana]
Usunięta treść Dodana treść
m drobne red.
Rozbudowa
Linia 1:
{{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}}.<ref name=":0">{{Cytuj książkę|nazwisko=Białynicki-Birula, Białynicka-Birula|imię=Iwo, Iwona|tytuł=Modelowanie rzeczywistości|rok=2002|wydawca=Pruszyński i S-ka SA|miejsce=Warszawa|strony=14-18|isbn=83-7255-103-0}}</ref>
 
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}}<ref name=":0" />.
 
Główną trudnością problemu jest duża liczba danych do analizy. Dla ''n'' miast liczba kombinacji wynosi <math>\frac{n!}{2}</math>, tak więc dla 20 miast uzyskujemy wynik <math>\frac{19!}{2}=6\times 10^{16}</math><ref name=":0" />
 
'''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.
Linia 16 ⟶ 18:
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}}<ref name=":0" />.
 
== Przykład ==