Problem komiwojażera

Cykl Hammiltona (1) Przykładowy cykl Hammiltona
Algorytm najbliższego sąsiada animacja (2) Rozwiązanie problemu komiwojażera za pomocą algorytmu najbliższego sąsiada

Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.

Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.

Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.

Wybrane algorytmy

Wybrane algorytmy wykorzystywane do rozwiązywania problemu komiwojażera zaprezentowano w poniższej tabeli. Przez algorytm dokładny rozumiemy algorytm gwarantujący znalezienie rozwiązania optymalnego.

Algorytm Dokładny Złożoność czasowa
Sprawdzenie wszystkich wariantów Tak O(n!)
Algorytm Helda-Karpa Tak O(n22n)
Algorytm najbliższego sąsiada Nie O(n2)
Algorytm najmniejszej krawędzi Nie O(n2log n)
Algorytm RNN Nie O(n3)

Do rozwiązywania problemu komiwojażera można wykorzystać również algorytm genetyczny (przykład). Rozwiązanie uzyskane za pomocą algorytmów niedokładnych można ulepszać korzystając z metod lokalnej optymalizacji. Przykładem takiej metody jest algorytm 2-optymalny będący najprostszym wariantem algorytmu k-optymalnego.

Problemy pokrewne

Problem komiwojażera ma liczne modyfikacje i problemy pokrewne. Jednym z nich jest problem marszrutyzacji, w którym wierzchołki mają znaleźć się nie w jednym cyklu, a w kliku osobnych.

Ocena: +4 Tak Nie
Liczba głosów: 4.

Dodano: 1 października 2016 13:08, ostatnia edycja: 7 sierpnia 2017 11:23.

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość

Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

→ Czytaj całość

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

→ Czytaj całość
Polityka prywatnościKontakt