0000082

funkcje F, której wartości F(m) »e wyznaczone przez wartości

^(k) oraz tf*j(u) dlo wierzchołków x i gołpzi u drogi ^ , Oznaczmv orzaz    zbiór dróo nroetuch

gdzie eketreaua mole być określono jako minimum (droga najkrót-oza) lub maksimum (droga najdłuższa).

Ola zastosowań praktycznych latotny jaat zbiór metod wyznaczania dróg ekctremelnych (najkrótszych 1 najdłuższych) w różnego rodzaju sieciach. Niektóre z tych metod e* przedstawione w niniejszym rozdziale w eposób usystematyzowany, wynikający

z wprowadzenia odpowiedniej, skierowanej sieci standardowej 1 etandardowogo o formułowania problomu eketremelizerji.

x^p l sieci S należy znalezc etake drogę proste _tr(x^,x^k)

Standardowe olecię skierowane dla dróg ekstremalnych jest siec S »<G,9. (l}> , gdzie C jest dlgrafem, a 1 jest funkcje rzeczywiste określone na zbiorze jego łuków. Natomiast standardowe zadanie ma nast«pujeco postać: Ole ustalonych wiorzcholków

łoczpce ta wierzchołki, dla której spełniona jest równość(10.1), gdzie

l(u)

(10.2)

chołek x^p z x

chołek *^p

Celowość wprowadzenia i ograniczania się do powyższego, stan -dardowego zadania akstremalizacjl drogi wynika z tego, że w wipkezoścl praktycznych zadań można je sprowaozlć do tej postaci standardowej, przeksztołcajec odpowiednio sieć skierowane 1 funkcje f. ha przykład: jeżeli w pierwotnym zadaniu funkcja F określona jest zarówno przez długość łuków l(u) jak 1 wartości $(*) wierzchołków, to zamieniamy każdy wierzchołek « sieci pierwotnoj dworno wierzchołkami x' 1 x" oroz łukiom łoczecym te wierzchołki, o wartość ]j(x) przyploujemy temu łukowi (ry -aunek 10.1).

Ry#.10.1

Łuki dochodzące dotychczoe do wlerzchołko x będę docho -dziły do x', o wychodzące z wlerzchołko x będę wychodziły z x". Dożęli notoaiaot pierwotno funkcjo F Jest określono Joko ilo -czyn dodotnich wartości funkcji opleanych no wlorzchołkoch i łukech toj drogi, to funkcje te możno zooienić ich logorytmori i wyrazić F Joko wymagano aumę. Mogo oczywlśclo wystąpić przy-podki, w których nie doje olę oprowadzić zadanio do równoważno* go eu zadania otendardowego. Trzoba wtedy stoaować inne metody optymalizacji. Sc to jednak przypodkl rzadkie w zastosowaniach praktycznych.

Zadanie standardowe wyznaczania prostej drogi ekotremol-nej w eieci akierowonoj możno w każdym przypadku'przedatowić w postaci odpowiedniego zadania programowanlo całkowitollczbowogo 1 rozwiązywać metodoml znanymi z teorii programowania motomoty-cznego. Wiadomo jednak, że ze wzrostem wymloru zodanla, to znaczy ze wzrostem liczby wierzchołków sieci, czas obliczeń wzrasta wykładniczo, co ogranicza praktyczne zaotoaowanlo tych metod w przypadku dużych alocl. Dlatego też istnieje dużo zapotrzebowanie no opecjolne metody teorii grofów 1 oiecl, pozwolojoce rozwiązać to zodanla nawet dla bardzo dużych aleci.

Wybór efektywnej metody wyznaczanlo drogi ekotremolnej zo-leży od wielu czynników, takich jaki cykllezność aleci w eenale dróg, znak funkcji l(u) i rodzaj ekatremolizacjl (max czy min). Dla oiecl acyklicznych w aonelo dróg, to znaczy nie zawierajcie 3