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?
.
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
wynosi 
czyli 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