Návrh algoritmů II Ivana Cerná Fl MU Brno cerna@fi.muni.cz September 4, 2006 NAII Obsah prednášky • Zložitost, analýza zložitosti problémov a algoritmov • Dátové štruktúry - Haldy: binomiálna, Fibonacciho - Reprezentácia množín • Techniky návrhu efektívnych algoritmov - rozděl a panuj - dynamické programovanie - hladové heuristiky - branch and bound • Konkrétne algoritmy - Grafové algoritmy - Algoritmy pre prácu s retazcami nah Analýza zložitosti • Výpočtový model, zložitostné kritérium. Zložitost ako funkcia s dĺžky vstupu. • Asymptotická zložitost algoritmu • Typy zložitosti - zložitost v najlepšom prípade - zložitost v najhoršom prípade - priemerná zložitost, vážený priemer • Zložitost problému vs. zložitost algoritmu. Analýza zložitosti 2 Analýza zložitosti problému • Dolný odhad zložitosti problému • Horný odhad zložitosti problému — zložitost konkrétneho algoritmu pre problém • Zložitost problému Analýza zložitosti problémov 3 Dolný odhad zložitosti problému - techniky Informačná metóda riešenie problému v sebe obsahuje isté množstvo informácie a v každom kroku výpočtu sme schopní určit len časí tejto informácie (násobenie matíc, cesta v grafe, triedenie) Redukcia Metóda sporu Varianta A: za predpokladu, že algoritmus má zložitost menšiu než uvažovanú hranicu, vieme skonštruovat vstup, na ktorom nedá korektné riešenie. Varianta B: za predpokladu, že algoritmus nájde vždy korektné riešenie, vieme skonštruovat vstup, pre ktorý zložitost výpočtu presiahne uvažovanú hranicu. Analýza zložitosti problémov 4 Problém i-teho prvku postupnosti Vstup postupnost vzájomne rôznych celých čísel x = (#i,..., xn) a číslo i G N Úloha nájst i-ty najmenší prvok postupnosti, tj. číslo k t.ž. | tXj n tXj n ^^ tXj Zr> [ ------ L Ak i = ľ^l hovoríme o mediáne. Problém i-teho prvku postupnosti 5 __________________Dolný odhad__________________ Lema. Nech algoritmus A je algoritmus založený na porovnávaní prvkov a nech A rieši problém maximálneho prvku. Potom A musí na každom vstupe vykonat aspoň n — 1 porovnaní. Dôkaz. (Varianta A) Nech x = (xi,...,xn) je vstup dĺžky n, na ktorom A vykoná menej než n — 1 porovnaní a nech xr je maximálny prvok v x. Potom y x musí existovat prvok xp taký, že p ^ r a v priebehu výpočtu Xp nebol porovnávaný so žiadnym prvkom väčším než on sám. Existencia takého prvku plynie z počtu vykonaných porovnaní. Ak v x zmeníme hodnotu prvku xp na xr + 1, tak A určí ako maximálny prvok xr - spor. D Problém i-teho prvku postupnosti 6 Veta. Každý algoritmus založený na porovnávaní prvkov, ktorý rieši problém i-teho prvku postupnosti n prvkov pre 1 < i < [n/2], musí urobit pre každú vstupnú postupnost aspoň n + i — 2 porovnaní Dôkaz. Označme M(n, i) počet porovnaní potrebných na nájdenie z-teho prvku n prvkovej postupnosti čísel. Dokážeme, že pre každé n a každé 1 < i < [n/2] platí M (n, i)>n + i-2. Pre i > [n/2] platí M{n,i) = M{n,n — i + 1), stačí ak čísla v postupnosti prenásobíme číslom -1. Nech B je fixovaný algoritmus pre problém i-teho prvku a (x, i) jeho fixovaný vstup. Uvážme výpočet B na x až do okamihu, ked sa prvý krát porovnávajú prvky x^ a x j také, že aspoň jeden z nich už bol porovnávaný s niektorým dalším prvkom postupnosti. Problém i-teho prvku postupnosti 7 Môže nastat niekolko prípadov. Porovnávame maximá dvoch usporiadaných párov (prípad (b) na obrázku), minimá dvoch usporiadaných párov (prípad (c)), minimum jedného a maximum druhého usporiadaného páru (prípad (a)), minimum jedného páru s prvkom, ktorý ešte nebol porovnávaný (prípad (d)) a maximum jedného páru s prvkom, ktorý ešte nebol porovnávaný (prípad (e)). max O a Nó ô min (a) max x CX k * Ô -n x min (b) max O O J3 (y' min (c) O .O Cr' min (d) max r> ô (e) Problém i-teho prvku postupnosti 8 V prípade (b) sa porovnávajú maximá dvoch predošlých porovnaní. Uvážme postupnost x ktorá vznikne z x tak, že číslo Xk nahradíme číslom max, ktoré bude v x maximálnym a číslo J nahradíme číslo min, ktoré bude minimálnym. Výpočty B na x a x sú až do uvažovaného porovnania zhodné a preto výpočet B na x obsahuje 3 porovnania, v ktorých vystupujú max a min. Uvážme postupnost ž, ktorá vznikne z x odstránením max a min. z-ty prvok postupnosti x je zhodný s (i — l)-vým prvkom x. Preto B na x musí urobit aspoň tolko porovnaní prvkov rôznych od max a min ako B na x, tj. aspoň M(n — 2,i — 1). Spolu dostávame, že B na x musí urobit aspoň 3 + M (n — 2, i — 1) porovnaní, tj. M(n,i) >3 + M(n-2,i-l) (1) Problém i-teho prvku postupnosti 9 Analogický vztah platí pre situácie (a) a (c). Pre prípad (e) odvodíme M(n,i) >2 + M(n-l,i) (2) a pre prípad (d) M(n,i) >2 + M(n-l,i-l). (3) Indukciou dokážeme, že M(n, i) > n + i — 2. Tvrdenie platí pre n = 2 a i = 1, pretože M(2,1) = 1. Predpokladajme, že pre všetky m < n a r < [m/2] platí M (m, r) > m + r — 2. Ukážeme že platí pre n a všetky i < [n/2]. Problém i-teho prvku postupnosti 10 Pretože i - 1 < [n/2] - 1 = \(n - 2)/2], tak v prípade (1) M(n,i) > M(n-2,i-l) + 3 > (n — 2) + (i — 1) — 2 + 3 podlá ind.predpokladu = n+ž-2 V prípade (2) ak i < \(n- l)/2] tak M(n}i) > M(n-l,i) + 2 > (n — 1) + i — 2 + 2 podlá ind.predpokladu > n+i-2 Problém i-teho prvku postupnosti 11 Ak n je liché a i = (n + l)/2, tak n — i = \(n — l)/2] a preto M(n7i) > M(n-l,i) + 2 = M(n-l,n-i) + 2 > (n - 1) + (n - i) - 2 + 2 = 2n - i - 1 podlá ind.predpokladu = n + i — 2 pretože n = 2i — 1 V prípade (3) využijeme i — 1 < [n/2] — 1 < [(n — l)/2] M(n,i) > M(n-l,i-l) + 2 > (n-l)+i-l-2 + 2 = n+ž-2 podlá ind.predpokladu D Problém i-teho prvku postupnosti Algoritmus Select pre problém i-teho prvku Vstupom pre algoritmus Select je postupnost x = (#i,... ,xn) vzájomne rôznych čísel a číslo i G N. Algoritmus nájde i-ty prvok postupnosti x. Zložitost algoritmu je lineárna voči dĺžke postupnosti. Problém i-teho prvku postupnosti 13 1. n prvkov rozděl do \^~] skupín , z ktorých každá (s možnou výnimkou jednej skupiny) obsahuje 5 prvkov. 2. nájdi medián každej z [^] skupín 3. rekurzívně volaj Select pre postupnost mediánov nájdených v kroku 2 a hodnotu [[^]/2] (t.j. nájdi medián d z [^ mediánov nájdených v kroku 2) 4. prvky postupnosti x (okrem d) rozděl do 2 skupín skupina 1: prvky menšie než d (označme ich počet m) skupina 2: prvky väčšie než d (ich počet je n — m — 1) 5. ak m + 1 = i tak d je hladaný i-ty prvok postupnosti x ak i < m tak rekurzívně volaj Select pre skupinu 1 a číslo i ak i > m + 1 tak rekurzívně volaj Select pre skupinu 2 a číslo i + m — 1 Problém i-teho prvku postupnosti 14 Analýza zložitosti 1. O (n) 2. ö(n) (medián 5-tich prvkov nájdeme v konštantnom čase) 3. T([|]) ( T (k) je zložitost Select pre postupnost k prvkov) 4. O {n) 5. závisí od počtu prvkov menších resp. väčších než d bud T (m) alebo T(n — m — ľ). Problém i-teho prvku postupnosti 15 Odhad počtu prvkov menších a väčších než medián d Problém i-teho prvku postupnosti 16 Počet prvkov väčších než d — každá skupina, ktorá má medián aspoň d, obsahuje (aspoň) 3 prvky väčšie než d (s výnimkou skupiny obsahujúcej d a skupiny, ktorá nemusí byt úplná). Počet prvkov väčších než d je preto aspoň 1 2 n 5 3n -2 >------6 - 10 7n Následne počet prvkov menších než d je maximálne jfi + 6 Analogicky odvodíme, že počet prvkov menších než d je aspoň 3n — 6. Z toho plynie, že počet prvkov väčších než d je 10 maximálne 7n 10 + 6. V najhoršom prípade sa v bode 5. procedúra Select volá pre postupnost -jf + 6 prvkov. Problém i-teho prvku postupnosti 17 T (n) = { \ f T( [n/5]) + T(7n/10 + 6) + en pre n < 80, / je vhodná konštanta n>80 Indukciou k n dokážeme T {n) < en, kde c je vhodná konštanta 1. pre n < 80 tvrdenie platí 2. T(n) < c\n/5] + c(7n/10 + 6) + en < cn/5 + c + 7cn/10 + 6c + en = 9cn/10 + 7c + en = en + (—cn/10 + 7c + en) Ak zvolíme c tak, aby — cn/lO+7+en < 0, dostávame T(ri) < en, Problém i-teho prvku postupnosti 18 Amortizovaná zložitost Technika umožňujúca presnejšie určenie zložitosti. Uvažujme výpočet, v ktorom sa postupne vykonajú operácie L I ±l') ' ' ' 5 ±n- Klasický prístup Analyzujeme zložitost každej operácie. Výsledná zložitost je súčtom zložitostí jednotlivých operácií. Technika amortizácie Analyzujeme postupnost ako celok. Používajú sa metódy • zoskupení • účtov • potenciálových funkcií Amortizovaná zložitost 19 Príklady Zásobník Operácie Push(5, x), Pop(S'), Multipop^, k) (vyberie k prvkov z S resp. vyprázdni zásobník ak | S |< k). Uvažujme postupnost n operácií, každá operácia je Pop, Push alebo Multipop. Push a Pop majú zložitost 1. V postupnosti n operácií má Multipop v najhoršom prípade zložitost n. Preto celá postupnost má v najhoršom prípade zložitost n2. Amortizovaná zložitost 20 Binárne počítadlo fc-bitové počítadlo implementované ako pole A[0...k — 1]. 7 -j Hodnota počítadla je x = X)i=o ^[^]2*. Iniciálna hodnota počítadla je 0. INC(A) while i < fc — 1 A A [i] = 1 do A[i] ^ 0; i <- i + 1 od if i < fc - 1 then A [i] <- 1 fi Zložitost operácie Inc je počet preklopených bitov v A, tj. maximálne k. Zložitost postupnosti n (n < 2fc+1) operácií Inc je n • k. Amortizovaná zložitost 21 Metóda zoskupení Operácie rozdelíme do skupín a analyzujeme zložitost celej skupiny operácii súčasne. Zásobník Skupina 1 — operácie Push, súčet ich zložitostí nepresiahne n Skupina 2 — operácie Pop a Multipop, súčet ich zložitostí (= počet prvkov vybraných zo zásobníka) nemôže byt väčší než počet vykonaných operácií Push (= počet prvkov vložených do zásobníka). Zložitost celej skupiny preto nepresiahne n. Celá postupnost má v najhoršom prípade zložitost 2n. Amortizovaná zložitost - metóda zoskupení 22 Binárne počítadlo Skupina 1 — preklopenie A[0], pri každom volaní Inc. Celková zložitost je n. Skupina 2 — preklopenie A[l], pri každom druhom volaní Inc. Celková zložitost je n L2J Skupina 3 — preklopenie A[2], pri každom štvrtom volaní Inc Celková zložitost je [f ■ Počet skupín je k — 1 Postupnost n operácii Inc má zložitost Yli=o ln/^l\ < 2n. Amortizovaná zložitost - metóda zoskupení 23 Metóda účtov Každej operácii priradíme kredit (číslo), ktoré môže byt rôzne od jej skutočnej ceny (zložitosti). Pri realizácii operácie zaplatíme jej cenu kreditmi podlá nasledovných pravidiel: - ak cena operácie < kredit operácie, tak za operáciu zaplatíme tolko kreditov, aká je jej cena, a zvyšné kredity uložíme na účet, - ak cena operácie > kredit operácie, tak kredity potrebné na zaplatenie operácie vezmeme z účtu. Počiatočný stav účtu je 0 kreditov. Ak počas celého výpočtu je počet kreditov na účte nezáporný, tak súčet kreditov vykonaných operácií je > cena vykonaných operácií. Amortizovaná zložitosť - metóda účtov 24 Varianta Kredity priradíme objektom dátovej štruktúry, nad ktorou sa operácie realizujú. Cena operácie sa zaplatí kreditmi objektov, s ktorými operácia manipuluje. Terminológia Amortizovana cena operácie = počet kreditov priradených operácii. Amortizovana zložitosť - metóda účtov 25 Zásobník Operácia Cena Kredity Push Pop multipop 1 1 min{fc, \S\} 2 0 0 v okamihu, ked objekt vkladáme do zásobníka, si "předplatíme" jeho výber Operáciu Push zaplatíme 1 kreditom, 1 kredit dáme na účet. Operácie Pop a Multipop zaplatíme kreditmi z účtu. Ľahko overíme, že počas celého výpočtu platí invariant počet kreditov na účte je rovný počtu prvkov v zásobníku. Z toho plynie, že zostatok na účte nikdy neklesne pod 0. Celková zložitost postunosti n operácií je < súčet kreditov vykonaných operácií < 2n. Amortizovaná zložitost - metóda účtov 26 Binárne počítadlo Operácia Cena Kredity Nastavenie bitu na 1 Nastavenie bitu na 0 1 1 2 0 Operáciu nastavenie hodnoty premennej A[i] na 1 zaplatíme jedným kreditom, 1 kredit dáme na účet premennej A Nastavenie hodnoty A účte premenná A[i\. na 0 zaplatíme kreditom, ktorý má na Počas celého výpočtu platí invariant ak hodnota premennej A[i] je 1, tak premenná má na svojom účte 1 kredit. Počas operácie Inc sa mení hodnota premennej na 1 maximálne raz. Preto amortizovaná cena operácie Inc je 2 a cena zložitosti postupnosti n operácií Inc je 2n. Amortizovaná zložitosť - metóda účtov 27 Metóda potenciálovej funkcie Operácie sa realizujú nad dátovou štruktúrou. Potenciálová funkcia $ priradí každej hodnote (obsahu) dátovej štruktúry číslo. Uvažujme postupnost n operácií, nech skutočná cena i-tej operácie v tejto postupnosti je q. Označme D0 iniciálnu hodnotu dátovej štruktúry a Di jej hodnotu po vykonaní i-tej operácie. Definujeme amortizovanú cenu i-tej operácie, q, predpisom či = a + $(A) - $(A-i) Amortizovaná zložitosť - metóda potenciálovej funkcie 28 Súčet amortizovaných cien operácií je n Ec^ =Eľ=i(ci + *(A)-*(A-i)) i=l = Eti^ + HDn)-HD0) Za predpokladu $(£>n) > $(A)) platí Eľ=i £ > £ľ=i c* t.j. súčet amortizovaných cien operácií je horným odhadom pre zložitost celej postupnosti operácií. Aby sme zabezpečili platnost podmienky $(Dn) > $(üo), definujeme potenciálovú funkciu tak, aby pre každú hodnotu D dátovej štruktúry platilo, že jej potenciál &(D) je aspoň tak velký, ako potenciál počiatočnej hodnoty Dq dátovej štruktúry. Amortizovaná zložitost - metóda potenciálovej funkcie 29 Zásobník Dátová štruktúre je zásobník. Potenciálová funkcia = počet prvkov v zásobníku. Amortizovaná cena i-tej operácie - rozlíšime podlá typu operácie Push Pop Ci Ci MULTIPOP Či = 1 + (|S| + 1)-|S| =2 1 + |S|-(|S| + 1) = 0 k + (\S\ - k) - \S\ =0 ak \S\ > k S +0-\S\ =0 ak S $(A))- Preto zložitost celej postupnosti je Yľi=i c* — 5^ľ=i ^* — ^n Amortizovaná zložitost - metóda potenciálovej funkcie 30 Binárne počítadlo Dátová štruktúra je pole A[0...k — 1], potenciálová funkcia je počet 1 v poli. Označme bi počet 1 v počítadle A[0... k — 1] po vykonaní i-tej operácie Inc. Cena i-tej operácie Inc je U + l, kde ti je počet bitov preklopených z 1 na 0. Amortizovaná cena i-tej operácie je či = U + l + (bi-! -U + l)- bi-ľ = 2. Potenciálová funkcia je vždy nezáporná, potenciálová funkcia pre počiatočnú hodnotu póla je 0. Zložitost postupnosti n operácií Inc je Yľi=i ci — 5ľľ=i ^ — ^n- Amortizovaná zložitost - metóda potenciálovej funkcie 31 Dynamické tabulky Do tabulky ukladáme položky, dopredu nie je známy počet položiek a teda ani velkost tabulky, ktorú máme alokovat. Dynamické riešenie: pri naplnení tabulky alokujeme novú, väčšiu tabulku a položky do nej presunieme. Podobne, ak po odobraní položiek je tabulka nenaplnená, alokujeme novú, menšiu tabulku a položky do nej presunieme. Podporované operácie sú Table Insert, Table Delete. Pre neprázdnu tabulku T definujeme faktor cx(T) ako pomer počtu položiek uložených v tabulke a velkosti tabulky. Prázdna tabulka (tj. tabulka, ktorá nemá žiadne sloty) má velkost 0 a jej faktor je 1. Amortizovaná zložitosť - metóda potenciálovej funkcie 32 Na začiatku alokujeme prázdnu tabulku. Do tabulky, ktorej faktor je < 1, môžeme vložit novú položku. Ak chceme vložit novu položku do tabulky s faktorom 1, alokujeme najprv novú tabulku s dvojnásobnou velkostou, položky starej tabulku do nej presunieme a vložíme novú položku. Naopak, z tabulky, ktorej faktor je > 1/2 môžeme položky odoberat. Ak je faktor 1/2, tak alokujeme novú tabulku polovičnej velkosti, prvky starej tabulky do nej presunieme a položku odoberieme. Cena jednej operácie Table Insert alebo Table Delete je v najhoršom prípade rovná počtu prvkov, ktoré presúvame do novej tabulky. Cena postupnosti n operácií typu Table Insert a Table Delete je preto v najhoršom prípade ö(n2). Amortizovaná zložitosť - metóda potenciálovej funkcie 33 Analyzujme amortizovanu zložitost postupnosti n operácií Table Insert. Metódou zoskupení Skutočná cena i-tej operácie je i ak i je mocninou 2 a je 1 inak. Prvú skupinu tvoria operácie, ktorých skutočná cena je 1. Druhú skupinu tvoria operácie, pri ktorých sa alokuje nová tabulka. n 1=1 < n + 2n = 3n Amortizovaná zložitost - metóda potenciálovej funkcie 34 Metódou kreditov Každej operácii priradíme 3 kredity. Jeden kredit zaplatí vloženie položky do tabulky, 1 kredit dostane na svoj účet položka, ktorú sme práve vložili do tabulky a 1 kredit dáme na účet položke, ktorá je už v tabulke a nemá na svojom účte žiaden kredit. Predpokladajme, že sme práve alokovali novú tabulku velkosti m a žiadna z m/2 položiek tabulky nemá na svojom účte žiaden kredit. Než sa tabulka znovu naplní, tak každá z týchto m/2 položiek ako aj každá z m/2 nových položiek bude mat na svojom účte 1 kredit. Tieto kredity sa použijú na presun položiek do novej tabulky. Amortizovaná zložitosť - metóda potenciálovej funkcie 35 Metódou potenciálovej funkcie Označme num[T] počet položiek tabulky a size[T] veikost tabuiky. Definujeme potenciálovú funkciu predpisom $(T) = 2 • num[T] — size[T]. Ak i nie je mocninou 2, tak amortizovaná cena i-tej operácie je či = a + $i- $í_i = 1 + (2num[Ti\ — size\Tj\) — (2num[Ti_i\ — size[Ti_i\) = 1 + 2 = 3 Pre i rovné mocnine 2 je amortizovaná cena či = a + $i- $í_i = num[Ti] + (2num[Ti\ — size\Tj\) — (2num[Ti_i\ — size[Ti_i\) = 3 Amortizovaná zložitosť - metóda potenciálovej funkcie 36 Zložitost postupnosti n operácií typu Table Insert a Table Delete je 6(n2). Vysvetlite prečo. Navrhnite lepšiu stratégiu tak, aby amortizovana cena postupnosti n operácií typu Table Insert a Table Delete bola lineárna. Amortizovana zložitost - metóda potenciálovej funkcie 37 Dátové štruktúry Reprezentácia dynamickej množiny objektov spolu s operáciami nad touto množinou objektov. • zásobník, fronta (Push, Pop) • spájané zoznamy jednosmerné a dvojsmerné (Search, Insert, Delete) • slovníky (Search, Insert, Delete) • vyhladávacie stromy (+ Minimum, Maximum, Predecessor, Sucessor) - obecný vyhladávací strom - vyvážené vyhladávacie stromy: AVL, bielo-čierne stromy, B-stromy, 2-3 stromy Dátové štruktúry 38 • haldy (Insert, Delete, - (binárna) halda - binomiálna halda - Fibonacciho halda • reprezentácia dijunktných - spájané zoznamy - UNION-FIND štruktúra Dátové štruktúry m) (Insert, Find, UNION) 39 Haldy Dátové štruktúry pre reprezentáciu množiny prvkov, nad ktorými je definované usporiadanie. Podporované operácie: Make Heap() - vytvorí prázdnu haldu Insert(íí, x) - do haldy H vloží prvok x Minimum(íí) - nájde minimálny prvok v H Extract Min(íí) - z haldy H odstráni minimálny prvok Delete(íí, x) - z haldy H odstráni prvok x Union(íÍi, H2) - vytvorí novú haldu zjednotením háld H\,H2 Decrease Key(íí, x, fc) - zníži hodnotu vrcholu xnafc Haldy 40 Halda - strom, každý vrchol stromu obsahuje klúč = prvok reprezentovanej množiny. Pre každý podstrom haldy platí, že klúč koreňa je menší alebo rovný než klúče všetkých jeho následníkov. Binárna Binomiálna Fibonacciho Operácia halda halda halda Make-Heap 6(1) 0(1) 0(1) Minimum 6(1) 8 (log n) 0(1) Insert 8 (log n) 8(1) * 0(1) Union 8(n) 8 (log n) 0(1) Extract-Min 8 (log n) 8 (log n) 0(logn) * Delete 8 (log n) 8 (log n) 0(logn) * Decrease-Key 8 (log n) 8 (log n) 0(1) * * amortizovaná zložitosť Haldy 41 Binomiálna halda Binomialny strom Bk -je definovaný rekurzívně: • binomialny strom Bq obsahuje jediný vrchol, • binomialny strom B^ pozostáva z dvoch binomialnych stromov Bk-i, ktoré sú spojené tak, že koreň jedného z nich je najlavejším synom koreňa druhého z nich. O Bn Bi Binomiálna halda 42 o o c c / ) i o o p o o o c ) c D B0 B1 B2 B Binomiálna halda O Ô B 43 Binomialna halda 44 Vlastnosti binomiálneho stromu B k ,fc • Bk má 2^ vrcholov, jeho hĺbka je k • počet vrcholov hĺbky i je (J • koreň stromu B^ má stupeň k • synovia koreňa zlava doprava sú korene stromov ß^-i? • • • A) Dôkaz: indukciou vzhladom k hodnote k. Stupeň vrchola je počet jeho synov. Stupeň stromu je stupeň jeho koreňa. Binomiálna halda 45 Binomiálna halda Binomiálna halda je les H binomiálnych stromov, kde • každý binomiálny strom v Jí má vlastnost haldy tj. prvok uložený vo vrchole je väčší alebo rovný prvku, ktorý je uložený v jeho otcovi, • pre lubovolné k existuje v H maximálne jeden strom stupňa k • korene stromov tvoria zoznam usporiadaný vzostupne podlá stupňa koreňov ^ ® © <šfé>é Binomiálna halda 46 Vlastnosti binomialnej haldy halda s n vrcholmi má maximálne [log n] stromov schematicky môžeme haldu o n prvkoch vyjádřit pomocou binárneho zápisu čísla n Binomiálna halda 47 Operácie nad binomiálnou haldou Vrchol stromu je záznam s údajmi p - ukazatel na otca key - klúč degree - počet synov sibling - ukazatel na pravého brata child - ukazatel na najlavejšieho syna Premenná head[H] - ukazatel na strom s minimálnym stupňom Binomiálna halda 11 / / sibling child sibling 11 / / Binomiálna halda 49 Nájdenie minimálneho prvku haldy Minimálny prvok každého stromu je uložený v koreni. Preto stačí prejst koreňový zoznam. Zložitost č)(logn) BH_Minimum(íí) y ^ Nil x <— head[H] min <— oo while x ^ Nil do if key [x] < min then min <— key [x]; y <— x f i x <— sibling[x] od return y Binomiálna halda 50 Zjednotenie dvoch háld 1. Koreňové zoznamy háld H\ a H2 spojíme tak, že stupne koreňov tvoria neklesajúcu postupnost. Zložitost č) (logni + log712) -00—-p - I s^\ 000 I o ■0000 66 Binomiálna halda 51 2. Prechádzame vytvorený koreňový zoznam. Ak narazíme na dva stromy s rovnakým stupňom koreňa, spojíme ich (analógia sčitovania binárnych čísel). Zložitost č)(logn) 3) k k k+1 Bu Bu Bu k k k k+1 Binomiálna halda 52 BH_UNION(iři,iř2) i H <- Make_BH_Heap() 2 head[H] <- BH_HEAP_MERGE(/ři,/ř2) 3 if head[H] = Nil then return H fi 4 prev-X <— Nil 5 x <— head[H] 6 next-X <— sibling[x] 7 while next-x ^ Nil do 8 if (degree[x] ^ degree[next-x]) V 9 (sibling[next-x] ^ Nil A io degree[sibling[next-x]] = degree[x]) u then prev-X <— x; x <— next-X i2 else if key [x] < key[next-x] i3 then sibling[x] <— sibling[next-X u BH_LiNK(nexr_x, x) Binomiálna halda 15 else if prev-x = Nil 16 then head[H] <— next-X 17 else sibling[prev-x] <— next-X f i 18 BH_Link(x, next-x) 19 x <— next-X fi 20 fi 2i next-X <- - sibling[x] 22 od 23 return H BK-LiNK(y,z) i p[y] <- z 2 sibling[y] <— child[z] 3 child[z] <— y 4 degree[z] <— degree[z] + 1 Binomiálna halda 54 BH_Heap_Merge(ÍÍi, H2) spojí zoznam koreňov haldy H\ a haldy H2 dojeného zoznamu tak, že korene sú usporiadané podlá stupňa (ako v algoritme triedenia spájaním, Mergesort) Binomiálna halda 55 Vloženie nového prvku do haldy Operácia BH_Insert pripojí k halde H nový vrchol x. Predpokladáme, že key[x] je vkladaný prvok a že pre ostatné parametre platí p[x] = Nil, child[x] = Nil, sibling[x] = Nil, a degree[x] = 0. Zložitost 0(l) + 0(logn) BH_Insert(íí, x) i Hf <- Make_BH_Heap() 2 head[H'\ <— x Binomiálna halda 56 Odstránenie minimálneho prvku z haldy Nájdeme koreň k s minimálnym prvkom. Odstránime k z koreňového zoznamu. Z detí koreňa k vytvoríme novú haldu a pripojíme ju k pôvodnej halde. Zložitost č)(log n) BH_Extract_Min(íí) i nech x je koreň s minimálnym klúčom; odstráň x z H 2 Hf <- Make_BH_Heap() 3 obrat poradie, v ktorom sú spojené deti vrchola x 4 nech /zeadfií7] ukazuj e na tento zoznam 5 H ^BHJJmoN(H,Hf) Binomiálna halda 57 UNION Binomiálna halda 58 Zníženie hodnoty klúča Parametrom operácie je vrchol x a číslo k. Operácia zmení hodnotu klúča uloženého v x na k za predpokladu, že k je menšie než pôvodný klúč uložený v x. BH_Decrease_Key zníži hodnotu klúča a vrchol presúva smerom nahor (ako v binárnej halde). Zložitost ö(logn). BH_Decrease_Key(íí, x, k) i if k > key[x] then chyba, nový klúč je väčší než pôvodný f i 2 key[x] <— k; y <— x; z <— p[y] 3 while z t^ Nil A {key[y\ < key[z\) 4 do exchange key [y] ^ key [z] 5 y <- z 6 z <— p[y] od Binomiálna halda 59 Odstránenie prvku z haldy Vrcholu, ktorý chceme odstranit, znížime pomocou BH_Decrease_Key hodnotu klúča na —oo a operáciou BH_Extract_Min ho odstránime z haldy. Zložitost ö(logn). BH_Delete(ü» i BH_Decrease_Key(íí, x,-oo) 2 BH_Extract_Min(íí) Binomiálna halda 60 Binárna Binomiálna Fibonacciho Operácia halda halda halda Make-Heap 6(1) 6(1) 6(1) Minimum 6(1) 8 (log n) 6(1) Insert 8 (log n) 8(1) * 6(1) Union e(n) 8 (log n) 6(1) Extract-Min 8 (log n) 8 (log n) 0(logn) * Delete 8 (log n) 8 (log n) 0(logn) * Decrease-Key 8 (log n) 8 (log n) 0(1) * Binomiálna halda 61 Amortizovaná cena operácií nad binomiálnou hladou Invariant: každý strom v halde má na svojom účte 1 kredit. Amortizovaná cena operácie BH_Insert je 0(1). 1 kredit zaplatí vytvorenie nového vrcholu, 1 kredit dáme na účet novovytvorenému stromu. Spájanie stromov zaplatíme kreditmi stromov, ktoré spájame. Amortizovaná cena operácie BH_Union je č) (log n). Kredity použijeme na zaplatenie spájania koreňových zoznamov háld. Spájanie stromov zaplatíme kreditmi stromov, ktoré spájame. Amortizovaná cena operácie BH_Extract_Min je ö(logn). Kredity vložíme na účet stromov, ktoré vznikli odstránením koreňa s minimálnym prvkom. Spájanie stromov zaplatíme kreditmi stromov, ktoré spájame. Binomiálna halda 62 Fibonacciho halda Je modifikáciou binomiálnej haldy. Dovoluje efektívnejšiu realizáciu operácií Union, Minimum a Decrease_Key; zároveň nezhoršuje amortizovanú zložitost ostatných operácií. Základné princípy • zavedenie ukazatela na minimálny prvok • štruktúra môže obsahovat viac stromov rovnakého stupňa • stromy nie sú binomiálne (pri súčasnom zachovaní ich vyváženosti) • operácie, ktoré nie sú potrebné, odkladáme a vykonáme ich až ked je to nevyhnutné. Konkrétne, pri Union a Insert realizujeme jednoduché spojenie koreňových zoznamov (konštantná zložitost). Stromy spájame až pri volaní operácie Decrease_Key. Fibonacciho halda 63 r®=®; 3Eiä=I)i QlP ^ Fibonacciho halda 64 Vrchol stromu je záznam s údajmi p - ukazatel na otca key - klúč degree - počet synov mark - binárny príznak left - ukazatel na lavého brata right - ukazatel na pravého brata child - ukazatel na syna Premenné min H - ukazatel na minimálny prvok Fibonacciho haldy n H] - aktuálny počet prvkov v halde H Označenie D (n) - maximálny možný stupeň vrchola vo Fibonacciho halde s n prvkami m(H) - počet stromov v halde H Fibonacciho halda 65 Operácie Vytvorenie prázdnej haldy Make_Fib_Heap() vytvorí prázdnu haldu H, head[H] = nil skutočná cena = 1 amortizovaná cena = 0(1) (2 kredity na účet vytvoreného stromu) Invariant výpočtu: každý strom má na svojom účte 2 kredity Nájdenie minimálneho prvku Fib_Minimum(H) udržujeme ukazatel min[H] na koreň obsahujúci minimálny prvok skutočná = amortizovaná cena = 1 Fibonacciho halda 66 Vloženie nového prvú do haldy Operácia Fib_Insert pripojí k halde H nový vrchol x. Predpokladáme, že key[x] je vkladaný prvok a že pre ostatné parametre platí P x = Nil, child[x] = Nil, left[x] = right[x] = x, mark[x] = false a degree[x] = 0. Aktualizujeme hodnoty min[H] a n[H . skutočná cena = 0(1) amortizovaná cena = 0(1) (2 kredity na účet vytvoreného stromu) Fib_Insert(íí, x) i spoj zoznam x so zoznamom H 2 if min [H] = nil V key [x] < key[min[H 3 then minlH] <— x f i 4 n H] n ~H] + 1 Fibonacciho halda 67 Zjednotenie dvoch háld - zoznamy Hi a H2 spojíme do jedného - aktualizujeme hodnoty min[H] a n[H skutočná = amortizovaná cena = 0(1) Fib_Union(íÍi, H2) 1 H <- Make_Fib_Heap() 2 spoj zoznamy Hi a H2 do zoznamu H 3 if (min[Hi\ = nil) V {min[H^[ 7^ nil A min[H2 4 then min[H] <— min[H2 5 else min\H] <— min\Hi\ f i 6 n H n Hi +nH2 return H Fibonacciho halda Union mintH^ minthy H2\4>------0 H (D-© © ® Fibonacciho halda 69 Odstránenie minimálneho prvku z haldy - všetkých synov koreňa z obsahujúceho minimálny prvok pripojí- me do koreňového zoznamu H - odstránime z - voláme Consolidate a upravíme haldu tak, aby neobsahovala dva stromy rovnakého stupňa - v upravenej halde prechádzame koreňový zoznam a hladáme nový minimálny prvok Fibonacciho halda 70 s Úprava haldy ( Consolidate) využíva pomocné pole rozmerov D(n[H\) prechádzame koreňový zoznam H, ukazatel na každý koreň x uložíme do A[degree(x)]. Ak je hodnota A[degree(x)] ^ Nil, tak prevedieme spojenie (Link) príslušných stromov a ukazatel na výsledný strom uložíme do A[degree(x) + 1]. V prípade potreby spájanie opakujeme. na základe informácii uložených v A vytvoríme nový koreňový zoznam. Fibonacciho halda 71 min[H] 0 12 3 Fibonacciho halda 21----118----52----38----17 0 12 3 21----18----52----38----17 AV ^30 , w,x 72 0 12 3 0 12 3 7----21----18----52----38 Fibonacciho halda 0 12 3 /_ ]/_ u v 0 1 2 3 A / / / " 21 ----118-----{52j----38 73 0 12 3 21 ----118-----{52)----38 Fibonacciho halda 0 12 3 74 Fib_Exctract_Min(íí) i z <— min[H 2 if z ^ NIL 3 then for pre každého syna x vrcholu z do 4 8 9 10 u n 12 f i i3 return z pridaj x do koreňového zoznamu haldy H p[x] <— NIL Od odstraň z zo zoznamu H if z = right[z] then min[H] <— NIL z bol jediný vrchol haldy else min[H] <— right[z] Consolidate(íí) fi H] ^- n[H] - 1 Fibonacciho halda 75 Consolidate(íí) i for i ^0 to D(n[H]) do 2 A[i] <— NIL od 3 for pre každý vrchol w v koreňovom zozname haldy H do 4 x <— w 5 d <— degree[x] 6 while A[d] ^ nil do j y <- A[d] s if key [x] > key [y] 9 then exchange x <-» y f i io Fib_Link(íí, ?/,#) u A [d] <— NIL i2 d <— d + 1 od i3 A[d] <— x u od Fibonacciho halda 76 15 min[H] <— nil i6 for i <— 0 to D(n[H]) do if A[i] 7^ NIL then pridaj A [i] do koreňového zoznamu haldy H if min[H] = nil V fcey[A[i]] < key[min[H]] 17 18 19 20 21 22 23 fi od then min\H m fi Fib_Link(íí, ?/,#) i odstráň y z koreňového zoznamu haldy ií 2 sprav y synom x, zvýš degree[x] 3 mark[y] <— FALSE Fibonacciho halda 77 Amortizovaná zložitost operácie Fib_Exctract_Min(ií) Operácii priradíme ö(D(n[H])) kreditov. D (n) - maximálny možný stupeň vrchola vo Fibonacciho halde s n prvkami m(H) - počet stromov v halde H FIB_EXCTRACT_MIN - pripojenie synov vrcholu z do koreňového zoznamu ~ konštantná zložitost, tj. 0(1) kreditov - každý nový strom haldy dostane na svoj účet 2 kredity, tj. spolu maximálne D(n[H\) kreditov Fibonacciho halda 78 Consolidate - inicializácia póla A « D(n[H]) + 1 kreditov - vkladanie stromov do póla A a spájanie stromov (cyklus 1-14): označme m počet stromov v halde, ktorú máme upravit. Každý strom má na svojom účte 2 kredity. Počas cyklus vložíme do póla A m stromov a vykonáme k spájaní. Každé spájanie zníži počet stromov o 1 a preto k < m. Na zaplatenie všetkých operácii preto postačujú kredity, ktoré majú na svojich účtoch stromy. - vytvorenie nového koreňového zoznamu na základe informácií uložených v A a hladanie nového minima (cyklus 16-23) ~ D(n[H]) + l kreditov - každému stromu v zrekonštruovanej halde dáme na účet 2 kredity tj. spolu maximálne D(n[H\) + 1 kreditov Fibonacciho halda 79 Zníženie hodnoty klúča Ak sa znížením klúča vo vrchole x poruší vlastnost haldy, tak namiesto výmeny vrcholov (ako v binárnej a binomiálnej halde) odrežeme celý podstrom s koreňom x a urobíme ho novým stromom haldy, tj. pripojíme ho do koreňového zoznamu (Cut). V dôsledku prerezávania sa môže stat, že strom vysokého stupňa má velmi málo vrcholov a následne halda obsahuje velmi vela stromov. Preto pri opakovanom odřezávaní podstromov zároveň znižujeme stupeň stromu. Konkrétne: ak niektorému vrcholu odrežeme druhého syna (príznak mark), tak odrežeme aj tento vrchol od jeho otca a v prípade potreby postupujeme s odřezáváním smerom ku koreňu (Cascading.Cut) Fibonacciho halda 80 8^2 Fibonacciho halda 8^2 10 Fibonacciho halda O 82 8^2 10 Fibonacciho halda 1 83 8^2 (10) Fibonacciho halda 1 84 8^2 Í)-f7 min Fibonacciho halda 1 © 85 8^2 D-CD mm Fibonacciho halda Fib_Decrease_Key(íí, x, k) i if k > key[x] then chyba, nový klúč je väčší než pôvodný f i 2 key [x] <— k 3 y <— p[x 4 if y t^ NIL A key [x] < key [y] 5 then C\JT(H,x,y) 6 CASCADING_CUT(ií, y) 7Í\ 8 if key [x] < key[min[H 9 then min[H] <— x io fi Fibonacciho halda 87 CuT(H,x,y) i odstraň x zo zoznamu detí vrchola y; zníž degree[y] 2 pridaj x do koreňového zoznamu haldy H 3 p[x] <— NIL 4 mark[x] <— FALSE CASCADING_CUT(ií, y) i z <- p[y] 2 if z ^ NIL 3 then if mark[y] = false then mark[y] <— true 4 else C\JT(H,y,z) 5 Cascading_Cut(íí, z) 6 f! 7Í\ Fibonacciho halda 88 Amortizovaná zložitost operácie Fib_Decrease_Key Na zaplatenie operácie postačuje 6 kreditov - ak za neodrezáva žiaden vrchol, kredity sa nevyužijú - ak sa odreže x od y 1 kredit zaplatí odrezanie 2 kredity dostane na účet strom s koreňom x (zachovanie invariantu výpočtu) 3 kredity dostane na účet vrchol y - v okamihu, ked potrebujeme odřezat y od jeho otca, má y na svojom účte 6 kreditov, ktorými zaplatíme toto odrezanie Fibonacciho halda 89 Odhad hodnoty D (n) Lema. Ak strom vo Fibonacciho halde má koreň stupňa k, tak má aspoň 2^/^ vrcholov. Dôkaz. Fixujme časový okamih. Nech x je lubovolný vrchol haldy a ž/i,...,ž/m jeho synovia v poradí, v akom boli pripájaní k x. Uvážme vrchol ž/í- Vo chvíli, ked sa stal synom x, tak x mal aspoň synov ž/i, • • • ,ž/i-i- Pri spájaní stromov vždy spájame stromy rovnakého stupňa, preto vo chvíli ked sa ž/í stal synom x mal aj ž/í aspoň i — 1 synov. Odvtedy sme mu maximálne 1 syna odrezali. Preto vo fixovanom okamihu má ž/í stupeň aspoň i — 2. Ukázali sme, že vo Fibonacciho halde má i-ty syn každého vrchola aspoň i —2 synov. Označme fi minimálny počet vrcholov v strome, ktorý má uvedenú vlastnost a jeho stupeň je i. Fibonacciho halda 90 i 1 Platí /o — 1» /l — 2, Ín+2 — /n+1 + /n- Postupnost (/i) má kladné členy, preto je rastúca a fk > 2fk-2 Dosadením pre k liché h > 2 • fk_2 > 2 • 2 • /fc_4 > ... > 2Lfe/2j . A = 2ľfe/2l. Podobne pre k sudé. D Pozn.: presnejší odhad je /& > ((1 + \/5)/2)fc Fibonacciho halda 91 Dôsledok. Fibonacciho halda s n vrcholmi má nanajvýš 2 log n stromov, tj. D(ri) < 2 log n. Dôsledok. Amortizovaná zložitost operac/7 Fib_Extract_Min a Fib_Delete v postupnosti n operáciií nad Fibonacciho haldou je O (log n). Poznámka: Pod Fibonacciho haldou rozumieme každú štruktúru, ktorá vznikne z prázdnej haldy (tj. haldy vytvorenej operáciou MakE-FiB-HeapJ aplikáciou uvedených operácií. Fibonacciho halda 92 Dátové štruktúry pre disjunktně množiny Dátové štruktúry pre reprezentáciu disjunktných množín, z ktorých každá má svojho jednoznačne určeného reprezentanta. Podporované operácie: Make_Set(x) - vytvorí množinu obsahujúcu prvok x Union(íÍi, H2) - vytvorí novú množinu zjednotením množín H\ a #2 Find_Set(x) - nájde reprezentanta množiny obsahujúcej prvok x. Operácia Find_Set dovoluje efektívne testovat, či dva prvky patria do tej istej množiny. Implementácia pomocou spájaných zoznamov a lesa stromov. Disjunktně množiny 93 Spájané zoznamy Množinu reprezentujeme ako spájaný zoznam, prvý prvok zoznamu je reprezentantom množiny. Každý prvok zoznamu obsahuje uka-zatel na nasledujúci prvok zoznamu a na reprezentanta. Reprezentant obsahuje údaj o kardinalite množiny. E- ^ B- *n= c M 0 ^ Qt \fT- P 0 M 0 C rank[y] then p[y] <— x 2 else p[x] <— y 3 if rank[x] = rank[y] 4 then rank[y] <— rank[y] + 1 f i f i Find_Set(x) i if x ^ p[x] then p[x] <— Find_Set(p[x]) f i 2 return p[x Disjunktně množiny 101 Lema. Pri reprezentácii množín stromami je zložitost postupnosti obsahujúcej m operácií Union a Find_Set a n operácií Make_Set rovná ö(ma{n)). Definícia funkcie oi{n) Pre prirodzené čísla k > 0 a j > 1 definujeme funkciu Ak(j) AM = < j + l Afe_i(Afe_i(...Afe_iy(j))) k j+l krát pre k = 0 pre k > 1 A1{j)=Ao(A0{...A0(j)..))=2j + l A2(j) = A1(A1(... A1(j)..)) = v+Hj +1) -A3(l) = 2047 At(l) = 16512 > 1080 -1 Disjunktně množiny 102 Funkcia a(n) je inverzná k funkcii Ak(n) def a(n) = min{& Afc(l) > n} o; (n) = < O 1 2 3 4 V pre O < n < 2 pre n = 3 pre 4 < n < 7 pre 8 < n < 2047 pre 2048 < n < A4(l) Disjunktně množiny Dátová štruktúra Union-Find a Kruskalov algoritmus Úlohou je pre daný neorientovaný graf G = (V, H) s ohodnotením hrán w nájst najlacnejšiu kostru. Algoritmus využíva dátovú štruktúru Union-Find na reprezentáciu disjunktných množín; každá množina reprezentuje jeden strom v aktuálnom lese. Postupne uvažujeme hrany grafu v neklesajúcom poradí podlá ich ohodnotenia. Ak koncové vrcholy hrany (u, v) patria do rôznych stromov, tak hranu pridáme do kostry a príslušné množiny zjednotíme. Kruskal((V, H),w) i for každý vrchol v G V do Make_Set(í;) od 2 utried hrany z H do neklesajúcej postupnosti podia w 3 for každú hranu (u, v) v danom poradí do 4 if Find_Set(^) 7^ Find_Set(í;) 5 then K <— K U {(u, v)}; Union(i/, v) fi od 6 return K Disjunktně množiny 104 Techniky návrhu algoritmov • Rozděl a panuj • Dynamické programovanie • Hladové algoritmy • Backtracking Disjunktně množiny Rozděl a panuj 1. Problém rozděl na podproblemy 2. Vyrieš podproblemy 3. Z riešení podproblemov zostav riešenie problému Rozděl a panuj 106 Maximálny a minimálny prvok Problém nájdenia maximálneho a minimálneho prvku postupnosti 5[l..n]. Zložitostné kritérium - počet porovnaní prvkov. Max(S) i max <— S[l] 2 for i = 2 to n do 3 if S [i] > max then max <— S [i] fi 4 od Minimum nájdeme medzi zvyšnými n — 1 prvkami podobne. Celkove (n — 1) + (n — 2) porovnaní. Rozdeí a panuj - maximálny a minimálny prvok 107 6285 Prístup Rozděl a panuj 1. Problém rozděl na podproblémy 2. Vyrieš podproblémy 3. Z riešení podproblémov zostav riešenie problému 1. pole rozděl na dve (rovnako velké) podpostunosti 2. nájdi minimum a maximum oboch podpostupnosti 3. maximálny prvok postupnosti je väčší z maximálnych prvkov podpostupnosti podobne minimálny prvok Rozdeí a panuj - maximálny a minimálny prvok 108 i function Maxmin(x,2/) **predpoklad x < y 2 if y = x + 1 then return (max (S [x], 5 [?/]), min (5 [x], 5 [y])) f i 3 if y = X + 2 4 then použitím 3 porovnaní utried S[x], S[x + 1], 5[y] 5 return (max, min) 6Í\ 7 if y > x + 2 s then (maxi, mini) <— Maxmin(x, |_(# + ž/)/2_|) p (max2, mm2) <— Maxmin( [(x + y)/2j + 1, y) io return (max(maxl,max2) min(mml.mm2)) n fi Korektnost: indukciou vzhladom k n = y — x + 1 ukážeme, že Maxmin(x,?/) vráti maximálnu a minimálnu hodnotu S[x..y\. Rozdeí a panuj - maximálny a minimálny prvok 109 Zložitosť: (počet porovnaní) 1 T(n) = { 3 V T([n/2\) + T(\n/2-]) + 2 pre n pre n inak 2 3 Indukciou k n overíme, že T {n) < |n — 2. 1. Pre n = 2 platí f • 2 - 2 > 1 = T(2). Pre n = 3 platí f • 3 - 2 > 3 = T(3). 2. Predpokladajme platnost nerovnosti pre všetky hodnoty 2 < i < n, dokážeme jej platnost pre n. T(n)=T(ln/2\) + T(\n/2}) + 2 indukčný predp. < ||n/2J - 2 + |[n/21 - 2 + 2 = ^n - 2 Rozdeí a panuj - maximálny a minimálny prvok 110 Dynamické programovanie 1. Charakterizuj štruktúru optimálneho riešenia optimálne riešenie problému v sebe obsahuje optimálne riešenia podproblémov 2. Rekurzívně definuj hodnotu optimálneho riešenia 3. Vypočítaj hodnotu optimálneho riešenia zdola-nahor 4. Z vypočítaných hodnôt zostav optimálne riešenie Technika je vhodná pre riešenie optimalizačných problémov, u ktorých dochádza k prekrývaniu podproblémov. Dynamické programovanie 111 Násobenie matíc Je daná postupnost matíc (Ai,..., A7 Matica Ai má rozmery pi-\ x pi. Úlohou je vypočítat ich súčin, zložitostné kritérium je počet skalárnych násobení. Zložitost výpočtu závisí od poradia, v akom násobíme matice. Úlohou je navrhnut algoritmus, ktorý určí, v akom poradí sa majú matice násobit tak, aby celková zložitost výpočtu bola minimálna. Počet rôznych spôsobov, ako môžeme uzatvor kovat postupnost n matíc, P{ri), je 1 pre n = 1 Yľkll p(k) * p(n ~k) pre n > 1 P(n) = , _„_! Indukciou k n overíme, že P(n) > 2 n-2 Dynamické programovanie - násobenie matíc 112 10x20 20x50 50x100 20x100 10x100 10x20 10x1 10x100 Dynamické programovanie - násobenie matíc celková cena = 125 000 cena = 5 000 cena = 100 000 cena = 20 000 celková cena = 2 200 cena = 1 000 cena = 200 cena = 1 000 113 Štruktúra optimálneho riešenia Označme Aimmj (i < j) súčin matíc A^ ..., Aj. Pre výpočet Aimmj musíme najprv vypočítat Aimmk a Ak+i..j pre nejaké k a nakoniec vynásobit matice Aimmk • Ak+i..j ■ Podproblémami problému ozátvor kovania post. < A^ ... ,Aj > je ozátvor ková nie postupností < A^ ..., A^ >, < A^+i,..., Aj > pre všetky i < k < j. Nech optimálne ozátvor ková nie rozdelí Ai- — Aj medzi Ak a Afc+i. Ľahko overíme (sporom), že aj ozátvor ková nie Ai- — Ak a Afc+i • • • Aj musí byt optimálne. Preto ak poznáme optimálne riešenia všetkých podproblemov, môžeme zostavit riešeniu problému. Dynamické programovanie - násobenie matíc 114 Hodnota optimálneho riešenia Označme m[i,j] minimálny počet skalárnych násobení potrebný na výpočet Aí,,j. Platí r. .n ÍO aki=j [mmi 0 je (d je vhodná konštanta) n—1 n—1 T(n) = ^2(T(k) + T (n - k)) + dn = 2 J^ T(fc) + dn fc=i fc=i Platí T(n) - T(n - 1) = 2T(n - 1) + d a T(n) = 6(3n) Dynamické programovanie - násobenie matíc 116 Výpočet hodnoty optimálneho riešenia technikou Dynamického programovania A i NÁSOBENIE MATÍc(Ai, . . . , ,,n 2 for i = 1 to n do m[i, i] <— 0 od 3 for l = 2 to n do 4 5 6 7 8 9 10 11 i2 od for i = 1 to n — l + 1 do j^i + l-1; m[i,j] <— oo for fc = i to j* — 1 do g <— m [i, fc] + m[fc + 1, j] + Pi-ipkpj if q < m[i,j] then m[i, j] <— g; s[ž, j] od od Zložitosť: T(n) = 0(rŕ) Dynamické programovanie - násobenie matíc Zostavenie optimálneho riešenia i Postup Násobenia(s,í, j) 2 if i = j then print Ai 4 5 6 7Í\ else print "C Postup Násobenia(s,í,s[í, j]) Postup Násobenia(s,s[í, j] + 1J) print ")" Dynamické programovanie - násobenie matíc 118 Najväčšia spoločná podpostupnost Nech X =< #i,..., xm > a Z =< z\,..., Zk > sú postupnosti symbolov. Z je podpostupnostou X práve ak existuje rastúca postupnost indexov < ii,...,ifc > postupnosti X taká, že pre všetky j = 1,..., k platí a^. = z j. Pre dané dve postupnosti symbolov X a y hovoríme, že postupnost Z je ich spoločnou podpostupnostou práve ak Z je podpostupnostou X aj F. Problém najdlhšej spoločnej podpostupnosti je pre dané dve postupnosti symbolov X a Y nájst ich najdlhšej spoločnú podpostupnost (NSP). Dynamické programovanie - najväčšia spoločná podpostupnost 119 Štruktúra optimálneho riešenia Označenie: pre postupnost X =< xi,...,xm > definujeme jej z-ty prefix (pre i = 0,..., m) ako Xi =< xi,..., xi >. Nech X =< xi,..., xm > a F =< ?/i,..., yn > sú postupnosti symbolov a nech Z =< 21,..., Zk > je ich NSP. 1. Ak xm = yn tak ^ = xm = yn a 2&-i Je NSP postupností J^m—l 3 Yn—i. 2. Ak xm ^ yn 3 Zk ^ xm, tak Z je NSP postupností Xm_i a y. 3. Ak xm ^ yn a Zk ^ yn, tak Z je NSP postupností X a l^_i. Dynamické programovanie - najväčšia spoločná podpostupnost 120 Hodnota optimálneho riešenia Definujme c[i,j] ako dĺžku NSP postupností Xi a Yj. Platí c[ij] = < 0 c v max(c[i, j — 1], c [i — ak i = 0 alebo j = 0 ak i J > 0 a Xi = yj 1J}) ak i J >0 a Xi^yj Poradie výpočtu: c[l, 1],..., c[l,n c[2,1],..., c[2,n c m, 1],..., c m,n Dynamické programovanie - najväčšia spoločná podpostupnost 121 Výpočet hodnoty optimálneho riešenia nsp(x,f) i for i = 1 to m do c[i, 0] <— 0 od 2 for j = 0 to n do c[0, j] <— 0 od 3 for i = 1 to m do 4 for j = 1 to n do 5 if Xi = Yj then c[i,j] <— c [i — 1, j — 1] + 1 6 6[i,j]<-* 7 else if c [i — l,i] > c[i, j — 1] s then c[i, j] <— c[i — 1, j] p 6[i,j]<-4 io else c[i,j] <- c[i,j - 1] i2 fi fi od od i3 return c, 6 Dynamické programovanie - najväčšia spoločná podpostupnost 122 Zostavenie optimálneho riešenia PRINT_NSP(6,X,i,j) j if i = 0 V j = 0 then return fi 2 if b[i,j] = 4 then Print_NSP(6,X,í - 1, j - 1) 3 print Xj 4 else if b[i,j] = 4 s then Print_NSP(6, X, i - 1, 6 else Print_NSP(6, X, i, -1) 7 fi 8Í\ Dynamické programovanie - najväčšia spoločná podpostupnost Ďalšie príklady algoritmov dynamického programovania • Floydov algoritmus • Warshallov algoritmus • Konštrukcia vyváženého binárneho vyhladávacieho stromu Dynamické programovanie - najväčšia spoločná podpostupnost 124 Hladové algoritmy 1. Technika je vhodná pre riešenie optimalizačných problémov, ktoré majú optimálnu subštruktúru (optimálne riešenie problému v sebe obsahuje optimálne riešenie podproblémov). 2. Pre získanie optimálneho riešenia stačí poznat optimálne riešenie jedného z podproblémov. Tento podproblém vyberáme na základe kritéria lokálnej optimality (KLO), tj. bez znalosti jeho riešenia. 3. Vo výpočte postupujeme zhora nadol. Technika nieje použitelná pre všetky optimalizačné problémy. Hladové algoritmy 125 Problém mincí K dispozícii máme mince hodnoty hi,...,/&&, počet mincí každej hodnoty je neobmedzený. Úlohou je pre dané N zaplatit sumu N za použitia čo najmenšieho počtu mincí. Problém má optimálnu subštruktúru, pretože ak použijeme mincu hodnoty hi, tak na zaplatenie sumy N — hi musíme opat použit optimálny počet mincí. Označme MIN[i] minimálny počet mincí, ktoré sú potrebné na zaplatenie sumy i. Platí MIN 0 pre i = 0 1 + mmi< j 0 Hladové algoritmy - problém mincí 126 Dynamický prístup: počítame hodnoty MIN[1],... ,MIN[N]. ZLožitost je ö(Nk), algoritmus vždy vypočíta optimálnu hodnotu. Hladový prístup: KLO = ak máme zaplatit hodnotu i, tak vyberieme mincu hx maximálnej hodnoty takú, že hx < i. Mince(í) i predpokladáme, že h\ > h^ > ... > hk 25^0 3 for m = 1 to k do 4 while i > hm do i <— i — hm; 5 ^ s + 1 od 5 od 6 return s Pre mince hodnoty 6, 4, 1 a sumu 8 algoritmus nenájde optimálne riešenie!! Hladové algoritmy - problém mincí 127 Problém pásky Je daných n súborov dĺžky mi,m2,..., mn. Súbory sa majú uložit na pásku. Všetky súbory sa budú z pásky čítat. Prístupový čas k súboru i je rovný súčtu dĺžok súborov, ktoré sú na páske uložené pred ním, plus jeho dĺžka vrti. Úlohou je uložit súbory na pásku v takom poradí, aby sa súčet prístupových časov k jednotlivým súborom minimalizoval. Problém má optimálnu subštruktúru, pretože ak ako prvý uložíme na pásku súbor i, tak ostatné súbory musíme usporiadat optimálne. Hladový algoritmus: KLO = vyber spomedzi ešte neuložených súbor najkratší a ulož ho na pásku (tj. ulož súbory na pásku od najkratšieho po najdlhší). Hladové algoritmy - problém pásky 128 Korektnost Lema 1. Každá permutácia (ii,..., in) súborov taká, že postupnostmi, ..., rriinje neklesajuca, má minimálny súčet prístupových časov. Dôkaz. Nech II = (ii,...,in) Je permutácia (l,...,n) taká, že postupnost m^,... ,min nie je neklesajuca. Preto existuje 1 < j < n pre ktoré m^. > rrii.+r Nech IT je permutácia,ktorá vznikne z II prehodením ij a i/+i- Cena permutácií II a IT je n k n fc=ij=i k=i Hladové algoritmy - problém pásky 129 i-1 C(Iľ) = 5](n - fc + l)mifc + (n fc=i n Z toho C(n) - C(lľ) = (n - j + l)(mť. - mij+1) + (n - j)(m,J+1 - mť.) Preto n nemá minimálny súčet prístupových časov. Naviac lahko overíme, že všetky permutácie požadovaných vlastností majú rovnaký (a teda minimálny) súčet prístupových časov. □ -j + 1)771;.,.. + (n-j)m, *j+i j Hladové algoritmy - problém pásky 130 Rozvrh Je daných n prednášok, každá prednáška i má pevne stanovený svoj začiatok zi a koniec ki (zí < ki). Prednášky i a j nazveme kompatibilné práve ak Zi > kj alebo Zj > ki. Úlohou je vybrat čo najväčšiu množinu vzájomne kompatibilných prednášok (tj. prednášok, ktoré sa môžu konat v jednej posluchárni). Hladový algoritmus: KLO = vyber prednášku, ktorá má minimálnu hodnotu ki a je kompatibilná s už vybranými prednáškami. i predpokladáme, že k\ < k2 < ... < kn 3 for i = 2 to n do if zi > kj then A ^ AU {i} 4 j <— i fi od 5 return A Hladové algoritmy - rozvrh 131 Korektnost Indukciou vzhladom k velkosti vypočítaného rozvrhu A. 1. \A\ = 1 Zrejme A = {1} a z výpočtu plynie, že žiadna z prednášok nie je kompatibilná s 1. Potom ale žiadne dve prednášky nie sú kompatibilné a nájdené riešenie je optimálne. 2. \A\ = i, predpokladáme platnost pre \A\ < i — 1 V prvom kroku sa do A zaradí prednáška 1. V následnom výpočte sa algoritmus aplikuje na výpočet rozvrhu pre množinu Sf prednášok kompatibilných s 1 a vypočíta sa A! = A \ {1}. Pretože \A'\ = i — 1, je podia IP optimálny. Ukážeme, že potom aj A je optimálny rozvrh pre všetky prednášky. Hladové algoritmy - rozvrh 132 (a) A zrejme obsahuje kompatibilné úlohy. (b) A je maximálny - ukážeme sporom. Nech by existoval rozvrh B pre S taký, že \B\ > \A\. Potom existuje rozvrh B' taký, že \B'\ = \B\ a B' obsahuje 1 {B1 = (B \ {i}) U {1}, kde i je úloha z B s najmenším fc^. Rozvrh B' je kompatibilný, pretože fci < ki.). Ale potom aj B' \ {1} je rozvrhom pre S1. Platí |B7| - 1 = |B| - 1 > \A\ - 1 = \Ä\ a to je spor s optimalitou A'. Hladové algoritmy - rozvrh 133 Príklady hladových algoritmov • Dijkstrov algoritmus pre problém najkratších ciest z daného vrchola • Kruskalov a Primov algoritmus pre najlacnejšie kostry • Huffmanove kódy Hladové algoritmy - rozvrh 134 Backtracking Technika prehladavania priestoru potenciálnych riešení založená na princípe Rozděl a panuj. - do priestoru potenciálnych riešení vnesieme stromovú štruktúru, (binárne retazce, fc-árne retazce, permutácie, kombinácie) - stromovú štruktúru prehladávame do hĺbky - prehladávanie zefektívnime odřezáváním ciest, ktoré dokazatelné nevedú k Nadanému riešeniu Príklady Batoh - potenciálne riešenia sú všetky podmnožiny predmetov Hamiltonovský cyklus - p.r. sú všetky permutácie vrcholov grafu k-klika - p.r. sú všetky kombinácie k-tej triedy vrcholov grafu Backtracking 135 Návrh backtrackovacieho algoritmu 1. Volba spôsobu reprezentácie potenciálnych riešení. 2. Generovanie potenciálnych riešení technikou Rozděl a panuj. 3. Testovanie požadovanej vlastnosti. 4. Odrezávanie neperspektívnych ciest. Backtracking 136 Problém tyčí Daných je n tyčí dĺžky d1?..., dn a číslo D G N. Úlohou je vybrat s tyče tak, aby súčet ich dĺžok bol presne D. 1. Potenciálne riešenia sú všetky spôsoby výberu tyčí. Riešenia budeme reprezentovat ako binárne retacze, konkrétne pomocou binárneho póla A[l..n]. Hodnota A[i] = 1 práve ak tyč i je vybraná. Binárne retazce vytvárajú stromovú štruktúru Backtracking - problém tyčí 137 9 9 9 ? ? O 9 9 1 ? O O 3 ? 0 1 9 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 o 1 0 1 1 1 1 1 i TYČ(m,Z) 2 if m = 0 then if Z = 0 then print A fi 3 4 5 6 /fi else A m ^0 TYČ(m-l,Z) if dm < I then ^4[ra 1 TYČ(m — 1,/ — dm) fi 2. Strom prehladávame do hĺbky: pole A napĺňame zprava dolava Backtracking - problém tyčí 138 3. Požadovanú vlastnost testujeme v okamihu, ked máme vygenerované celé potenciálne riešenie (riadok 2, základ rekurzie). 4. Cesty odřezáváme, ked dĺžka vybraných tyčí prekročí daný limit (riadok 5). Poznámka: technikou dynamického programovania sa problém dá rieši t v čase ö{nD). Zobec nenie pre prípad, že daných je k i tyčí dĺžky di. Backtracking - problém tyčí 139 Hamiltonovský cyklus Hamiltonovský cyklus v orientovanom grafe je cyklus, ktorý navštívi každý vrchol grafu práve raz. Úlohou je nájst v danom grafe G = (V, H) Hamiltonovský cyklus. Reprezentácia grafu: polia 7V[l..n, l..s] a 5[l..n], kde n je počet vrcholov grafu a s je maximálny stupeň vrcholu v grafe. Hodnota S [i] je stupeň vrcholu i a N [i] je zoznam susedov vrcholu i. 1. Potenciálne riešenia sú všetky cykly dĺžky n v grafe. Riešenia reprezentujeme ako retazce nad abecedou {l,...,n} (pole A[l..n]), cyklus je A[n] -> A[n - 1] ->-------> A[l] -^ A[ri\. Aby sme mohli prerezavat neperspektívne cesty, ktoré nie sú Hamiltonovské, použijeme pomocné pole P[l..n]; hodnota P [i] je false ak aktuálna cesta už navštívila vrchol i. Backtracking - Hamiltonovský cyklus 140 for i = 1 to n — 1 do P true od P n false; A n n 3 HAMILTON(n - 1) 4 procedure HAMiLTON(m) 5 if m = 0 then Kontrola(A) ô else for j = 1 to 5[A[m + 1]] do 7 w<^N[A[m + l]J] s if P[w] then P[w] <— false; A[m 9 HAMILTON(m - 1) 10 P w true fi od fi u procedure Kontrola(A) i2 ok <— false is for j = 1 to S[A[1}} do if N[A[1], j] = A u if ok then prints n then ok Backtracking - Hamiltonovský cyklus 2. Strom riešení prehladávame do hĺbky; pole A napĺňame zprava 3. Po vygenerovaní Hamiltonovskej cesty dĺžky n testujeme (procedúra Kontrola), či je možné cestu uzavriet do cyklu. 4. Neperspektívne cesty odřezáváme vždy ked sa nich zopakuje niektorý vrchol druhý krát (riadok 8). Zložitost T(ri) algoritmu je (6, c sú vhodné konštanty) bs ak n = 1 T(n) < ' sT(n — 1) + c inak Z toho T{n) = ü(sn). Backtracking - Hamiltonovský cyklus 142 Hamiltonovský cyklus - riešenie založené na permutáciách Potenciálne riešenia - permutácie postupnosti (1,... , n). Permutácie sú uložené v poli A[l..n], iniciálne A[i] = i pre i — 1,...,n Algoritmus generovania permutácií i procedure PERMUTÁciE(m) 2 if m = 1 then kontrola vlastností 3 else PERMUTÁciE(m - 1) 4 for i = m — 1 downto 1 do 5 vymeň A[m] a, A[i 6 PERMUTÁCIE(m - 1) 7 vymeň A[m] a A[i s od fi Algoritmus doplníme o kontrolu, či vygenerovaná permutácia tvorí Ham. cyklus. Graf je zadaný maticou susednosti M[l..n, l..n Backtracking - Hamiltonovský cyklus 143 i for i = 1 to n do A[i] <— i od 2 HAMILTON_PERM(n - 1) 3 procedure HAMiLTON_PERM(m) 4 if m = 0 then Kontrola_Perm(A) 5 else for i = m downto 1 do 6 \fM[A[m + l],A[i\] 7 then vymen A[m] a A[i] 8 HAMILTON_PERM(m - 1) 9 vymeň A[m] a A[i] f i ío od li fi i2 procedure Kontrola_Perm(A) is if M[A[l],n] then print A f i Backtracking - Hamiltonovský cyklus 144 Označme T (n) počet výmen, ktoré urobí počas výpočtu algoritmus HAMILTON_PERM(n). Potom T(n) = {° Pren=1 nT{n - 1) + 2(n - 1) pre n > 1 Indukciou vzhíadom k n sa ukáže T (n) < 2n\ — 2 Zložitost problému Hamiltonovského cyklu je • ö(sn) - algoritmus založený na retazcoch • O ((n — 1)!) - algoritmus založený na permutáciách Algoritmus založený na retazcoch je lepší ak s < n/e. Backtracking - Hamiltonovský cyklus 145 Grafové algoritmy • Prehladávanie (prieskum) grafov a rôzne druhy súvislosti • Stromy a kostry • Optimálne sledy • Toky v sietiach Grafové algoritmy 146 Hledání minimální kostry grafu Je dán souvislý neorientovaný graf G = (V, íŕ) spolu s ohodnocením hran (váhovou funkcí) w : H —» R+. Množinu K C H nazveme kostrou grafu G, jestliže je graf G' = (V,K) souvislý a acyklický (kostra je vždy stromem). Definujeme váhu kostry K předpisem W{K) = Y^ w(h)- heK Minimální kostrou rozumíme kostru s minimální váhou. Minimální kostry 147 Příklad: Minimální kostra K má váhu W(K) =4 + 8 + 7 + 9 + 2 + 4 + 1 + 2 = 37, Minimální kostry 148 Růst minimální kostry Inicializace : K = 0 Do K přidáváme postupně (po jedné) hrany, dokud nedosáhneme kostry. Invariant : K je podmnožinou nějaké minimální kostry. Necht K je množina hran, která je podmnožinou nějaké minimální kostry grafu G. Hranu h £ H nazveme bezpečnou hranou pro množinu K C H, jestliže h 0 K a K U {h} je stále podmnožinou nějaké minimální kostry. Minimální kostry 149 Obecný algoritmus pro nalezení minimální kostry Min-kostra((V, H),w) 2 while K netvoří kostru do 3 Vyber hranu /z, která je bezpečná pro K 4 K^KU{h}. 5 od 6 return K Korektnost algoritmu plyne z definice bezpečných hran. Algoritmus vždy zastaví nebot cyklus while proběhne vždy právě V\ - 1 krát. Nejobtížnější částí algoritmu je krok 3 - nalezení bezpečné hrany pro aktuální K. Minimální kostry - obecný algoritmus 150 Hledání bezpečných hran Řezem (S,V — S) v grafu rozumíme libovolné rozdělení množiny vrcholů do dvou podmnožin. Řekneme, že hrana h křižuje řez (5, V — S), jestliže jeden z jejich koncových vrcholů leží v S a druhý v V — S. Rez (5, V — S) respektuje množinu hran K, pokud žádná hrana z množiny K nekřižuje řez (5, V — S). Hranu h G H nazveme lehkou hranou vzhledem k řezu (S,V — S), jestliže tento řez kříží a má ze všech takových hran minimální váhu. Minimální kostry - bezpečné hrany 151 Příklad řezu respektujícího danou množinu hran. Příslušná lehká hrana je zvýrazněna světlemodře. Minimální kostry - bezpečné hrany 152 Následující lemma poskytuje návod jak hledat bezpečné hrany. Lema 2. Necht G = (V, H) je souvislý neorientovaný graf s váhovou funkcí w : H —» R+. Dále necht K C H je množina hran, která je podmnožinou nějaké minimální kostry grafu G. Uvažujme libovolný rez (5, V — S), který respektuje množinu K a hranu h, která je lehkou hranou vzhledem k řezu (5, V — S). Pak h je bezpečná pro množinu K. K T Minimální kostry - bezpečné hrany 153 Dôkaz. Necht T' je nějaká minimální kostra, jejíž podmnožinou je K. Pokud h G T7, není co dokazovat. Předpokládejme tedy, že h 0 T'. Sestrojíme minimální kostru, která obsahuje K U {h}, čímž dokážeme, že hrana h je bezpečná pro K. Množina hran T' U {h} jistě obsahuje cyklus, musí tedy existovat hrana h' ^ h z tohoto cyklu, která křižuje řez (5, V — S). Označme T = T' U {h} — {hf}. Zřejmě je (V, T) souvislý graf, a protože \T\ = \Tf\ = \V\ - 1, je T kostra grafu G. Z minimality kostry T7 plyne w(T) > w(T) =^> w(/&) > w(hf). Naopak z lehkosti hrany h plyne w(/&) < w(h'). Celkem tedy w(h) = w(h'), odkud máme, že T je minimálni kostra. Navíc K U {h} C T a tedy /z je bezpečná pro K. ■ D Minimálni kostry - bezpečné hrany 154 Kruskalův algoritmus Množina K tvoří les. V každém kroku Kruskalova algoritmu vybíráme hranu h s minimální vahou ze všech hran spojujících různé komponenty z K. Necht K\,K R. Sled p =< vo, i>i,..., Vk > symbolicky značíme vq ^ Vfe. Dĺžkou sledu p =< vo, i>i,..., i>fc > je súčet dĺžok jeho hrán, def ^(p) = y2w(vi-uvi) 1=1 s Dlžka sledu p —< v > neobsahujúceho žiadnu hranu je w{p) = 0 Najkratšie cesty 162 Najkratšie cesty 163 záporný cyklus tvoria hrany dĺžky -6, 1, 3 všetky vrcholy v okrem vrcholu s majú S(s,v) = —oo Najkratšie cesty 164 Cyklus c =< vo, i>i,..., v*; >, vo = vk, nazývame záporný cyklus s práve ak jeho dlžka w(c) < 0. Ak žiadna cesta z vrcholu u do vrcholu v neobsahuje vrchol patriaci zápornému cyklu, tak dlžka najkratšej cesty z u do v je zhodná s dĺžkou najkratšieho sledu z u do v. Naopak, ak existuje cesta z u do v obsahujúca vrchol patriaci zápornému cyklu, tak žiaden sled z u do v nemôže byt najkratší. Najkratšie cesty 165 Definujeme dĺžku najkratšej cesty z u do v ako 5{u,v) = < oo —oo p \ mm{w(p) u ^ v} ak neexistuje cesta z u do v ak nejaká cesta z u do v obsahuje vrchol patriaci zápornému cyklu inak Ak 8(u,v) je konečné, tak najkratšia cesta z u do v je lubovolná cesta z u do v dĺžky 5(i/, v). Najkratšie cesty 166 Problémy Najkratšie cesty z daného vrcholu s do ostatných vrcholov grafu Najkratšie cesty zo všetkých vrcholov grafu do daného vrcholu t Najkratšia cesta medzi danou dvojicou vrcholov Najkratšie cesty medzi všetkými dvojicami vrcholov grafu Úlohou je vypočítat dĺžku najkratšej cesty medzi určenými dvojicami vrcholov. Naviac, ak ô(u, v) je konečné, tak požadujeme, aby algoritmu našiel niektorú najkratšiu cestu z u do v. Najkratšie cesty 167 Optimálna subštruktúra najkratších ciest Lema 3. Nech p =< vi,...,Vk > je najkratšia cesta z vrcholu vi do vrcholu Vk a nech pre lubovolne i, j také, žel podcesta cesty p z v i do v j. Potom pij je najkratšia cesta z v i do v j. Algoritmy sú založené na princípoch dynamického programovania resp. na princípe hladových algoritmov. Najkratšie cesty 168 Najkratšie cesty z koreňa s do ostatných vrcholov grafu • Bellman-Fordov algoritmus • Algoritmus pre acyklické grafy s • Dijkstrov algoritmus pre grafy s nezápornými dĺžkami hrán Najkratšie cesty z koreňa 169 Reprezentácia najkratších ciest Pre každý vrchol v udržujeme hodnotu p[v] - otec vrchola v. Iniciálna hodnota je p v = Nil. Na konci výpočtu je graf Gp = (Vp,Hp) indukovaný hranami (p[v],v) stromom najkratších ciest z s do ostáných vrcholov grafu. Pritom Vp = {v G V | p[v] ^ Nil} U {s} HP = {{p[v],v) e H \v eVp\{s}} Ďalej pre každý vrchol v udržujeme hodnotu d[v] - dĺžka cesty z s do í; v aktuálnom grafe indukovanom hranami (p[v],v). Iniciálna hodnota je pre v ^ s rovná d[v] = oo (v indukovanom grafe neexistuje cesta z s do v) a d[s] = 0. Na konci výpočtu je d[v] = ö(s,v). Najkratšie cesty z koreňa 170 Bellman-Fordov algoritmus Algoritmus je založený na postupnom zlepšovaní hodnôt d[u\. Ak vrcholu u zlepšíme hodnotu diu], musíme následne preskúmat všetky hrany (u,v) £ H a ak je to možné, zlepšit hodnotu d[v] (operácia Relaxácia). Algoritmus vráti hodnotu true práve ak graf neobsahuje cyklus zápornej dĺžky dosiahnutelný z koreňa s. Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 171 Bellman-Ford(G, w, s) i Inicializácia^, s) 2 for i = 1 to IV\ — 1 do 3 for každú hranu (u, v) G H do Relaxácia^,?;,?/;) od od 4 for každú hranu (i/,, i;) G H do 5 if d [v] > d[u] + w(u, v) then return false fi od 6 return true Inicializácia^, s) i for každý vrchol vGľdo 2 d[v] <— oo; p[v] <— Nil od s d[s] <- 0 RELAXÁCIA^, i;, w) i if d [V] > d [i/] + w(u, v) 2 then d[v] <— d[u] + w(u, v); p[v] <— u f i Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 172 Q 2 graf G p c 2 (d) (e) Výpočet algoritmu Bellman-Ford pre graf s koreňom a. V každej iterácii cyklu 2-3 relaxujeme hrany v poradí (c, e), (d, e), (6, d), (c, d), (6, c), (a, c), (a, b). Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 173 Korektnost algoritmu Bellman-Ford Lema 4. Nech v grafe G neexistuje záporný cyklus dosiahnutel-ný z koreňa s a pre G zavoláme procedúru InicializÁcia(G, s). Potom G p je strom s koreňom s a tento invariant zostáva v plat-nosti po vykonaní lubovolnej postupnosti relaxácií. Dôkaz. Tvrdenie triviálne platí bezprostredne po inicializácii. Uvažujme graf Gp, ktorý dostaneme po vykonaní postupnosti relaxácií. Ukážeme, že je acyklický a že pre každý vrchol v G Vp existuje v Gp jediná cesta z s do v. Predpokladajme, že v Gp existuje cyklus c =< ^0,^1,...,^ >■ kde vo = Vk- Potom p[vj\ = i^_i a búno môžeme předpokládat, že cyklus vznikol počas RELAXÁciA(vfc_i, v^,?/;). Ľahko overíme, že všetky vrcholy cyklu sú dosiahnutelné z vrcholu s. Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 174 Tesne pred volaním RelaxÁcia^-i,^,?/;) platí pre každý vrchol Vi cyklu, i = 1,..., k — 1, d[vi] > d[vi_i] +w(yi-1,vi). Pretože počas uvedenej relaxácie sa mení hodnota p[vk], tak bezprostredne pred jej vykonaním platí d[vk] > d[vk-i] +w(yk-i,vk). Sčítaním všetkých nerovností dostávame Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 175 ■ k n i v^fc Pretože 5ľi=1d[^i-i] = J2i=id[vi]1 tak dostávame nerovnost k 0 > ^2w(vi-UVi) = w{c) i=l čo je spor s predpokladom o neexistencii záporného cyklu v G. Zostáva overit, že pre každý vrchol v G Vp existuje v Gp práve jedna cesta z s do v. Existencia cesty je zrejmá. Pretože hodnota p[v] je určená jednoznačne, nemôžu v Gp viest do žiadneho vrcholu dve hrany. Preto v Gp nemôžu existovat ani dve cesty z s do v. D Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 176 Lema 5. Nech v grafe G neexistuje záporný cyklus dosiahnu-telný z koreňa s. Predpokladajme, že pre G voláme Inicializacia(G, s) a potom relaxujeme hrany v lubovolnom poradí tak, že na konci výpočtu pre každý vrchol v platí d[v] = 5 [s, v]. Potom G p je strom najkratších ciest s koreňom s. Dôkaz. Zrejme Vp je množina vrcholov dosiahnutelných z s. Podlá Lemy 4 je Gp strom. Zostáva ukázat, že pre každý vrchol v G Vp je jediná cesta s ^> v v Gp najkratšou cestou z s do í;. Nech p =< ^0,^1,...,^ >> kde vq = s a Vk = v. Pre každé i = 1,2, ...,fc máme d[vj\ = S(s,Vi) a ^(^_i,^) < 5(s,i>i) — ö(s,Vi-i). Sčítaním všetkých nerovností dostávame w(p) = ö(s,vk). D Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 177 Lema 6. Nech v grafe G neexistuje záporný cyklus dosiahnutelný z koreňa s. Po tom po \V\ — 1 iteraciach cyklu 2-3 algoritmu bellman-Ford(G,^, s) platíd[v] = ô[s,v] pre všetky vrcholy v dosiahnutelné z vrcholu s. Dôkaz. Nech p =< ^0,^1,...,^ >, kde vq = s a v^ = v, je najkratšia acyklická cesta z s áo v. Potom k < \V\ — 1. Indukciou vzhladom k i (s využitím optimálnej subštruktúry najkratších ciest) dokážeme, že po i-tej iterácii cyklu 2-3 platí d[ví\ = ô(s,Vi). Naviac platí, že ak premenná d[ví\ nadobudne hodnotu ö(s,Vi), tak jej hodnota sa už v priebehu výpočtu nemení. D Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 178 Veta. Ak v grafe G neexistuje žiaden záporný cyklus dosiahnutelný z s, tak algoritmus Bellman-Ford(G, w, s) vráti hodnotu true, pre každý vrchol v platíd[v] = 5[s, v] a Gp je strom najkratších ciest s koreňom s. Ak v G existuje záporný cyklus dosiahnutelný z s, tak algoritmus vráti hodnotu false. Dôkaz. Nech v G neexistuje záporný cyklus dosiahnutelný z s. Ak vrchol v je dosiahnutelný z s, tak podlá Lemy 6 na konci výpočtu platí d[v] = S[v\. Ak v nie je dosiahnutelný, tak z invariantu výpočtu d[v] > ô[v] plynie, že na konci je ô[v] = oo. Na konci výpočtu pre každú hranu (u, v) G H platí d[v] = S(s,v) < S(s,u) + w(u,v) = d[u] + w(u,v) a preto žiaden test na riadku 5 nevráti hodnotu false. Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 179 Naopak, nech v G existuje záporný cyklus c =< vq, i>i, ..., Vk >, kde vo = Vk, dosiahnutelný z 5. Predpokladajme, že algoritmus vráti true. Potom pre všetky i = 1, 2,..., k platí d[^] < d[i^_i] +w(vi-i,Vi). Sčítame všetky nerovnosti k k Ei=idN < ^2i=i(d[vi-i] +w(vi-1,vi)) k k = Ei=i d[vi-x] + Y,í=i w(Vi-U Vi) Pretože X^í=i^[^-i] = Y2í=i d[vj\ a pre všetky i je d[vj\ < 00, tak dostávame nerovnost k 0 < ^2w(vi-UVi) = w(c) i=l čo je spor s predpokladom o zápornej dĺžke cyklu c. D Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 180 Zložitost Bellman-Fordovho algoritmu Inicializácia grafu má zložitost 8(|1/|). Cyklus 2-3 má zložitost 6(|ií|); počet jeho opakovaní je \V\ — 1. Celková zložitost je ö{nm), ked n je počet vrcholov a m je počet hrán grafu. Varianty Bellman-Fordovho algoritmu Líšia sa poradím, v akom sa relaxujú hrany grafu a v spôsobe, akým sa zistuje existencia dosiahnutelného záporného cyklu v grafe. Pre špeciálne typy grafov existujú efektívnejšie algoritmy. Príkladom sú algoritmy pre acyklické grafy, pre grafy s malým ohodnotením hrán a pre grafy s nezáporným ohodnotením hrán. Najkratšie cesty z koreňa - Bellman-Fordov algoritmus 181 Algoritmus pre acyklické grafy Optimálne poradie relaxácie hrán v Bellman-Fordovom algoritme je také, ked vždy relaxujeme hranu (u, v) pre ktorú d[u] = ô(s,u). Pre obecný graf určit poradie relaxácií tak, aby bola dodržaná uvedená podmienka, môže byt rovnako náročné ako vypočítat najkratšie cesty. Špeciálne pre acyklické grafy sa toto poradie dá vypočítat jednoducho. Topologické utriedenie pre orientovaný acyklický graf G = (V, H) je lineárne usporiadanie vrcholov grafu také, že ak graf obsahuje hranu (u,v), tak u predchádza v v usporiadaní. Topologické utriedenie grafu môžeme vypočítat tak, že graf prehladávame do hĺbky a vrcholy usporiadame v poradí, v akom sa v prehladávaní ukončil ich prieskum. Najkratšie cesty z koreňa - acyklické grafy 182 Najkratšie-cesty-v-acyklickom-grafe((V, H),w, s) i Inicializácia((V,íí'),s) 2 for každý vrchol u v topologickom utriedení do 3 for každý vrchol v taký, že (i/,, v) G H do 4 Relaxácia^, v, w) 5 od od Každá hrana grafu sa relaxuje iba raz, celková zložitost algoritmu je 0(n + m). Najkratšie cesty z koreňa - acyklické grafy 183 Dijkstrov algoritmus Rieši problém najkratších ciest z koreňa s do ostatných vrcholov grafu pre grafy s nezáporným ohodnotením hrán . Algoritmus udržuje množinu S vrcholov, pre ktoré sa už vypočítala s dĺžka najkratšej cesty. Algoritmus opakovane vyberá vrchol u EV\S s najkratšou cestou a relaxuje hrany vychádzajúce z u. Najkratšie cesty z koreňa - Dijkstrov algoritmus 184 Dijkstra(G,w,s) i Inicializácia^, s) 25^0; Q^V 3 while Q ^ 0 do 4 5 6 7 8 9 10 11 u <— (u G Q A d[u] = min{d[x] | x G Q}) s <- s u M Q <- Q \ W for každý vrchol v taký, že (i/,, v) G ií do if d [v] > d [i/] + ^(^, v) then d [V] <— d [i/] +w(u,v); p v u od od Najkratšie cesty z koreňa - Dijkstrov algoritmus Korektnost Dijkstrovho algoritmu Veta 1. Pre orientovaný graf G = (V, H) s nezáporným ohodnotením hrán w a koreňom s Dijkstrov algoritmus skončí a pre všetky u E V platíd[u] = 5(s, u). Dôkaz. Ukážeme, že invariantom while cyklu algoritmu je pre každý vrchol v G S platí d[v] = ô(s,v) Platnost invariantu po inicializácii je zrejmá. Nech u je prvý vrchol, ktorý zaradíme do S a pritom d[u] ^ ô(s,u). Zrejme u 7^ s a u je dosiahnutelný z s (v opačnom prípade by platilo ô(s,u) = 00 = d[u\). Nech p je najkratšia cesta z s do u. Cestu p môžeme dekomponovat na dve cesty ako s ^ x —> y ^ u tak, že bezprostredne pred zaradením u do S všetky vrcholy cesty p\ patria do S a y 0 5. Potom d [x] = 5(s, x) a aj d [y] = ô (s, y) (pri zaradení x do 5 bola relaxovaná hrana (x, y)). Najkratšie cesty z koreňa - Dijkstrov algoritmus 186 Cesta p2 je najkratšou cestou z y do u čo spolu s nezáporným ohodnotením hrán implikuje ô(s,y) < ô(s,u). Pretože ale vrchol u bol vybraný do S, tak zároveň bezprostredne pred zaradením u do S platí d[u] < d[y] = ô(s,y). Spojením dostávame ö(s,u) < d[u] < S(s,y) < S(s,u) a teda d[u] = S(s,u). Výpočet končí ked Q = 0, tj. V = S a tvrdenie vety je dokázané. D Najkratšie cesty z koreňa - Dijkstrov algoritmus 187 Zložitost Dijkstrovho algoritmu Zložitost závisí od spôsobu reprezentácie množiny Q, efektivity výberu prvku u s minimálnou hodnotou d[u] (operácia Extract_Min) a aktualizácie hodnôt d[v] pre vrcholy susediace s u (operácia Decrease_Key). Ak hodnoty d[v] sú uložené v poli, tak Extract_Min má zložitost ö(|l/|) a Decrease_Key má konštantnú zložitost. Celková zložitost Dijkstrovho algoritmu je Ö(\V\2 + \H\) = Ö(\V\2). Pri reprezentácii pomocou Fibonacciho haldy je amortizovaná cena každej Extract_Min operácie (9(log|l/|) a amortizovaná cena Decrease_Key je konštantná. Celková zložitost je 0(\V\log\V\ + \H\). Najkratšie cesty z koreňa - Dijkstrov algoritmus 188 Najkratšie cesty medzi všetkými dvojicami vrcholov grafu algoritmus založený na násobení matíc - #(|1/|3 log | V|) Floyd-Warshallov algoritmus - #(|1/|3) Johnsonov alg. pre riedke grafy - (9(|1/|2 log \V\ + \V\ • \H\) Prvé dva algoritmy predpokladajú, že graf je reprezentovaný maticou susednosti. Johnsonov algoritmus využíva Bellman-Fordov a Dijkstrov algoritmus. Najkratšie cesty medzi všetkými dvojicami 189 Algoritmus založený na násobení matíc Daný je orientovaný graf G = (V, H) s ohodnotením hrán w R. Predpokladáme, že graf je reprezentovaný n x n (n maticou susednosti W = (wíj), kde H V\) def 0 Wíj = < váha hrany (i, j) oc v a k i = j ak i ^ j a (i J) G Ír ak i ^ j a (i, j) £# Predpokladáme, že graf neobsahuje žiadne záporné cykly. Navrhovaný algoritmus pracuje na princípoch dynamického programovania. Najkratšie cesty medzi všetkými dvojicami - násobenie matíc 190 Štruktúra optimálneho riešenia Uvažujme najkratšiu cestu p z i do j. Cesta p je konečná a má m hrán. s Ak i = j tak p má dĺžku 0 a neobsahuje žiadnu hranu (m = 0). Ak i y^ j, tak cestu p môžeme rozložit na i ^ k —> j, kde p' má m — 1 hrán. Podlá Lemy 3 je pf najkratšou cestou z i do fc a Najkratšie cesty medzi všetkými dvojicami - násobenie matíc 191 Hodnota optimálneho riešenia (m) m hrán. Pre m = 0 platí Označme l™ minimálnu dĺžku cesty z i do j, ktorá má n ,(o) def I 0 ak i = j %3 oo ak i ^ j Pre m > 0 platí 4m) =min(4m ^»mini^fe^l^ 1}+wfci}) r7(m—1) , t = minife + wkj j Pretože najkratšia cesta z i do j nemôže mat viac než 'i j hrán, tak ô(ij) = ľ£ Najkratšie cesty medzi všetkými dvojicami - násobenie matíc Výpočet hodnoty optimálneho riešenia Počítame matice L^\ ... L^"1), kde L n - 1, tak l^^^ = L(»-i) Zložitost celého výpočtu je 6(n3 log n). Najkratšie cesty medzi všetkými dvojicami - násobenie matíc 194 All_Pairs_Shortest_Path(VF) i L& <- W 2 m <— 1 3 while m < n — 1 do 5 m <— 2m od 6 return L^ Najkratšie cesty medzi všetkými dvojicami - násobenie matíc 195 Floyd-Warshallov algoritmus Daný je orientovaný graf G = (V, H), V = {l,2,...,n}, s ohodnotením hrán w : H —» R a bez záporných cyklov. Predpokladáme, že graf je zadaný n x n maticou susednosti w = (wij)- Nech p =< i>i,i>2? • • • ?^z >i í > 2, je cesta v grafe. Vnútorné vrcholy cesty p sú vrcholy {^2,..., ^-i}- Pre lubovolnú dvojicu vrcholov i5j Gľ uvažujme všetky cesty z i do j, ktorých vnútorné vrcholy sú z množiny {1,2, ...,fc}, nech p je z nich najkratšia. Floydov - Warshallov algoritmus využíva vztah medzi touto množinou ciest z i do j a množinou ciest z i do j, ktorých vnútorné vrcholy sú z množiny {1, 2,... k — 1}. Najkratšie cesty medzi všetkými dvojicami - Floyd-Warshall 196 ak k nie je vnútorným vrcholom cesty p, tak najkratšia cesta z i do j s vnútornými vrcholmi z {1, 2,..., k — 1} je zároveň najkratšou cestou i do j s vnútornými vrcholmi z {1, 2,..., k} ak k je vnútorným vrcholom cesty p, tak cestu p môžeme rozdělit na i ^> k ^> j. Podlá Lemy 3 je p\ najkratšou cestou z i do fc s vnútornými vrcholmi z {1,2,..., k — 1}. Podobne p2 je najkratšou cestou z k do j s vnútornými vrcholmi z {1,2,...,fc- 1}. ,(fc) vrcholmi z množiny {1,2,..., fc}. Platí Označme cQ. dĺžku najkrašej cesty z i do j s s vnútornými (a,) def jwij ak k = 0 d" - \min(dr», dS»-1) + dg"") ak * > 1 Najkratšie cesty medzi všetkými dvojicami - Floyd-Warshall 197 Floyd- Warshall(VF) i lK°) <- W 2 for k = 1 to n 3 do for i = 1 to n 4 do for j = 1 to n dodí^minfdr^dr^+dg-") 6 od 7 od 8 od 9 return £)(n) Časová zložitost algoritmu je (9(n3). Najkratšie cesty medzi všetkými dvojicami - Floyd-Warshall 198 Konštrukcia najkratšej cesty s Spolu s maticou D dĺžok najkratších ciest počítame maticu ü predchodcov vrcholov na najkratšej ceste. Presnejšie, počítame postupnost matíc T\^\ II^1), . . . , Il(n) = II, kde 7r}. je definované ako predchodca vrchola j na najkratšej ceste z i do j s vnútornými vrcholmi z {1,2, ...,fc}. Hodnotu tt\• definujeme rekurzívně. Ak k = 0 tak najkratšia cesta z i do j neobsahuje žiaden vnútorný vrchol a preto (o) def j Nil ak i = j alebo Wíj = oo nij = i ak i t^ j a i^7- < oo Najkratšie cesty medzi všetkými dvojicami - Floyd-Warshall 199 Pre k > 1 rozlíšime dva prípady. • Ak najkratšia cesta obsahuje vnútorný vrchol k, tj. má tvar i ^ k ^> j, tak predchodca vrcholu j na tejto ceste je zhodný s predchodcom vrchola j na najkratšej ceste z k do j s vnutormými vrcholmi z množiny {1,..., k — 1}. • V opačnom prípade je predchodca vrcholu j zhodný s predchodcom vrchola j na najkratšej ceste z k do j s vnutormými vrcholmi z {1,..., k — 1}. (fc) def ry*-!) ak d (fe-l) ^ Ak-l) v > d ik + d (fe-i) kj (fe-l) | ,(fc-l) ^ j(fe-l) , j(fe-l) K^h äkdiJ -dik +dkj Najkratšie cesty medzi všetkými dvojicami - Floyd-Warshall 200 Johnsonov algoritmus Daný je orientovaný graf G = (V, H) s ohodnotením w : H —» R. Johnsonov algoritmus je založený na technike transformácie ohodnotenia hrán a využíva efektivitu Dijkstrovho algoritmu. Ak ohodnotenie všetkých hrán je nezáporné, tak pre každý vrchol použijeme Dijkstrov algoritmus. Ak G má hrany so záporným ohodnotením, tak zistíme, či graf má záporné cykly. Ak G nemá záporné cykly, tak ohodnotenia hrán transformujeme tak, aby ohodnotenia všetkých hrán boli nezáporné a pre každý vrchol použijeme Dijkstrov algoritmus. Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 201 Transformácia ohodnotenia hrán Nové ohodnotenie w musí splňat: 1. pre každé u, v G V platí, že p je najkratšia cesta z u do v pri ohodnotení w práve vtedy ak p je najkratšia cesta z u do v pri ohodnotení w 2. pre každú hranu (u,v) G íŕ platili/,?;) > 0. Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 202 Lema 7. Nech G = (V, H) je orientovaný graf s ohodnotením w : H —» R. A/ec/7 /z : 1/ -^ R j e lubovolná funkcia. Pre každú hranu (iz, v) E V definujeme w(u, v) = w(u, v) + h{u) — h(v). Potom pre každú cestu p z vo do v k platí: w(p) = S(vo,Vk) vtedy a len vtedy ak w(p) = č^o,^)1- Naviac, G pri ohodnotení w má záporný cyklus vtedy a len vtedy ak G pri ohodnotení w má záporný cyklus ô(vq, Vk) je dĺžka najkratšej cesty z vq do Vk pri ohodnotení w. Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 203 Dôkaz. Nech p =< v$, ^i? • • • ? ^fc >■ Potom k ^(p)= y]^(^i-i^i) = ^2(w(ví-!, Vi) + h{vi-x) - h(vi)) i=i = w(p) + h(v0) - h(vk) Preto ak p je najkratšia cesta z vo do ?;& pri ohodnotení w, tak je najkratšou cestou aj pri ohodnotení w a naopak. Nech c =< vo, ^i,..., Vfe >i ^o = vk> Je cyklus. Podobne odvodíme w(c) = w(c) + h(vo) — h(vk) = w(c). Z toho plynie druhé tvrdenie Lemy. □ Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 204 Cielom je rozhodnut, či graf má záporný cyklus a ak nie, tak zvolit funkciu h tak, aby hodnota w(u,v) bola pre každú hranu nezáporná. 1. Skonštruujeme G = (V, H) s ohodnotením w : H —» R, kde • iJ^tfUfts,!;) I i; G I/} • w(u,v) = w(u,v) pre (i/,?;) G ií a ?ž;(s,?;) = 0 pre vGľ Platí: • c je záporný cyklus v G <^> c je záporný cyklus v G • každý cyklus v G je dosiahnutelný z koreňa s • žiadna najkratšia cesta z u do v (u, v ^ s) neobsahuje vrchol s. Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 205 2. Definujeme h(v) = ô(s,v) pre v EV Pre každú (u, v) G H platí: /&(?;) < h (u) +w(u. w(u, v) = w(u, v) + h{u) — h(v) Pre každú (u, v) G H platí: w(u,v) > O Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus Johnson(G) i skonštruuj G = (V,ií)podla bodu 1. 2 if Bellman-Ford(G, w, s) = false 3 then graf má záporný cyklus 4 else foreach vrchol v G V 5 do h (v) <— 5(s,i>) (vypočítané alg. Bell.-Ford) od 6 foreach hranu (iz, v) G H 7 do w(u, v) <— w(u, v) + h{u) — h(v) od s foreach vrchol u G V o do Dijkstra(G, w, u) io foreach vrchol v G V u do duv <— S(u, v) + h(v) — h(u) u od od 13 fi u return D = (duv) Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 207 Zložitost Johnsonovho algoritmu zložitost algoritmu Bellman-Ford + V -krát zložitost Dijkstrovho alg. Ö{\V\'\H\) F|-0(1^1-log l^l + l/řl) ö{\V\2\og\V\ + \V\\H\) Pre riedke grafy je Johnsonov algoritmus efektívnejší než Floyd-Warshallov algoritmus. Najkratšie cesty medzi všetkými dvojicami - Johnsonov algoritmus 208 _________________Toky v sietiach_________________ Siet G = (V, H) je orientovaný graf, ktorého každá hrana (u, v) G H má nezápornú kapacitu (priepustnost) c(u,v) > 0. Ak (u, v) 0 H, kladieme c(u,v) = 0. Predpokladáme, že v sieti sú vyznačené dva vrcholy — zdroj s a ciel t a že všetky vrcholy grafu ležia na nejakej ceste z s do t. Tok v sieti G je funkcia /:ľxľ->R spĺňajúca Kapacitné ohraničenia f {u,v) < c(u,v) pre všetky iz, i; G V Podmienky symetrie f (u, v) = —f (v, u) pre všetky iz, i; G V Podmienky kontinuity pre všetky u 0}. Zlepšujúca cesta p je cesta z s do t v G f. Reziduálna kapacita cesty p je cf(p) — vcim{cf(u,v) | (u, v) leží na p}. Toky v sietiach - Ford-Fulkerson 212 Ford-Fulkersonov algoritmus FORD_FULKERSONOV_ALGORITMUS i for každú hranu (i/,, v) £ H do 2 f [U, V 3 od 0; /M<-0 4 while existuje zlepšujúca cesta p do 5 6 7 8 9 io od n return / cf(p) ^~ vcim{cf(u,v) | (u,v) leží nap} for každú hranu (i/,, v) na p do f [u, v] <- /[ix,i;] +c/(p) /[v,ix] <-----/[ix,i;] od Toky v sietiach - Ford-Fulkerson 213 kapacity tok |f| = 5 kapacity tok |f| = 8 Toky v sietiach - Ford-Fulkerson reziduálna siet reziduálne kapacity zlepšujúca cesta cf (P) S Q reziduálna siet reziduálne kapacity Korektnost Ford-Fulkersonovej metody Lema 8. Nech G je siet, f tok v G a p zlepšujúca cesta v G f Definujme funkciu fp : V x V —» R predpisom c f (p) ak (i/,, v) leží na ceste p fp(u,v) = ^ —Cf(p) ak (v, u) leží na ceste p 0 inak \ Potom fp je tok v G f a jeho hodnota je \fp\ = c f (p). Naviac f = f + fp je tok v G a jeho hodnota je \f\ > \f\. Dôkaz. Overíme, že fp v G j a f y G spĺňajú kapacitné ohraničenia a podmienky symetrie a kontinuity. D Toky v sietiach - Ford-Fulkerson 215 Rez (S, T) v sieti G je rozdelenie V na S a T také, že s (2) Plynie z Lemy 8. (2) => (3) Nech Gf nemá žiadnu zlepšujúcu cestu. Definujme S = {v G V | existuje cesta z s do v v G f} a T = V \ S. Rozdelenie (5, T) je rezom v G/. Pre každú dvojicu vrcholov u, v takú, žeu^Sav^T platí /(i/, i?) = c(iz, v) (v opačnom prípade by (u, v) G /r/) a teda f (S,T) = ^5, T). Podía Lemy 9 platí |/|=/(S, T). (3) =>* (1) Podlá Lemy 9 pre každý rez platí |/| < c(S,T). Rovnost l/l = c(S,T) preto implikuje maximalitu toku. □ Toky v sietiach - Ford-Fulkerson 217 Zložitost Ford-Fulkersonovho algoritmu Ak v sieti G s celočíselnými kapacitami je |/*| hodnota maximálneho toku, tak počet iterácií cyklu 2-6 je nanajvýš |/*|. Zložitost jednej iterácie je rovná zložitosti nájdenia cesty z s do t aječ?(|iř|). Celková zložitost je 0(\f H). Toky v sietiach - Ford-Fulkerson 218 Príklad grafu, pre ktorý zložitost Ford-Fulkersonovho algoritmu je \ľ\-0{\H\). Počiatočný tok má hodnotu |/| = 0. zlepšujúca cesta s,1,2,t => tok |/| = 1. zlepšujúca cesta s,2,1,t => tok |/| =2. zlepšujúca cesta s,1,2,t =>* tok |/| = 3. ... V prípade, že kapacity hrán sú iracionálne čísla, konečnost Ford-Fulkersonovej metódy nieje zaručená. Toky v sietiach - Ford-Fulkerson 219 Varianty Ford-Fulkersonovej metódy Líšia sa v spôsobe, akým sa vyberá zlepšujúca cesta. Algoritmus Edmonds-Karp Tok zväčšujeme vždy po najkratšej zlepšujúcej ceste (dĺžka cesty je rovná počtu hrán cesty). Zložitost algoritmu je Ö(|V| • \H ) pre grafy s lubovolnými kapacitami. Algoritmus najširších ciest Tok zväčšujeme vždy po zlepšujúcej ceste s maximálnou reziduálnou kapacitou. Zložitost algoritmu je (9(|1/|2 • |íŕ|ln|/*|) pre grafy s celočíslenými kapacitami. Algoritmus zjemňovania stupnice Ďalšie metódy: metóda "push-relabel" vedie k algoritmu zložitosti o(\v\3). Toky v sietiach - Ford-Fulkerson 220 Varianty problému maximálneho toku • Siete s násobnými zdrojmi a cielmi • Najlacnejší maximálny tok • Viacproduktové toky • Najpočetnejšie párovania Toky v sietiach - Ford-Fulkerson Vyhladavacie algoritmy Algoritmy pre vyhladavanie, porovnávanie a editaciu retazcov. Problémy • vyhladavanie vzorky v texte • vzdialenost retazcov a transformácia retazcov • spoločná podpostupnost • aproximácia retazcov • opakujúce sa podretazce Vyhladavacie algoritmy 222 Vyhíadávanie vzorky v texte Je daný text T a vzorka P - retazce nad abecedou E. Úlohou je vyhiadat všetky výskyty vzorky v texte. Text je daný ako pole T[l..n], vzorka ako P[l..m]. Hovoríme, že vzorka P sa vyskytuje v texte T s posunom s ak 0 < s < n — ma T [s + l..s + m] = P[l..m] (tj. T [s + j] = P[j] pre 1 < j < m). Číslo s uvedených vlastností sa nazýva platným posunom pre text T a vzorku P. Problém vyhladávania vzorky môžeme formulovat ako úlohu nájst pre dané T a P všetky platné posuny. String matching 3Pattern Vyhíadávanie vzorky v texte 223 Algoritmy Algoritmus Predspracovanie Vyhladávanie Úplné prehladavanie 0 O ((n — m + l)m) Karp-Rabin 0(m) O ((n — m + l)m) Konečné automaty O(mS) 6(n) Knuth-Morris-Pratt 0(m) 6(n) Boyer-Moore O ((n — m + l)m) Algoritmy Karp-Rabin a Boyer-Moore majú výrazne lepšiu priemernú zložitost Vyhladávanie vzorky v texte 224 Úplné prehladávanie Úplné_Prehladávanie(T, P) i for s = 0 to n — m do 2 if P[l..m] = T[s + 1..S + m 3 then print us je platný posun fi 4 od Zložitost: cyklus sa vykoná n — m + 1 krát v každom cykle sa na riadu 2 vykoná m porovnaní. Spolu ö((n — m + l)m) Vyhladávanie vzorky v texte - úplné prehladávanie 225 Algoritmus Karp-Rabin Predpokladajme, že S = {0,1,..., 9}4. Každý retazec nad abecedou S môžeme chápat ako číslo zapísané v desiatkovej sústave. Označme p číslo zodpovedjúce retazcu P[l..n] a ts čísla zodpovedajúce retazcom T[s + l..s + m]. Problém overit, či s je platným posunom sa redukuje na problém overit, či ts —p. Predspracovanie: výpočet čísla p Homérovou schémou (čas 0(m)) p = p[m]+io(P[m-l]+10(P[m-2]+. • - + 10(P[2] + 10P[1])...)) Výpočet čísla to - podobne ako p (čas 0(m)) Výpočet čísel ŕi,..., tn-m (čas 0(n — m)) ŕa+i = 10(ts - lO^Tjs + 1]) + T[s + m + 1] 4zobecnenie pre E = {0, 1, . . . , d} je priamočiare Vyhladávanie vzorky v texte - Karp-Rabin 226 Algoritmus Karp-Rabin so zvyškami Algoritmus Karp-Rabin sa nedá použit ak čísla p,ts sú príliš velké. V takom prípade sa používa výpočet modulo q, kde typicky q je prvočíslo také, že lOq « počítačové slovo. Test ts = p sa nahradí testom ts = p( mod q). Číslo s, pre ktoré platí uvedená rovnost je len potenciálnym posunom, jeho platnost sa musí overit porovnaním príslušných retazcov. Zložitost predspracovania je opát 0(m), zložitost výpočtu je v najhoršom prípade (tj. ak pre všetky s platí skúmaná rovnost) O ((n — m + l)m). Zložitost konkrétneho výpočtu je daná počtom platných posunov. Ak očakávaný počet platných posunov je c, tak očakávaná zložitost algoritmu je ö((n — m + 1) + cm). Vyhladávanie vzorky v texte - Karp-Rabin 227 Konečné automaty Pre danú vzorku P[l..m] skonštruujeme konečný automat A = ({0,...,m},E,5,{0},{m}). Text T[l..n] spracujeme automatom A. Finite_Automaton_Matcher(T, A) i q^O 2 for i = 1 to n do 3 q <— S(q,T[i]) 4 if q = m then print i — m je platný posun fi 5 od Zložitost spracovania textu je 9(ri). Konečné automaty 228 Konštrukcia automatu pre danú vzorku P Označenie: Pq = P[l] ■ ■ ■ P [q], Tq = T[l] ■■■[q] Definujeme sufixovú funkciu a : S* —> {0,1,..., m} kde a(x) je dĺžka najdlhšieho prefixu vzorky P, ktorý je sufixom slova x. Napr. pre P = popapopa je a (e) = 0, cr(papap) = 1, a(papop) = 3 a cr(popapo) = 6. Konečný automat pre P je A = ({0,..., m}, S, 5, {0}, {m}), kde prechodová funkcia 5 je definovaná predpisom 5(g,o) = a(Pg a) Konečné automaty 229 Algoritmus pre výpočet prechodovej funkcie automatu Automat(P, S) i for q = 0 to m do 2 for každé a G S do 3 k <— min(m + 1, q + 2) repeat k <— k — 1 until 4 5(g,o) od od return ô k Pk je sufixom Pa a Zložitost konštrukcie automatu: je (9(m3|S|); efektívnejšia procedúra zložitosti(9(m|S|). existuje Konečné automaty 230 Korektnost algoritmu Veta. Ak A je automat pre vzorku P a T je text, tak i = 0,1,...,n platí S(T^=a(Ti). Dôkaz. Indukciou vzhladom k i. 1. T0 = e a preto 5{T0) = 0 = a(T0). 2. Indukčný predpoklad - platnost tvrdenia pre i 5(Ti+1) = 5{Tio) nech T [i + 1] = a = 5(5(Ti), a) z definície 5 = (5(g, a) nech 5(7$) = q = s pre ktoré P[l..k] = T[sf + l..sf + k] kde sf + k = s + q. K výpočtu sf nepotrebujeme poznat text, pretože T[s' + l..s' + k] je prefixom vzorky. Pre danú vzorku P[l..m] definujeme prefixovú funkciu 7ľ : {1, 2,..., m} —» {0,1,... m — 1} predpisom def TT [q] = maxjfc | k < q a P& je sufixom Pq} Algoritmus Knuth-Morris-Pratt 233 R 9 R 6 A k r 0 k r 0 k r 0 k r 0 k r 0 k r 0 k y 7T "91 = 6 k r o k 7^f6] = 3 k r o k 7j{3] © (k y Algoritmus Knuth-Morris-Pratt 234 KMP(T,P) i TT <— PrefixovÁ_Funkcia(P); g <— O 2 for i = 1 to n do 3 while g > 0 A P[q + 1] ^ T [i] do g <— 7r[g] 4 if P[g + 1] = T[i] then g <- g + 1 f i 5 if g = m then i — m je platný posun ; g <- 6 od Prefixová_Funkcia(P) i tt[1] ^ 0; k <- 0 2 for g <— 2 to m do 3 while bOAP[fc + l]/ P[g] do 4 k <— 7v[k] od 5 if P[fc + 1] = P[q] then fc <- fc + 1 f i 6 7r[g] <— k od 7 return 7r Algoritmus Knuth-Morris-Pratt Počítame 7r[g], poznáme 7r[l],... , 7r[g — 1]. Nech n[q — 1] = k. k q-1 q P[l..k] =P[*..q- 1] akP[k + l] = [q] tak P[l..k + 1] = P[*..q] a ir[q\ = fc + 1 ak P[fc+ 1] t^ [g] tak hladáme iný prefix A taký, že A je sufixom Pq — kandidátom je práve 7v[k] (z rovnosti P[l..k] = P[*..q — 1] vyplýva, že aj sufixy týchto reazcov sa musia zhodovat). Preto testujeme P[7r[fc] + 1] = P[q]- V prípade nerovnosti postupujeme analogicky. Algoritmus Knuth-Morris-Pratt 236 Časová zložitost algoritmu Knuth-Morris-Pratt Pre PrefixovÁ_Funkcia použijeme metódu účtov. Každý for cyklus z riadkov 2-6 dostane 3 kredity. 2 kreditmi zaplatíme príkazy z riadkov 5 a 6. Zvyšný 1 kredit uložíme na účet. Pri každom vykonaní príkazu v riadku 4 sa zníži hodnota k, lebo 7v[k] < k. Súčasne je 7v[k] > 0 pre všetky k a preto počet opakovaní príkazu nie je väčší než počet ukončených opakovaní for cyklu. Všetky priradenia v riadku 4 preto môžeme zaplatit kreditmi z účtu. Zložitost výpočtu Prefixová_Funkcia je 6(m). Analogickým postupom sa ukáže, že zložitost algoritmu KMP je 9(n). Algoritmus Knuth-Morris-Pratt 237