Algorytmy
49,00 zł
Nowoczesne receptury w Javie. Proste rozwiązania trudnych problemów
−30%38,43 zł
Wprowadzenie do obliczeń równoległych
−16%49,45 zł
Informatyka Europejczyka. Podręcznik dla szkoły podstawowej. Klasa 8
9,90 zł
Python. Uczenie maszynowe
69,00 zł
TDD. Techniki programowania sterowanego testami
59,00 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ż

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.

→ 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ść

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt