Problem komiwojażera
Przykładowy cykl Hammiltona
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.
Liczba głosów: 0.
Dodano: 1 października 2016 13:08, ostatnia edycja: 7 sierpnia 2017 11:23.
Zobacz też
Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).
Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.
Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.
Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.