algorytm.org

Problem komiwojażera

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Problem komiwojażera
Ocena użytkowników:***** / 21
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:30

Problem komiwojażera jest ściśle związany z cyklem Hamiltona w grafie, tzn. takim cyklem, który zawiera każdy z wierzchołków danego grafu dokładnie 1 raz.
Problem komiwojażera przedstawia się następująco: komiwojażer musi odwiedzić n miast w taki sposób, by wrócił do miasta, z którego wyruszył pokonując jak najmniejszą drogę, musi wyznaczyć więc sobie taką trasę między miastami, aby całkowity koszt jego podróży był najmniejszy. Problem ten można przestawić za pomocą grafu pełnego, tzn. grafu o stuprocentowym nasyceniu krawędziowym, co oznacza, że każda para wierzchołków jest połączona krawędzią. Miasta, które musi odwiedzić komiwojażer są wierzchołkami, a drogi łączące te miasta to krawędzie z wagami, symbolizującymi koszt podróży daną drogą. Należy wyznaczyć więc cykl Hamiltona o najmniejszej sumie wag krawędzi należących do tego cyklu. Klasyczny sposób rozwiązania tego problemu polegający na sprawdzaniu długości każdego cyklu Hamiltona wymaga sprawdzenia wszystkich permutacji wierzchołków, co w konsekwencji prowadzi do złożoności wykładniczej (n!), praktyczne zastosowanie takiego algorytmu już dla kilkunastu miast jest więc niemożliwe. Nawet przy zastosowaniu powracania, gdy w każdym kroku aktualny koszt porównywany jest z najkrótszym wyznaczonym do tej pory cyklem, nie zmniejszy tej złożoności, choć może skrócić czas wykonania algorytmu w średnim przypadku, gdy najkrótsza trasa zostanie wyznaczona w pierwszych krokach. Jednak złożoność nadal będzie wykładnicza. Alternatywą dla przeglądu wyczerpującego jest zastosowanie strategii zachłannej w algorytmie aproksymacyjnym, dającym wprawdzie rozwiązanie przybliżone, lecz w czasie O(n2). Dzieje się tak przy założeniu, że funkcja kosztu podróży spełnia warunek trójkąta, to znaczy, że koszt podróży z miasta u do miasta v jest na pewno mniejszy niż suma kosztów podróży z miasta u do w i z w do v, czyli: c(u,v) < c(u,w) + c(v,w). W przypadku problemu komiwojażera nierówność ta jest spełniona, gdyż koszt podróży z miasta u do v jest po porostu odległością euklidesową między tymi miastami. Można wykazać, że odległość przybliżona jest co najwyżej dwa razy większa od odległości optymalnej. Aproksymacyjny algorytm wyznaczania najkrótszego cyklu Hamiltona w grafie polega na zastosowaniu algorytmu wyznaczającego minimalne drzewo rozpinające (metodą Kruskala lub Prima). Po zbudowaniu minimalnego drzewa rozpinającego należy przejść je metodą preorder (tzn. odwiedzać ojców przed synami) i zapisywać wierzchołki na liście tylko, gdy są odwiedzane po raz pierwszy. Przechodząc drzewo należy równocześnie sumować koszt przebycia krawędzi między dwoma kolejnymi wierzchołkami a na końcu dodać jeszcze koszt przebycia krawędzi między pierwszym i ostatnim wierzchołkiem na liście, ponieważ, zgodnie z założeniami problemu, komiwojażer musi powrócić do miasta, z którego wyruszył.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 16 listopada 2011 20:31
Komentarze
photo
0 # pdwd 2010-09-16 02:44
Można wspomnieć o metodzie programowania dynamicznego działającej w czasie O(2^n*n^2) i pamięci O(2^n*n)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # afrodith 2012-11-11 18:47
opisywanie ma sens gdy opieramy się na przykladach, w tym przypadku laik nie może sam zastosować algorytmu
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz

Kod antysapmowy Odśwież