DSC00304 (9)
10,3. OROOl PROSTE, ■KmUlMAt.Nt W SIECIACH CYKLICZNYCH
10.3.1. Algorytm wyznaczania maksymalnego dendrytn dróg najkrótszych Dane
Siei S*(G, 0, {/}), dia której bądź 0, bądź wszystkie drogi cykliczne w niej zawarte mają nieujemną długość. Ustalony wierzchołek x*.
Procedura
Będziemy cechować wierzchołki podwójnymi cechami (F(x),g(x)) zmniejszając iteracyjnie wartości F{x).
1. Wierzchołkowi x* nadajemy cechą podwójną (0, +), a pozostałym wierzchołkom sieci cechy (oo, +).
2. Zmniejszamy iteracyjnie wartości lewych cech F(x) wierzchołków różnych od x* w następujący sposób:
Dla łuków u«(x,y) digrafu G takich, Ze
F(y)-F(x)>l«x,y»
nadajemy wartość lewej cechy wierzchołka y równą F(y) m F(x)+l«x] y»
Jako wartość prawej cechy g(y) wierzchołka y wpisujemy numer wierzchołka x, z którego nadano nową wartość lewej cechy wierzchołkowi y. Czynności opisane w tym punkcie kontynuujemy, sprawdzając wszystkie luki po kaZdej zmianie cechy, dotąd aż nie będzie można zmniejszyć lewej cechy żadnego wierzchołka.
3. Tworzymy maksymalny dendryt najkrótszych dróg prostych w ten
sposób, że do każdego wierzchołka y doprowadzamy jeden łuk od poprzednika x ■» g (y). Do dendrytu wejdą wszystkie wierzchołki o cechach różnych od (oo, +), Długości dróg *A równe ostatnim ce
chom F(x).
Uwaga I. W danej sieci S, od ustalonego wierzchołka x*, może istnieć wiele różnych dróg najkrótszych do pewnego wierzchołka x. Przedstawiony algorytm wyznacza tylko jedną z tych dróg (przypadkowo wybraną w wyniku przypadkowej kolejności zmniejszania lewych cech, wierzchołków).
Uwaga 2. Algorytm charakteryzuje się wielokrotnym, itcraćyjnytn cechowaniem wierzchołków. Jeżeli-zatem występuje w praktyce potrzeba wyznaczania tylko jednej drogi najkrótszej, łączącej ustaloną parę wierzchołków |p x*)t to nie możemy przerwać procesu cechowania z chwilą pierwszego zmniejszenia cechy F(xk). Procedura punktu 2 algorytmu musi być kontynuowana do końca i dopiero wtedy zamiast całego dendrytu możemy wyznaczyć tę jedną poszukiwaną drogę według prawych cech wierzchołków g(x).
Uwaga 3. W porównaniu z algorytmami stosowanymi dla sieci acyklicznych, opracowany algorytm ma znacznie mniejszą efektywność. Ilość niezbędnych obliczeń rośnie bardzo szybko ze wzrostem liczby wierzchołków sieci.
Wyszukiwarka
Podobne podstrony:
DSC00303 (8) ip.ł. DROPI PROSTR. BK3TKBMAŁNB W SIECIACH ACYKLICZNYCH 10.2.1. Algorytm wyznaczania ma
DSC00319 (7) 11.1.1. Algorytm wyznaczania maksymalnego przepływu Dane SieiS-<<M«},{h)>; g
10.3. Drogi proute. ekstremalne w sieciach cyklicznych • W sioci cyklicznej (zowierejęcoj drogi cykl
Dl* wyznaczenie dróg ekstremalnych w sieciach cyklicznych, nl* spełnlajęcych założeń twierdzeń 10.2
10.2.1. Algorytm wyznoczonlo dondrytu dróg najdłuższych O o n c x Siać cklorowann boz dróg cykliczny
Biochemia II W roztworach wodnych cukry proste występują głównie w postaci cyklicznej. W środowisku
DSC00300 (10) normalnym (i< *,ł^«anie łukowe zachodzi w gaz* *r. r- in.vm lub &nbs
DSC00302 (10) CpSkoucuue: XJ$ -Stbo gl t%M>3- XLCOe Ta^^l/WAAfWŁ O 1XlU0uUe- Ł^COJ^ !$f &n
DSC00304 (10) 16. Kodeks etyczny jest w stosunku do etyki zawodowej; i a), Zakresowe węższy_ b) Za k
DSC00305 (10) Kod genetyczny a AUG - metionina (kodon startowy) ! L □ U AA, U GA, UAG — ko
DSC00306 (10) Pomieszczenia, ich wyposażenie oraz sprzęt używany przy utrzymywaniu
DSC00308 (10) Odchody zwierząt oraz niezjedzone resztki pasz usuwa się z pomieszczeń gospodarsk
DSC00309 (10) 804 Jerzy Stachura • PATOLOGIA CHORÓB PRZEWODU POKARMOWEGO Typ Ho wyniosły Typ llb pła
DSC00310 (10) m POliZJA /.AKOWSKA Piosenka o wybieraniu króla
DSC00313 (10) *łj hrymilu, Ogótnw kMimi hompoirn. powieści, a kończy Mł postawieniem hipotezy. Wy. d
DSC00315 (10) 812 Jeny Stachuro • PATOLOGIA CHORÓB PRZEWODU POKARMOWEGO IE-2 - guz przekracza błonę
DSC00316 (10) Choroby jelita cienkiego 813 d) Rye. 18.17. a) Ektopowe ognisko trzu
więcej podobnych podstron