STPS


Problem komiwojażera w encyklopedii

Z Wikipedii, wolnej encyklopedii (Przekierowano z STPS) Przejdź do nawigacji Przejdź do wyszukiwania Rozwiązanie przykładowego problemu komiwojażera: najkrótszą ścieżką przechodzącą przez wszystkie czerwone punkty jest czarna pętla.

Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym[1][2]

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][2].

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.

Główną trudnością problemu jest duża liczba danych do analizy. W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi ( n 1 ) ! 2 {\displaystyle {\frac {(n-1)!}{2}}} [3], tak więc dla 20 miast uzyskujemy wynik 19 ! 2 6 × 10 16 {\displaystyle {\frac {19!}{2}}\approx 6\times 10^{16}}

Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.

Spis treści

Historia | edytuj kod

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[4].

Za pierwszego autora, który sformalizował matematycznie problem komiwojażera uznaje się austriackiego matematyka Karla Mengera, który zdefiniował go w 1930[5] zwracając szczególną uwagę na trudność w obliczeniu rozwiązania[6]. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University[5]. Natomiast pierwsza próba rozwiązania problemu miała miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych[5].

Z uwagi na bardzo prosty opis problemu oraz opinię o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny[5]. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów[5][2].

Przykład | edytuj kod

Miasta: Kutno, Warszawa, Poznań, Kraków

Odległości:

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 kod

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 | edytuj kod

  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 | edytuj kod

  1. a b c Sysło, Deo i Kowalik 1995 ↓, s. 282.
  2. a b c Iwo, Iwona Białynicki-Birula, Białynicka-Birula: Modelowanie rzeczywistości. Warszawa: Prószyński i S-ka SA, 2002, s. 14-18. ISBN 83-7255-103-0.
  3. Problem komiwojażera, [w:] JerzyJ. Wałaszek JerzyJ., Algorytmy i struktury danych  (pol.).
  4. Sysło, Deo i Kowalik 1995 ↓, s. 283.
  5. a b c d e Sysło, Deo i Kowalik 1995 ↓, s. 314.
  6. The traveling salesman and the assignement problem, [w:] AlexanderA. Schrijver AlexanderA., Combinatorial Optimization: Polyhedra and Efficiency, s. 51  (ang.).

Bibliografia | edytuj kod

Linki zewnętrzne | edytuj kod

Kontrola autorytatywna (problem NP-zupełny):
Na podstawie artykułu: "STPS" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy