Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
+ Historia, LZ |
→Historia: źródła/przypisy |
||
| Linia 13: | Linia 13: | ||
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}}. |
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. 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= |
Za faktycznego twórcę problemu komiwojażera uznaje się austriackiego matematyka [[Karl Menger|Karla Mengera]], który go zdefiniował w 1930. 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= |
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 == |
== Przykład == |
||
Wersja z 18:13, 22 maj 2016
| Najważniejsze pojęcia | |
|---|---|
| Wybrane klasy grafów | |
| Algorytmy grafowe | |
| Zagadnienia jako problemy grafowe | |
| Inne zagadnienia |
Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym[1].
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[1].
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.
Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.
Historia
Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832[a], 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[2].
Za faktycznego twórcę problemu komiwojażera uznaje się austriackiego matematyka Karla Mengera, który go zdefiniował w 1930. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University[3]. Natomiast pierwsze praktyczne zastosowanie problemu miało miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych[3].
Z uwagi na bardzo prosty opis problemu oraz opinii o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny[3]. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów[3].
Przykład
Miasta: Kutno, Warszawa, Poznań, Kraków
Odległości:
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[1].
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.
- ↑ 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
- ↑ a b c Sysło, Deo i Kowalik 1995 ↓, s. 282.
- ↑ Sysło, Deo i Kowalik 1995 ↓, s. 283.
- ↑ a b c d Sysło, Deo i Kowalik 1995 ↓, s. 314.
Bibliografia
- Maciej Marek Sysło, Narsingh Deo, Janusz S. Kowalik, Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0.
Linki zewnętrzne
- Traveling Salesman Problem [online] [dostęp 2016-05-22] (ang.).