38 (543)

52. Sformułować problem komiwojażera. Podać algorytm typu „sprawdź wszystfie możliwości*⁷, oraz aiyorytm heurystycznym oparty na postępowaniu zachłannym. Jakie są złożoności tych algorytmów?

Sformułowanie problemu:

Jeśli dany jest graf G, który jest niezorientowany ( czyli bez „szczałek” ), pełny ( czyli nic ma wolnych strzelców ) i posiada koszty na swoich krawędziach, to problem marszruty komiwojażera polega na takim, znalezieniu drogi,-która odwiedzałaby wszystkie wierzchołki grafu i posiadała najmniejszy koszt. Ważne jest aby w wyniku marszruty komiwojażera powstał cykl o początku i końcu w punkcie wyjścia. No !

Dla rozwiązania tego problemu można się posłużyć ai go rytmem heurystycznym lub algorytmem typu „sprawdź wszystkie możliwości".

AJ go rytm heurystyczny polega na tym, ze w sposób zachłanny postępujemy' jeśli chodzi o wybór

wierzchołków do rozpoczęcia cykju i kolejno wybieramy wierzchołki włączając je do cyklu bądź nic

włączając, heurystyczne jest natomiast pewne „uczenie” sic podczas pracy algorytmu. Otóż pewni

jesteśmy, ze aby móc utworzyć trasę komiwojażera to włączając kolejne wierzchołki do trasy nie

możemy powodować zamknięcia cyklu i nie możemy powodować, że stopień wierzchołka po włączeniu

do cyklu ( stopień, czyli liczba kresek przy wierzchołku ) był >2 ! „Uczenie” się poiega na

zapamiętywani*] wierzchołków już włączonych i zapamiętywaniu, uraz sprawdzani u które wierzchołki

rue moea dyc włączone do cvkJu.

^ ^ ✓

Tworzenie marszruty komiwojażera przez algorytm zachłanny jest następujące:

Dana jest tabela kosztów wszystkich krawędzi. Posortować ją należy w sposób malejący. Wybieramy cc trasy kolejne krawędzie, od najmniejszej, sprawdzając warunek zamknięcia cyklu i warunek utrzymania stopnia nie większego do 2. Jeśli dana krawędź spełnia warunki zaliczamy ją i dodajemy do sumy kosz: tej kjasvędzi. Ujemną stroną działania tego algorytmu jest, to ze w najgorszym przypadku ‘oędzizmy musieli przejrzeć całą tablice kjavvęćzi grafa Gwarancją natomiast jest to, ze znajdziemy cykl komiwojażera o najmmieiszym*koszcie na pewno. Złożoność oesymistyczna tego aisorynnu jest rzędu 0(n‘).

Tworzenie marszruty komiwojażera przez algorytm „sprawdź wszystkie możliwości ", jest następujące:

procbdure k c-.t.ż wojater (G: ę r a f, va r droga: ciąg krawędzi);

var i: ir.zeger;

«»in: re&l;

be gi n

s\ir. := -cc;

żor i: = i to (r.-l) • do

rhoikćw v_;# v- , v. ,    ..

G odpowiadajęcii perzruc<»c j i d jego wierzchołków;

P ■ - Z ~ Z c t c JTTTiC Z £ C J £ C*1 2 Z t (d(p) jesz crocć, w grafie if koszt (d(p)) < nzin then droga:=d(p); iriin: = kos z t i d {p) ) ;

end id; end for;

er*.c {procedurę };

Omówienie dokładne tego algorytmu mija się z celem gdyż jest dokładnie jasne co w nim się dzieje i jak on sobie fika po grafie. Ważne jest to, że tego typu algorytm bez względu na to czy oda mu się szybko znaleźć najtańszą drogę w grafie do wszystkich wierzchołków czynie, tu i tak będzie on się wykonywał mnósrwo razy gdyż pętla for zawiera warunek -pracy aż do siini z (i>l). Bez wzgiędu na wyniki poszukiwań licznik pętli musi dobiec do (n-l)L Złożoność obliczeniowa wynosi O(rd). ( Chyba^ że należałoby to poddać kosuJtacji, proponuję kolegę J.P lub P.3.)

P.S Dla grafu o 170 wierzchołkach pętla for obróci się 7,25741561530&er-5Qó razy. ( Korzystano z kalkulatora WINDOWS, widok profesjonalny !)

3S