Problem komiwojażera
Dlaczego komiwojażera ?
Komiwojażer ma do odwiedzenia pewna liczbe miast. Chciałby dotrzeć do każdego z nich i wrócić do miasta, z którego wyruszył. Dane sa również odległościmiedzy miastami. Jak powinien zaplanować trase podróży, aby w sumie przebył możliwie najkrótsza droge? Przez 'odległośc' miedzy miastami możemy rozumieć odległość w kilometrach, czas trwania podróży miedzy tymi miastami albo koszt takiej podróży (na przykład cene biletu lotniczego). W tym ostatnim przypadku, poszukiwanie optymalnej trasy polega na zminimalizowaniu całkowitych kosztów podróży. Tak wiec możemy poszukiwać trasy nakrótszej albo najszybszej albo najtańszej. Zakładamy przy tym, że odgłość miedzy dowolnymi dwoma miastami jest nie wieksza niż długość jakiejkolwiek drogi łaczacej te miasta, która wiedzie przez inne miasta. Założenie to tylko z pozoru wydaje sie być zawsze spełnione. Rozważmy nastepujacy przykład. Załóżmy, że interesuje nas czas trwania podróży koleja. Najszybsze połaczenie z Katowic do Białegostoku wiedzie przez Warszawe. Czas trwania tej podróży traktujemy w tym przypadku jako 'odległość' z Katowic do Białegostoku.Sformułowanie problemu.
Zbudujmy graf ważony, którego wierzchołki sa miastami. Każda pare miast połaczmy krawedziami. Każdej krawedzi nadajemy wage równa 'odległości' miedzy miastami odpowiadajacymi wierzchołkom, które sa końcami tej krawedzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczajac w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, ktory przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy wiec w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawedzi.Przykład
Na rysunku pokazano graf ważony o wierzchołkach odpowiadajacych pieciu miastom polskim. Wagami krawedzi sa odległości podane w kilometrach. Poszukujemy rozwiazania nastepujacego problemu:
Komiwojażer wyrusza z Warszawy i chce odwiedzić wszystkie pozostałe cztery miasta a nastepnie wrócić do Warszawy. Jak powinien zaplanować podróż, aby przebył możliwie najmniejsza liczbe kilometrów?Już przy pieciu miastach wszystkich możliwych tras podróży komiwojażera jest
![]()
. Można zauważyć, że przy wiekszej liczbie miast rozważanie wszystkich możliwości nie jest najlepszym pomysłem.
Dlaczego rozwiazanie tego problemu zawsze istnieje ?
Dowolny graf pełny posiada co najmniej jeden cykl Hamiltona. Ponieważ graf ma skończona liczbe wierzchołków, to w zbiorze cykli Hamiltona istnieje taki (niekoniecznie jedyny), który posiada minimalna sume wag krawedzi.Algorytmy rozwiazujace problem komiwojażera.
Istnieje wiele algorytmów rozwiazujacych ten problem. Wszystkie maja jedna podstawowa wade. Wymagaja rozważenia bardzo dużej liczby przypadków i czas ich działania może być bardzo długi. Niewielki przyrost liczby miast powoduje 'duży' wzrost ilości przypadków do rozważenia i tym samym czasu działania algorytmu. Jeden z możliwych algorytmów polega na obliczeniu całkowitej długości wszystkich istniejacych w danym grafie cykli Hamiltona. Jest to jednak bardzo skomplikowane już dla liczby miast niewiele wiekszej od pieciu. Na przykład dla 20 miast liczba cykli Hamiltona w grafie pełnym o 20 wierzchołkach wynosiczyli około
.
Algorytmy przybliżone
Czas rozwiazywania problemu komiwojażera można zmniejszyć stosujac jeden ze znanych algorytmów przybliżonych, które nie wymagaja rozważania aż tak dużej liczby przypadków. Jednak algorytmy takie nie zawsze znajduja optymalne rozwiazanie. Stworzona przez nie trasa może być znacznie 'dłuższa' od najkrótszej. Stosowanie algorytmów przybliżonych wynika z konieczności wyboru pomiedzy szybkościa znajdowania a 'jakościa' znalezionego rozwiazan. Z reguły zakłada sie, że wynik działania takiego algorytmu nie może być gorszy od optymalnego o wiecej niż pewna ustalona z góry wartość.Jak wygladałby algorytm przybliżony dla problemu gotowania ziemniaków ?
Załóżmy, że nie możemy czekać aż pół godziny do czasu gdy proces gotowania ziemniaków sie zakończy. Co wtedy robimy ? Stosujemy algorytm przybliżony !!! Możemy przecież 'niedokładnie' obrać ziemniaki lub wyjać z wody 'lekko' niedogotowane. Wynik działania takiego algorytmu nie bedzie może najsmaczniejszy ale zaoszczedzimy na czasie, który bedziemy mogli wykorzystać na przykład na poczytanie o teorii grafów. Oczywiście z góry zakładamy dopuszczalna jakość. Musimy określić, co to znaczy 'lekko' niedogotowane. Nie możemy przecież jeść ziemniaków surowych! Znajdowanie cyklu Hamiltona w dowolnym grafie. W grafie pełnym cykl Hamiltona zawsze istnieje. W dowolnym grafie może jednak nie istnieć. Problem polegajacy na znalezieniu cyklu Hamiltona jest podobnie jak problem komiwojażera 'trudny' ze wzgledu na długi czas działania znanych algorytmów. Do znalezienia takiego cyklu może wystarczyć 'troche szcześcia'. Gorzej jest kiedy cykl Hamiltona w badanym grafie nie istnieje. W takim przypadku możemy nawet być zmuszeni do sprawdzenia wszystkich możliwych permutacji zbioru wierzchołków, aby uzyskać pewność, że cykl taki nie istnieje.
[ Początek strony ] [ MiNIWykłady ]
Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej