Wersja z 18:28, 22 maj 2016 edytuj Paweł Ziemian (dyskusja \| edycje) Redaktorzy, Administratorzy interfejsu, Administratorzy 68 275 edycji →‎Historia: drobne merytoryczne ← poprzednia edycja		Wersja z 18:15, 10 cze 2016 edytuj anuluj edycję WikiZuber (dyskusja \| edycje) Redaktorzy 1199 edycji m drobne red. następna edycja →
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}}. 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. Linia 9 ⟶ 10: == 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 Linia 62 ⟶ 63: Tak sformułowany problem jest [[problem NP-zupełny\|NP-zupełny]]. {{~~uwagi~~Uwagi}} {{~~przypisy~~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}} == 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]]

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