Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł
Zrozum struktury danych. Algorytmy i praca na danych w Javie
−30%27,93 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Kwalifikacja EE.08. Montaż i eksploatacja systemów komputerowych, urządzeń peryferyjnych i sieci. Część 2. Systemy operacyjne. Podręcznik do nauki zawodu technik informatyk
37,95 zł
Kwalifikacja E.12. Montaż i eksploatacja komputerów osobistych oraz urządzeń peryferyjnych. Podręcznik do nauki zawodu technik informatyk
57,00 zł
Kwalifikacja E.14. Część 3. Tworzenie aplikacji internetowych. Podręcznik do nauki zawodu technik informatyk
37,95 zł

Problem komiwojażera

Cykl Hammiltona Przykładowy cykl Hammiltona
Algorytm najbliższego sąsiada animacja 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: 0 Tak Nie
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!)).

→ Czytaj całość

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.

→ Czytaj całość

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.

→ Czytaj całość
Polityka prywatnościKontakt