40 (507)

r i

Algorytmy zostały omówione! Za momencik jeszcze Hamiltonik! Jeśli chodzi o porównanie to ważne jest ! chyba to, 2e problem komiwojażera da się rozwiązać w czasie 0(n'j_t cykl znajdowania drogi Eulera mozc zabrać w najlepszym przypadku O(e) czasu. No, a z Hamiltonem 10 już całkiem inna sprawa ! Można próbować zaimplementować aigorytm, który będzie działał na zasadzie „wypróbuj wszystkie możliwości”. AJe tuc jest to dobre wyjście z sytuacji gdyż postępowanie takie powoduje, że musirm wykonać n!*n kjokow dla wyczerpania wszystkich możliwości. Funkcja n!*n rośnie szybciej niż dowolny wielomian, a nawet szybciej niz dowolna funkcja expotencjaIna postaci a^c, jako że: n!*n > [n/2]^ = a¹Skoro wiadomo jak szybko rośnie ta funkcja oczywiste, że dla dużych grafów ( czyli takich c

dużej liczbie wierzchołków ) czas pracy tego algorytmu rośnie do ...... -> -> -> hen.

hen...Fundamentalnym problemem jest więc znalezienie algorytmu, który' tworzyłby cykl Hamiltona u grane z czasem ograniczonym przez wielomian zmiennej „n” ( liczby wierzchołków ). Pewne podstawy dowodzą, że tak algorytm me istnieje, bowiem problem cykli Hamiltona należy do klasy problemów A^rF* zupełnych. Szczegółowe omówienie tej problematyki wykracza poza ramy tego opracowania f Istnieją jednak techniki pozwalające na znaczne ograniczenie liczby wykonywanych kroków w algorytmie - jedna z nich są algorytmy z powracaniem ( ang. backtracking ).

Implementacje algorytmu wyszukiwaniu cykli Hamiltona (zpowrucuniem ):

procedura HAMILTON(k)    { generowanie wszystkich cykli Hani 1 eona )

begin

fer ysZA(X[k-1]J do

if (k=n + l) and (y=v._:.} then

wr i c e (X ( i ] / X[2), . . . , X [ r.} , v*o)

el se

a z DO?;V) then

\r r l. 1 . _ . . .

'V l / '    1 *

CC? (y ] : = i a i s e; HAMILTON(k+ i); DO?(y]:-zrue;

ena if; and if; end for;

end; (procedurę\

becin

for v€V do

iaj: l v} 1 =true; X_;[ 1} :=v,;

DCr (vqj ! HAMILTON (2) ;

end for;

anc;

A wszystkich dociekliwych odsyłam do książki: Witold Lipski, p.L JSCombinatoryka dla programistów”, sir. 100. Tam można poczytać o tym i owym 1 dowiedzieć się jak ten algorytm działa, '00 ja ( szczerze mówiąc, opsss.. pisząc ) nie rozumiem. Ni ..uja ! ( Sorry'..)

55. Omówić przeszukiwanie grafu w głąb. Podać zastosowanie tego przeszukiwania dla problemu znajdowania składowych spójności.

Przedstawmy nnjsamwprzćd algorytm,z arrgiiska [dzpihfirst starek]:

proc&dure WGIA,3{v);    [ przeszukiwanie w głąb z wierzchołka    )

b-egin

znak[ v] .■■odwiedzony;

for us (listy incydencji[v]3 do

if znak(u) ■ niaodwiedzony then

nG1—(u) ; (1 krawadź (v_t u) wstawiacie jest do drze’wa rozpir.ł j^c = go / and if; end for;

end; (prccsdure}

40