Problem komiwojażera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu teoria grafów.




Najważniejsze pojęcia
graf
drzewo
podgraf
cykl
klika
stopień wierzchołka
stopień grafu
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


Algorytmy grafowe
A*
Bellmana-Forda
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
wszerz
w głąb
najbliższego sąsiada


Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem marszrutyzacji
problem kojarzenia małżeństw


Inne zagadnienia
kod Graya
diagram Hassego
kod Prüfera


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[edytuj]

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[3], zwracając szczególną uwagę na stopień jego skomplikowania[4]. 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[edytuj]

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[edytuj]

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.

Uwagi

  1. 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

Przypisy

  1. a b c Sysło, Deo i Kowalik 1995 ↓, s. 282.
  2. Sysło, Deo i Kowalik 1995 ↓, s. 283.
  3. a b c d e Sysło, Deo i Kowalik 1995 ↓, s. 314.
  4. The traveling salesman and the assignement problem, [w:] AlexanderA. Schrijver AlexanderA., Combinatorial Optimization: Polyhedra and Efficiency, s. 51 (ang.).

Bibliografia[edytuj]

Linki zewnętrzne[edytuj]