ALM3 Mgr. Petr Osička, Ph.D. Update: 15. listopadu 2016

KMI/ALM3

´ matematika 3 Algoritmicka Mgr. Petr Osiˇcka, Ph.D.

Update: 15. listopadu 2016

Pˇ redn´ aˇ ska 1 ´ proble ´m Algoritmicky Definice 1. Abeceda Σ je koneˇcn´ a nepr´ azdn´ a mnoˇzina. Prvk˚ um Σ ˇr´ık´ame symboly. Slovo (ˇretˇezec) nad abecedou Σ je uspoˇr´ adan´ a sekvence znak˚ u z Σ. D´elka slova x ∈ Σ je d´elka t´eto sekvence. Mnoˇzinu vˇsech slov nad abecedou Σ oznaˇcujeme jako Σ∗ . Jazyk L nad Σ je libovoln´a podmnoˇzina Σ∗ . Pˇ r´ıklad 1. Mˇejme ΣBool = {0, 1}. Sekvence 0001, 1110, 00 jsou slovy nad touto abecedou, sekvence 12, #43k nejsou. Σ∗ je pak mnoˇzina {0, 1, 00, 01, 10, 11, 000, . . . }. Definice 2. Necht’ Σ je abeceda. Pak algoritmick´y probl´em definujeme jako dvojici hL, Ri, kde L ⊆ Σ∗ je mnoˇzina vstup˚ u (instanc´ı) a R je relace zachycuj´ıc´ı vztah mezi instancemi a spr´avn´ ymi v´ ysledky. Tedy pokud hx, yi ∈ R, pak y je spr´ avn´ ym ˇreˇsen´ım x. Form´ alnˇe je L ⊆ Σ∗ mnoˇzina zak´odov´an´ı instanc´ı pomoc´ı ˇretˇezc˚ u nad abecedou Σ, a R ⊆ Σ∗ × Σ∗ , v´ ysledky tak´e k´ odujeme pomoc´ı Σ. Pro uk´ azku si probl´em testov´ an´ı prvoˇc´ıselnosti uvedeme ve verz´ıch bez k´odov´an´ı pomoc´ı ˇretˇezc˚ u i s jeho k´ odov´ an´ım. (a) Bez pouˇzit´ı ˇretˇezc˚ u m˚ uˇzeme probl´em zav´est n´asledovnˇe. Mnoˇzina instanc´ı je d´ana {n | n ∈ N, n > 1}, spr´ avn´e ˇreˇsen´ı je ANO, pokud je n prvoˇc´ıslo, jinak NE. (b) Zavedeme-li k´ odov´ an´ı nad ΣBool takov´e, ˇze zak´odov´an´ım n je jeho z´apis ve dvojkov´e soustavˇe, k´odov´ an´ım ANO je slovo 1 a k´ odov´ an´ım NE je slovo 0, pak je probl´em pops´an pomoc´ı dvojice hL, Ri takov´e, ˇze: L = {x ∈ {0, 1}∗ | x je z´ apis ˇc´ısla n ve dvojkov´e soustavˇe, n ∈ N, n > 1} a hx, yi ∈ R pr´avˇe kdyˇz x je zak´ odov´ an´ım prvoˇc´ısla. Proˇc k´ odovat vstupy a v´ystupy? Velikost instance m˚ uˇzeme zav´est jako d´elku zak´odovan´ı dan´e instance. M˚ uˇzeme tak zachytit sloˇzitost algoritmu, kter´ a by jinak z´ ustala skryt´ a. Naivn´ı algoritmus pro test prvoˇc´ıselnosti (ten, kter´ y zkouˇs´ı dˇelitelnosti vˇsemi menˇs´ımi ˇc´ısly) m´a pro pˇr´ıpad (a) z pˇredchoz´ıho pˇr´ıkladu sloˇzitost O(n), protoˇze vstup n m´a velikost n. V pˇr´ıpadˇe zak´odov´an´ı pomoc´ı dvojkov´e soustavy m´ a algoritmus sloˇzitost exponenci´ aln´ı, protoˇze d´elka z´ak´odov´an´ı n je lg n. Pokud se v instanci probl´emu vyskytuje mnoˇzina ˇc´ısel, bereme ˇcasto jako velikost instance jejich poˇcet. Zanedb´ av´ ame tak ovˇsem velikost tˇechto ˇc´ısel. Nˇekter´e operace, o kter´ ych pˇri anal´ yze algoritmu pˇredpokl´ad´ame, ˇze maj´ı konstantn´ı sloˇzitost, maj´ı ve skuteˇcnosti pro velk´a ˇc´ısla sloˇzitost horˇs´ı (napˇr´ıklad sˇc´ıt´an´ı, porovn´av´an´ı na souˇcastn´em harwaru). Pokud zavedeme velikost instance jako d´elku zak´odov´an´ı, tomuto probl´emu se vyhneneme. ˇ ım vˇetˇs´ı ˇc´ıslo, ˇc´ım vˇetˇs´ı je d´elka jeho z´ C´ ak´ odov´an´ı a tedy i d´elka zak´odov´an´ı instance.

´m˚ Typy proble u Definice 3. Probl´em hL, Ri je rozhodovac´ım probl´emem, pokud je mnoˇzina vˇsech moˇzn´ ych v´ ysledk˚ u dvouprvkov´ a, tj |{y | (x, y) ∈ R pro x ∈ L}| = 2. Jeden z prvk˚ u t´eto mnoˇziny pak oznaˇcujeme jako rozhodnut´ı ANO, druh´ y z prvk˚ u jako rozhodnut´ı NE. Rozhodovac´ı probl´em je probl´emem zjiˇstˇen´ı, jestli dan´a instance m´a poˇzadovanou vlastnost. Pokud ji m´ a, oˇcek´ av´ ame odpovˇed’ ANO, pokud ji nem´ a, oˇcek´av´ame odpovˇed’ NE. Protoˇze R je v tomto pˇr´ıpadˇe jednoduch´e, m˚ uˇzeme probl´em reprezentovat pomoc´ı jazyka. Slova, kter´a k´oduj´ı instance, pro kter´e je odpovˇed’ ANO, do jazyka patˇr´ı, slova, kter´ a k´ oduj´ı instance, pro kter´e je odpovˇed’ NE, do jazyka nepatˇr´ı.

Pˇ r´ıklad 2. (a) Probl´em testov´ an´ı prvoˇc´ıselnosti je rozhodovac´ı probl´em. (b) Typick´ ym rozhodovac´ım probl´emem je probl´em splnitelnosti formul´ı v´ yrokov´e logiky v konjunktivn´ı norm´ aln´ı formˇe (CNF). Formule je v CNF, pokud je konjunkc´ı klausul´ı. Klausule je disjunkc´ı liter´ al˚ u, z nichˇz kaˇzd´ y je bud’ v´ yrokovou promˇennou nebo jej´ı negac´ı. Formule (x ∨ y) ∧ (y ∨ z) je v CNF, kdeˇzto formule (x ∧ y) ∨ (x → ˇ y) nen´ı v CNF. Kaˇzdou formuli v´ yrokov´e logiky lze pˇrev´est do CNF. Rekneme, ˇze formule ϕ je splniteln´ a, pokud existuje ohodnocen´ı v´ yrokov´ ych promˇenn´ ych takov´e, ˇze ϕ je pravdiv´a. Napˇr´ıklad formule (x ∨ y) je splniteln´ a, protoˇze pro ohodnocen´ı x = 1, y = 1 je pravdiv´a. Oproti tomu formule (x ∧ ¬x) splniteln´a nen´ı, protoˇze nen´ı pravdiv´ a pro ˇz´ adn´e ohodnocen´ı promˇenn´ ych. Probl´em splnitelnosti formul´ı v´ yrokov´e logiky, kter´ y oznaˇcujeme jako SAT, je probl´emem urˇcen´ı toho, zda je formule splniteln´a. Probl´em je tedy urˇcen jazykem {zak´ odov´ an´ı ϕ | ϕ je splniteln´ a formule v CNF}. Definice 4. Necht’ Σ je abeceda. Optimalizaˇcn´ı probl´em je ˇctveˇrice hL, sol, cost, goali, kde L ∈ Σ∗ je mnoˇzina instanc´ı dan´eho probl´emu, sol : L → P(Σ∗ ) je zobrazen´ı pˇriˇrazuj´ıc´ı instanci probl´emu mnoˇzinu jej´ıch pˇr´ıpustn´ ych ˇreˇsen´ı; cost : L × P(Σ∗ ) → Q je zobrazen´ı pˇriˇrazuj´ıc´ı kaˇzd´e instanci a pˇr´ıpustn´emu ˇreˇsen´ı t´eto instance jeho cenu; goal je bud’ minimum (pak mluv´ıme o minimalizaˇcn´ım probl´emu) nebo maximum (pak mluv´ıme o ˇ maximalizaˇcn´ım probl´emu). Rekneme, ˇze y ∈ sol(x) je optim´ aln´ım ˇreˇsen´ım instance x, pokud cost(x, y) = goal{cost(y, x) | x ∈ sol(x)}. Optimalizaˇcn´ı probl´em je probl´emem v´ ybˇeru ˇreˇsen´ı s nejlepˇs´ı cenou z mnoˇziny vhodn´ ych ˇreˇsen´ı dan´e instance. Vhodn´ a ˇreˇsen´ı obdrˇz´ıme pomoc´ı zobrazen´ı sol, cenu kaˇzd´eho z nich urˇcuje cost. Nakonec goal n´am ˇr´ık´a, jestli chceme naj´ıt to s nejvˇetˇs´ı nebo s nejmenˇs´ı cenou. ´ Pˇ r´ıklad 3. (a) Uloha batohu: je d´ ana mnoˇzina poloˇzek s r˚ uzn´ ymi v´ahami a kapacita batohu. Chceme nal´ezt takovou podmnoˇzinu poloˇzek, kter´ a se do batohu vejde (souˇcet vah tˇechto poloˇzek je nejv´ yˇse kapacita batohu). Souˇcasnˇe chceme batoh zaplnit co nejv´ıce, tedy hled´ame takovou mnoˇzinu poloˇzek, kter´a vede k nejvˇetˇs´ımu moˇzn´emu (menˇs´ımu neˇz kapacita) souˇctu. ´ Uloha batohu Instance:

{(b, w1 , . . . , wn ) | b, w1 , . . . , wn ∈ N}

Pˇr´ıpustn´ a ˇreˇsen´ı: Cena ˇreˇsen´ı:

sol(b, w1 , . . . , wn ) = {C ⊆ {1, . . . , n} | P cost(C, (b, w1 , . . . , wn )) = i∈C wi

C´ıl:

maximum

P i∈C

wi 6 b}

ˇ ısla wi odpov´ıdaj´ı objem˚ C´ um jednotliv´ ych pytl˚ u s p´ıskem, b je kapacita batohu. Pro instanci I = (b, w1 , . . . , w5 ), kde b = 29, w1 = 3, w2 = 6, w3 = 8, w4 = 7, w5 = 12, existuje jedin´e optim´aln´ı ˇreˇsen´ı C = {1, 2, 3, 5} s cenou cost(C, I) = 29. Lze snadno ovˇeˇrit, ˇze vˇsechna ostatn´ı pˇr´ıpustn´a ˇreˇsen´ı maj´ı menˇs´ı cenu. (b) Probl´em tˇr´ıdˇen´ı lze tak´e formulovat jako optimalizaˇcn´ı probl´em. Pro sekvenci prvk˚ u a = a1 , . . . , an a jejich uspoˇr´ ad´ an´ı 6 je poˇcet inverz´ı definov´ an jako Inv(a) = |{(ai , aj ) | i < j, ai  aj }|, tedy jako poˇcet dvojic prvk˚ u, kter´e jsou nejsou uspoˇr´ ad´ any ve spr´ avn´em poˇrad´ı. Pak je probl´em tˇr´ıdˇen´ı definov´an n´asledovnˇe: Probl´ em tˇ r´ıdˇ en´ı Instance:

a = a1 , . . . , an , uspoˇr´ad´an´ı 6

Pˇr´ıpustn´ a ˇreˇsen´ı:

sol(a) = mnoˇzina vˇsech permutac´ı prvk˚ u a1 , . . . , an

Cena ˇreˇsen´ı:

pro x ∈ sol(a) je cost(a, x) = Inv(x)

C´ıl:

minimum

Algoritmus dan´emu vstupu (instanci nˇejak´eho probl´emu) pˇriˇrazuje v´ ystup. Z vnˇejˇsku jej lze tedy ch´apat jako ˇ zobrazen´ı. Form´ alnˇe zap´ıˇseme fakt, ˇze algoritmus A pro vstup x vr´at´ı y jako A(x) = y. Rekneme, ˇze A ˇreˇs´ı probl´em hL, Ri pokud (x, A(x)) ∈ R pro kaˇzd´e x ∈ L, tedy pokud pro kaˇzdou instanci probl´emu vrac´ı A spr´ avn´e ˇreˇsen´ı. 2

U optimalizaˇcn´ıch probl´em˚ u, pro kter´e nezn´ ame efektivn´ı algoritmus pro nalezen´ı optim´aln´ıho ˇreˇsen´ı, se ˇcasto spokoj´ıme s algoritmem, kter´ y vrac´ı ˇreˇsen´ı pˇr´ıpustn´e–ne nutnˇe optim´aln´ı, ale souˇcasnˇe pracuje efektivnˇe. Takov´ y algoritmus naz´ yv´ ame aproximaˇcn´ım algoritmem.

ˇ ´ sloˇ Casov a zitost ˇ Casov´ a sloˇzitost (d´ ale jen sloˇzitost) algoritmu A je funkce T imeA : N → N pˇriˇrazuj´ıc´ı velikosti vstupn´ı instance poˇcet instrukc´ı, kter´e mus´ı algoritmus A bˇehem v´ ypoˇctu prov´est. Protoˇze obecnˇe nemus´ı algoritmus pro dvˇe r˚ uzn´e stejnˇe velk´e instance prov´est stejn´e mnoˇzstv´ı instrukc´ı, potˇrebujeme poˇcty instrukc´ı pro instance stejn´e velikosti nˇejak´ ym zp˚ usobem agregovat. ˇ Definice 5. Oznaˇcme si tA (x) poˇcet instrukc´ı, kter´e algoritmus A provede pro instanci x ∈ L. Casov´ a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe je definovan´ a T imeA (n) = max{tA (x) | x ∈ L, |x| = n}. Sloˇzitost v pr˚ umˇern´em pˇr´ıpadˇe je pak P T imeA (n) =

x∈L,|x|=n tA (x)

|{x | |x| = n}|

.

Jedn´ım z vyuˇzit´ı sloˇzitosti (mimo zˇrejm´e vyuˇzit´ı k porovn´an´ı algoritm˚ u) je rozdˇelen´ı probl´em˚ u na prakticky ˇreˇsiteln´e a na praktick´ y neˇreˇsiteln´e. Jak ovˇsem pˇriˇradit sloˇzitost k probl´emu? Definice 6. Necht’ U je algoritmick´ y probl´em. • O(g(n)) je horn´ım omezen´ım sloˇzitosti probl´emu U, pokud existuje algoritmus A ˇreˇs´ıc´ı U takov´ y, ˇze T imeA (n) ∈ O(g(n)). • ω(f(n)) je doln´ım omezen´ım sloˇzitosti probl´emu U, pokud pro kaˇzd´ y algoritmus B ˇreˇs´ıc´ı U plat´ı, ˇze T imeB (n) ∈ ω(f(n)) Za horn´ı omezen´ı sloˇzitosti probl´emu bereme sloˇzitost nejlepˇs´ıho zn´am´eho algoritmu. Nal´ezt doln´ı omezen´ı sloˇzitosti je oproti tomu mnohem komplikovanˇejˇs´ı. Mus´ıme totiˇz vylouˇcit existenci algoritmu se sloˇzitost´ı danou doln´ı hranic´ı nebo lepˇs´ı. To je netrivi´ aln´ı a pro naprostou vˇetˇsinu probl´em˚ u je takov´a hranice nezn´am´a (vylouˇc´ıme-li napˇr´ıklad hranici danou t´ım, ˇze algoritmus mus´ı pˇreˇc´ıst cel´ y vstup). Pˇr´ıkladem probl´emu, pro kter´ y je tato hranice zn´ am´ a je napˇr´ıklad tˇr´ıdˇen´ı porovn´av´an´ım, pro kter´e neexistuje algoritmus se sloˇzitost´ı lepˇs´ı neˇz O(n log n). Probl´emy rozdˇelujeme na prakticky ˇreˇsiteln´e a prakticky neˇreˇsiteln´e pomoc´ı jejich horn´ıho omezen´ı sloˇzitosti. Rozdˇelen´ı je n´ asleduj´ıc´ı – probl´em povaˇzujeme za praktick´ y ˇreˇsiteln´ y, pokud pro je jeho horn´ı omezen´ı sloˇzitost O(p(n)), kde p(n) je polynom. Tedy, probl´em je praktick´ y ˇreˇsiteln´ y, pokud pro nˇej existuje algoritmus s nejh˚ uˇre polynomickou sloˇzitost´ı. – ostatn´ı probl´emy povaˇzujeme za prakticky neˇreˇsiteln´e. Proˇc polynomick´ a sloˇzitost? Polynom je nejvˇetˇs´ı funkce, kter´ a neroste rychle.“ U tohoto d˚ uvodu pˇredpokl´ad´ame, ˇze stupeˇ n polynomu ” nebude extr´emnˇe velk´ y (napˇr. 100). U vˇetˇsiny zn´am´ ych algoritm˚ u s polynomickou sloˇzitost´ı, nen´ı stupeˇ n polynomu vyˇsˇs´ı neˇz 10. Druh´ ym d˚ uvodem je to, ˇze polynomy jsou uzavˇren´e vzhledem k n´asoben´ı (vyn´asoben´ım dvou polynom˚ u dostaneme zase polynom). Pokud uvnitˇr algoritmu A spouˇst´ıme nejv´ıˇse polynomick´ y poˇcet kr´ at algoritmus B s nejh˚ uˇre polynomickou sloˇzitost´ı, m´a tento algoritmus tak´e nejh˚ uˇre polynomickou sloˇzitost (pˇritom samozˇrejmˇe pˇredpokl´ ad´ ame, ˇze pokud bychom povaˇzovali sloˇzitost algoritmu B pˇri anal´ yze A za konstantu, bude sloˇzitost A m´ıt nejh˚ uˇre polynomickou sloˇzitost). V podstatˇe tedy m˚ uˇzeme efektivn´ı algoritmy skl´adat do sebe (analogicky vol´ an´ı funkc´ı pˇri programov´ an´ı) a z´ıskan´ y algoritmus bude tak´e efektivn´ı. 3

´ notace Asymptoticka Definice 7. O(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´e konstanty c a n0 takov´e, ˇze 0 6 g(n) 6 cf(n) pro vˇsechna n > n0 . Ω(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´e konstanty c a n0 takov´e, ˇze g(n) > cf(n) > 0 pro vˇsechna n > n0 . Θ(f(n)) je mnoˇzina vˇsech funkc´ı g(n) takov´ ych, ˇze existuj´ı kladn´ı konstanty c1 , c2 a n0 takov´e, ˇze 0 6 c1 f(n) 6 g(n) 6 c2 f(n) vˇsechna n > n0 . Z´ apis g(n) = O(f(n)) je pˇr´ıkladem tzv. jednostrann´e rovnosti (v n´asleduj´ıc´ıch u ´vah´ach lze zamˇenit Ω a Θ za O). Rovn´ıtko v n´ı interpretujeme jinak, neˇz je obvykl´e (coˇz je zˇrejm´e, na obou stran´ach rovnosti nejsou objekty stejn´eho typu). Korektnˇe by mˇel b´ yt vztah zaps´an jako g(n) ∈ O(f(n)), nicm´enˇe pouˇzit´ı rovn´ıtka se jiˇz zaˇzilo a stalo se de facto standardem. Pro pochopen´ı v´ yznamu rovnost´ı, ve kter´ ych se asymptotick´a notace nach´az´ı na lev´e i na prav´e stranˇe, si staˇc´ı uvˇedomit, ˇze v´ yraz, ve kter´em se tato notace nach´az´ı pˇredstavuje mnoˇzinu funkc´ı. Tedy napˇr´ıklad v´ yraz n3 + O(n) je mnoˇzina {n3 + f(n) | f(n) ∈ O(n)}. Protoˇze na obou stran´ ach = jsou mnoˇziny a jedn´a se o jednosmˇernou rovnost, interpretujeme = jako ⊆. Pro aritmetiku s mnoˇzinami funkc´ı plat´ı intuitivn´ı pravidla. Uv´aˇz´ıme-li mnoˇziny funkc´ı S a T , pak plat´ı S + T = {g + h | g ∈ S, h ∈ T }, S − T = {g − h | g ∈ S, h ∈ T }, S · T = {g · h | g ∈ S, h ∈ T }, S ÷ T = {g ÷ h | g ∈ S, h ∈ T }. Skl´ ad´ an´ı funkce s mnoˇzinou funkc´ı provedeme obdobnˇe, f(O(g(n))) = {f(h(n)) | h ∈ O(g(n))}. Napˇr´ıklad log O(n2 ) je mnoˇzina logaritm˚ u z funkc´ı omezen´ ych shora kvadrikou. Pokud jsou asymptotick´e v´ yrazy vnoˇreny, pak mnoˇziny sjednot´ıme, tedy napˇr´ıklad [ O(g(n) + O(f(n))) = {O(h) | h ∈ g(n) + O(f(n))}.

4

Rozdˇ el a panuj Z´ akladn´ı kostra algoritmu RaP pro vstup I je n´asleduj´ıc´ı: 1. Pokud je |I| < b pro pevnˇe danou konstantu b, je v´ ysledek trivi´aln´ı nebo jej poˇc´ıt´ame jin´ ym algoritmem. Algoritmus A tento v´ ysledek jenom vr´ at´ı. 2. Z instance I vygenerujeme instance I1 , I2 , . . . , Ik , takov´e, ˇze I > |Ii | pro vˇsechna 1 6 i 6 k. 3. Rekurzivnˇe zavol´ ame algoritmus A pro I1 , I2 , . . . , Ik . 4. V´ ysledky rekurzivn´ıch zavol´ an´ı zkombinujeme do v´ ysledku aktu´aln´ıho zavol´an´ı a tento v´ ysledek vr´at´ıme. V algoritmech realizuj´ıc´ıch techniku Rozdˇel a panuj m˚ uˇzeme rozpoznat dvˇe oddˇelen´e f´aze, kter´e ji dali n´ azev. Bˇehem prvn´ı f´ aze, kter´e ˇr´ık´ ame Rozdˇel, algoritmus vygeneruje mnoˇzinu menˇs´ıch instanc´ı. Bˇehem druh´e f´ aze, pojmenovan´e jako Panuj, sestav´ıme ze ˇreˇsen´ı vypoˇcten´ ych pro menˇs´ı instance ˇreˇsen´ı instance p˚ uvodn´ı. Pˇr´ıkladem algoritmu pouˇz´ıvaj´ıc´ı strategii rozdˇel a panuj je MergeSort (kter´ y jiˇz vˇsichni zn´ate). Algoritmus 1 Mergesort 1: procedure MergeSort(A, l, p) 2: if p < l then 3: q ← b(l + p)/2c 4: MergeSort(A, l, q) 5: MergeSort(A, q + 1, p) 6: Merge(A, l, q, p)

1:

. rozdˇel 2: . panuj

3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:

procedure Merge(A, l, q, p) n1 ← q − l + 1 n2 ← r − q for i ← 0 to n1 − 1 do L[i] ← A[l + 1] for i ← 0 to n1 − 1 do R[i] ← A[q + i + 1] L[n1 ] ← R[n2 ] ← ∞ i←j←0 for k ← l to p do if L[i] 6 R[j] then A[k] ← L[i] i←i+1 else A[k] ← R[j] j←j+1

´ za c ˇasove ´ sloˇ Analy zitosti D´ıky rekurzivn´ım zavol´ an´ım se sloˇzitost ned´ a vyj´adˇrit pˇr´ımo, ale mus´ıme ji vyj´adˇrit pomoc´ı rekurence. Oznaˇc´ımeli tuto sloˇzitost T(n), pak T (b) = Θ(1), T (|I|) =

k X

T (|Ik |) + f(|I|).

i=1

Pro instanci o velikosti menˇs´ı nebo rovno b je sloˇzitost´ı algoritmu konstanta (prvn´ı ˇr´adek kostry algoritmu). Pro zbyl´e instance algoritmus spoˇc´ıt´ a instance menˇs´ı (ˇr´adek 2) a kombinuje v´ ysledky rekurzivn´ıch zavol´an´ı (ˇr´ adek 4), sloˇzitost tˇechto ˇr´ adk˚ u je vyj´ adˇrena funkc´ı f(n). Abychom spoˇcetli sloˇzitost cel´eho algoritmu, mus´ıme jeˇstˇe P pˇriˇc´ıst sumu sloˇzitost´ı rekurzivn´ıch zavol´ an´ı, tedy sumu ki=1 T (|Ik |). Sloˇzitost chceme vyj´ adˇrit v uzavˇren´e formˇe, to je ve formˇe, kter´a neobsahuje rekurentn´ı vol´an´ı sebe sama“ ” na prav´e stranˇe rovnosti (hled´ an´ı uzavˇren´e formy se ˇr´ık´a ˇreˇsen´ı rekurence). Rekurence m˚ uˇzeme vyˇreˇsit pˇresnˇe, nebo–pokud je pˇresn´e ˇreˇsen´ı obt´ıˇzn´e– se spokoj´ıme s odhadem uzavˇren´e formy. V takov´em pˇr´ıpadˇe se spokoj´ıme s v´ ysledkem v asymptotick´e notaci. 5

´ rekurence 1: Hanojske ´ ve ˇˇ Snadna ze T (n) = 2T (n − 1) + 1 T (1) = 1

Hodnoty pro prvn´ıch p´ ar ˇc´ısel n

T(n)

1 2 3 4

1 3 7 15

Tipneme, ˇze T (n) = 2n − 1, pokus´ıme se v´ ysledek dok´azat indukc´ı. Pro n = 1 rovnost trivi´alnˇe plat´ı. Pˇredpokl´ adejme, ˇze plat´ı pro n − 1. Pak T (n) = 2T (n − 1) − 1 = 2(2n−1 − 1) = 2n − 1. ´ rekurence 2: Kra ´ jen´ı Pizzy Snadna T (0) = 1 T (n) = T (n − 1) + n Rekurenci rozvineme: T (n) = T (n − 1) + n = = T (n − 2) + (n − 1) + n = .. . = 1 + 1 + 2 + ··· + n = =1+

n(n + 1) 2

V´ ysledek jeˇstˇe dok´ aˇzeme indukc´ı. Pro n = 0 rovnost trivi´alnˇe plat´ı. Pˇredpokl´adejme, ˇze plat´ı pro n − 1, pak T (n) = T (n − 1) + n =

n(n − 1) n(n + 1) +1+n= +1 2 2

ˇn´ı metoda substituc Postup pro odhad pomoc´ı O notace (pro Ω notaci je postup analogick´ y): 1. Odhadneme uzavˇrenou formu pomoc´ı asymptotick´e notace, tj ˇze uzavˇren´a forma patˇr´ı do O(g(n)) pro nˇejakou funkci g(n). 2. Vybereme jednu funkci f(n) z asymptotick´eho odhadu, pˇri specifikaci funkce m˚ uˇzeme vyuˇz´ıt konstant. Pro tuto funkci indukc´ı dok´ aˇzeme, ˇze T (n) 6 f(n), ˇc´ımˇz dok´aˇzeme, ˇze T (n) = O(g(n)). Bˇehem d˚ ukazu lze zvolit vhodn´e hodnoty konstant.

6

Pˇ r´ıklad 1:

T (n) = T (bn/2c) + T (dn/2e) + 1 T (1) = 1 Odhadneme jako O(n). Vybereme funkci cn−b = O(n), c > 0, b jsou konstanty. Chceme dok´azat T (n) 6 cn−b pro nˇejak´e hodnoty konstant b, c. To udˇel´ ame indukc´ı. Indukˇcn´ı pˇredpoklady jsou: T (bn/2c) 6 c(bn/2c) − b T (dn/2e) 6 c(dn/2e) − b Dok´ aˇzeme nerovnost pro T (n). T (n) = T (bn/2c) + T (dn/2e) + 1 6 c(bn/2c) − b + c(dn/2e) − b + 1 6 cn − 2b + 1 = = cn − b + (−b + 1) Zvol´ıme b = 1 a t´ım dostaneme T (n) 6 cn − 1, coˇz jsme chtˇeli dok´azat. Zb´ yv´a ovˇeˇrit pˇr´ıpad, kdy n = 1. Nerovnost T (1) = 1 6 cn − 1 plat´ı pro jak´ehokoliv c > 2. Dohromady jsme dok´azali, ˇze T (n) 6 2n − 1 a tedy T (n) = O(n). Pˇ r´ıklad 2:

T (n) = 2T (bn/2c) + n T (1) = 1 Odhadneme je O(n lg n). Pokud vybereme funkci cn lg n m˚ uˇzeme dok´azat spr´avnost obecn´eho indukˇcn´ıho kroku pro c > 1 T (n) 6 2(cbn/2c lg(bn/2c) + n 6 cn lg(n/2) + n = cn lg n − cn lg 2 + n 6 cn lg n U okrajov´e podm´ınky ovˇsem naraz´ıme na probl´em. T (1) = 1 6= 1 lg 1 = 0 M˚ uˇzeme vyuˇz´ıt toho, ˇze dokazujeme asymptotick´ y odhad a nerovnost proto m˚ uˇze platit aˇz od urˇcit´eho n0 . Pro n > 3 uˇz T (n) nez´ avis´ı na T (1), ale staˇc´ı zn´at T (2) a T (3). Volbou n0 = 2 m˚ uˇzeme posunout“okrajovou ” podm´ınku smˇerem nahoru (ˇc´ımˇz pˇr´ıpad n = 1, kter´ y zp˚ usobuje probl´emy, z d˚ ukazu vypust´ıme) a nahradit okrajovou podm´ınku pomoc´ı T (2) = 4, T (3) = 5, s t´ım, ˇze nyn´ı mus´ı b´ yt c > 2.

7

f(n)

f(n)

f(n1 ) f(n2 )

1

f(nk )

+

1

1

Pk i=1

f(nk )

+ poˇcet list˚ u =

v´ ysledek

Obr´ azek 1: Idea metody odhadu pomoc´ı stromu rekurze

Odhad pomoc´ı stromu rekurze Metoda odhadu pomoc´ı stromu rekurze je zaloˇzen´a na jednoduch´e myˇslence. Rekurentn´ı vztah T (n) =

k X

T (ni ) + f(n).

i=1

si pˇredstav´ıme jako strom. Uzly stromu odpov´ıdaj´ı jednotliv´ ym rekurzivn´ım vol´an´ım.“ Kaˇzd´emu uzlu pˇriˇrad´ıme ” mnoˇzstv´ı pr´ ace, kterou pomysln´ y algoritmus pˇri dan´em vol´an´ı provede. Listov´e uzly tak budou m´ıt pˇriˇrazenu konstantu, kter´ a odpov´ıd´ a okrajov´ ym podm´ınk´am rekurentn´ıho vztahu. Mnoˇzstv´ı pr´ace vnitˇrn´ıch uzl˚ u pak odpov´ıd´ a aplikaci funkce f na argument dan´eho rekurzivn´ıho vol´an´ı. V koˇrenu tedy provedeme f(n) pr´ ace, v jeho i-t´em potomku pak f(ni ). Pˇrirozenˇe, pokud seˇcteme pr´aci pˇriˇrazenou vˇsem uzl˚ um, dostaneme ˇreˇsen´ı rekurence. Souˇcet provedeme ve dvou kroc´ıch. Nejdˇr´ıve pro kaˇzdou u ´roveˇ n stromu seˇcteme pr´aci provedenou v uzlech na on´e u ´rovni, pot´e seˇcteme sumy z jednotliv´ ych vrstev. Pˇ r´ıklad:

T (n) = 2T (n/4) + n2 T (1) = 1 Zaˇcnˇeme konstruovat strom rekurze. Koˇrenu pˇriˇrad´ıme n2 . Potomk˚ um koˇrene, kteˇr´ı odpov´ıdaj´ı T (n/4) pˇriˇrad´ıme (n/4)2 . Uzl˚ um v dalˇs´ı vrstvˇe, odpov´ıdaj´ıc´ım T (n/16) (rekurzivn´ı vol´an´ı s argumentem n/4) pˇriˇrad´ıme (n/16)2 . V prvn´ı vrstvˇe se nach´ az´ı 2 uzly, suma pr´ ace je tedy 2(n/4)2 , v druh´e vrstvˇe se nach´az´ı 4 uzly, suma je tedy 2 4(n/16) . Nyn´ı si m˚ uˇzeme vˇsimnout urˇcit´e pravidelnosti. Pr´ace, kterou provedeme v jednom uzlu v i-t´e vrstvˇe (koˇren je v nult´e vrstvˇe) odpov´ıd´ a (n/4i )2 , poˇcet uzl˚ u v i-t´e vrstvˇe je 2i , suma pˇres vˇsechny uzly v t´eto vrstvˇe i i 2 2 i je tedy 2 (n/4 ) = n /8 . Listy se nach´ azej´ı ve vrstvˇe log4 n, jejich poˇcet je tedy 2log4 n = n1/2 . Odvozen´ı tohoto: v´ıme, ˇze log2 n = a tedy log4 n = log2 nlog4 2 . Dosad´ıme do 2log4 n a dostaneme 2log2 n

log4 2

Pokud nyn´ı seˇcteme vˇsechny vrstvy, dostaneme X

log4 n−1

T (n) =

(n2 /8i ) + n1/2

i=0

X

log4 n−1

= n2

i=0

8

(1/8i ) + n1/2

= nlog4 2 .

log4 n log4 2

n2

n2

n2 16

n2 256

n2 16

n2 256

n2 256

1 1 1

n2 8

n2 256

n2 64

1 1 1

nlog4 2

Obr´ azek 2: Strom rekurze pro rekurenci T (n) = 2T (n/4) + n2 Abychom se zbavili z´ avislosti na n v sumˇe, nahrad´ıme ji sumou cel´e geometrick´e posloupnosti. Dostaneme tedy X

log4 n−1 2

T (n) = n

(1/8i ) + n1/2

i=0 ∞ X 6 n2 (1/8i ) + n1/2 i=0 2

=n

1 + n1/2 1 − 1/8

Odhad ˇreˇsen´ı rekurence je O(n2 ).

Master theorem Peˇcliv´e vyˇreˇsen´ı metody stromu pro specifick´ y druh rekurenc´ı d´a n´asleduj´ıc´ı vˇetu. Porovn´av´ame rychlost r˚ ustu strom (nlogb a je poˇcet list˚ u) s rychlost´ı r˚ ustu funkce f(n) (ze znˇen´ı vˇety). Vˇ eta 1. Necht’ a > 1 a b > 1 jsou konstanty a f(n) je funkce a T (n) je definovan´ a na nez´ aporn´ych cel´ych ˇc´ıslech pomoc´ı rekurence T (n) = aT (n/b) + f(n), pˇriˇcemˇz n/b interpretujeme jako bn/bc nebo dn/be. Pak m˚ uˇzeme T (n) n´ asledovnˇe asymptoticky omezit. 1. Pokud f(n) = O(nlogb a− ) pro nˇejak´e  > 0, pak T (n) = Θ(nlogb a ). 2. Pokud f(n) = Θ(nlogb a ), pak T (n) = Θ(nlogb a lg n). 3. Pokud f(n) = Ω(nlogb a+ ) pro nˇejak´e  > 0 a pokud af(n/b) 6 cf(n) pro konstantu 0 < c < 1 a vˇsechna dostateˇcnˇe velk´ a n, pak T (n) = Θ(f(n)).

´ na ´ soben´ı velky ´ ch c ˇ´ısel Rychle Jsou d´ ana dvˇe ˇc´ısla A a B (v bin´ arn´ım z´ apisu, cel´ y postup lze upravit pro z´apis ˇc´ısel v jak´ekoliv soustavˇe), a chceme spoˇc´ıtat A · B. Algoritmus n´ asoben´ı pod sebe ze z´akladn´ı ˇskoly m´a sloˇzitost O(n2 ). ˇ ıslo A je reprezentov´ano sekvenc´ı Pˇredpokl´ ad´ ame poziˇcn´ı reprezentaci kladn´ ych ˇc´ısel ve dvojkov´e soustavˇe. C´ Pn i bit˚ u an−1 an−2 . . . a0 (pro n, kter´e je mocninou 2) pokud plat´ı, ˇze A = zme ˇc´ısla A1 dan´e i=0 ai 2 . Uvaˇ

9

sekvenc´ı bit˚ u an−1 . . . an/2 a A2 dan´e sekvenc´ı bit˚ u an/2−1 . . . a0 . Pak plat´ı, ˇze A = A1 2n/2 + A2 . M˚ uˇzeme ps´ at AB = (A1 2n/2 + A2 )(B1 2n/2 + B2 ) = A1 B1 2n + (A1 B2 + B1 A2 )2n/2 + A2 B2 Mohli bychom navrhnout rekurzivn´ı algoritmus, kter´ y pro n-bitov´a ˇc´ısla A, B urˇc´ı A1 ,A2 , B1 , B2 (to jsou vˇsechno (n/2)-bitov´ a ˇc´ısla), rekurzivnˇe spoˇc´ıt´ a souˇciny A1 B1, A1 B2 , A2 B1 , A2 B2 a s jejich pomoc´ı pak spoˇcte v´ ysledek podle pˇredchoz´ıho vztahu. Rekurzi ukonˇc´ıme v momentˇe, kdy n´asob´ıme jednobitov´a ˇc´ısla. Protoˇze n´ asoben´ı mocninou dvou m˚ uˇzeme realizovat pomoc´ı bitov´eho posuvu, kter´ y m´a line´arn´ı sloˇzitost, a sˇc´ıt´an´ı ˇc´ısel m´ a tak´e line´ arn´ı sloˇzitost, je sloˇzitost navrhovan´eho algoritmu d´ana rekurenc´ı T (n) = 4T (n/2) + O(n) T (1) = O(1), jej´ımˇz ˇreˇsen´ım je Θ(n2 ). Abychom dos´ ahli algoritmu s menˇs´ı sloˇzitost´ı, mus´ım ubrat rekurzivn´ı zavol´an´ı. To m˚ uˇzeme prov´est d´ıky n´ asleduj´ıc´ı u ´vaze: A1 B2 + A2 B1 = A1 B2 + A2 B1 + A1 B1 − A1 B1 + A2 B2 − A2B2 = A1 B1 + A2 B2 + A1 (B2 − B1 ) + A2 (B2 − B1 ) = A1 B1 + A2 B2 + (A1 − A2 )(B2 − B1 ), a proto AB = A1 B1 2n + [A1 B1 + A2 B2 + (A1 − A2 )(B2 − B1 )]2n/2 + A2 B2 Nyn´ı staˇc´ı jenom tˇri rekurzivn´ı zavol´ an´ı, mus´ıme spoˇc´ıtat A1 B1 , A2 B2 a (A1 − A2 )(B2 − B1 ). Sloˇzitost algoritmu tak klesne na O(nlog2 3 ). Vzniklo nebezpeˇc´ı, ˇze budeme muset n´asobit z´aporn´a ˇc´ısla. To lze ale snadno obej´ıt t´ım, ˇze si nejdˇr´ıve spoˇc´ıt´ ame znam´enko v´ ysledku, a pak vyn´asob´ıme absolutn´ı hodnoty ˇc´ısel. Algoritmus 2 N´ asoben´ı velk´ ych ˇc´ısel 1: procedure Multiply(X,Y,n) 2: s ← sign(X) · sign(Y) 3: X ← abs(X) 4: Y ← abs(Y) 5: if n = 1 then 6: return X · Y · s 7: A ← ˇc´ıslo tvoˇren´e n/2 lev´ ymi bity X 8: B ← ˇc´ıslo tvoˇren´e n/2 prav´ ymi bity X 9: C ← ˇc´ıslo tvoˇren´e n/2 lev´ ymi bity Y 10: D ← ˇc´ıslo tvoˇren´e n/2 prav´ ymi bity Y 11: m1 ←Multiply(A, C, n/2) 12: m2 ←Multiply(A − B, D − C, n/2) 13: m3 ←Multiply(B, D, n/2) 14: return s · (shift(m1 , n) + shift(m1 + m2 + m3 , n/2) + m3 )

´ na ´ soben´ı polynom˚ Rychle u Souˇcin funkc´ı f a g je funkce f · g definovan´ a jako (f · g)(x) = f(x)g(x) pro kaˇzd´e x. ˇ ısl˚ Polynom je funkce A(x) = a0 + a1 x + a2 x2 + . . . . C´ um a0 , a1 , . . . ˇr´ık´ame koeficienty. Exponent nejvyˇsˇs´ı mocniny mezi ˇcleny s nenulov´ ym koeficientem je stupeˇ n polynomu. Pˇri z´apisu polynomu m˚ uˇzeme vˇsechny jeho ˇcleny s vyˇsˇs´ımi mocninami neˇz je jeho stupeˇ n vynechat. Souˇcin AB(x) polynom˚ u je definov´ an jako souˇcin funkc´ı. Algoritmus pro n´asoben´ı polynom˚ u rozn´asoben´ım z´ avorek m´ a sloˇzitost O(n2 ), kde n je maximum ze stupˇ n˚ u polynom˚ u. Polynomy totiˇz maj´ı maxim´alnˇe n + 1 ˇclen˚ u a n´ asob´ıme kaˇzd´ y ˇclen s kaˇzd´ ym. 10

Reprezentace polynom˚ u Polynom m˚ uˇzeme reprezentovat pomoc´ı posloupnosti jeho koeficient˚ u, tj. polynom A(x) = a0 + a1 x + a2 x2 + d · · · + ad x je lze reprezentovat jako [a0 , a1 , a2 . . . ad ] nebo [a0 , a1 , a2 . . . ad , 0, 0, 0] (napravo m˚ uˇzeme pˇridat tolik nul, kolik potˇrebujeme). Alternativn´ı reprezentace polynomu je d´ ana n´ asleduj´ıc´ı vˇetou. Vˇ eta 2. Polynom stupnˇe d je jednoznaˇcnˇe reprezentov´ an sv´ymi hodnotami v alespoˇ n d + 1 r˚ uzn´ych bodech. Polynom lze tedy reprezentovat i hodnotami tohoto polynomu v potˇredn´em poˇctu r˚ uzn´ ych bod˚ u. Tento poˇcet mus´ı b´ yt alespoˇ n tak velk´ y jako je poˇcet koeficient˚ u dan´eho polynomu, ale m˚ uˇze b´ yt vˇetˇs´ı. Mezi obˇema reprezentacemi m˚ uˇzeme pˇrech´ azet, jak je demostrov´ano na n´asleduj´ıc´ım obr´azku.

Vyhodnocen´ı Koeficienty a 0 , a1 , . . . , a d

Hodnoty

A(x0 ), A(x1 ), . . . , A(xd ) Interpolace

Pˇ r´ıklad: Polynom x3 +x+2 je reprezentov´ an pomoc´ı koeficient˚ u jako [2, 1, 0, 3]. Pro reprezentaci pomoc´ı hodnot mus´ıme zvolit alespoˇ n 4 r˚ uzn´e body, zvolme tedy 1, 2, 3, 4. Reprezentace hodnotami potom je [4, 12, 32, 70]. N´ asoben´ı v reprezentaci pomoc´ı hodnot M´ ame-li polynomy A a B reprezentov´ any hodnotami ve stejn´ych bodech, m˚ uˇzeme z´ıskat reprezentaci polynomu AB tak, ˇze reprezentace polynomu A a B po sloˇzk´ach vyn´asob´ıme. Tato operace m´a line´arn´ı sloˇzitost. Mus´ıme si ovˇsem d´ at pozor na to, aby v´ ysledn´ a reprezentace mˇela dostateˇcn´ y poˇcet poloˇzek. Tedy, pokud m´a A stupeˇ n s a B stupeˇ n t, m´ a AB stupeˇ n s + t, pak podle pˇredchoz´ı vˇety potˇrebujeme hodnoty polynomu AB v alespoˇ n s + t + 1 r˚ uzn´ ych bodech. Odtud plyne, ˇze i pro polynomy A a B mus´ıme m´ıt hodnoty v alespoˇ n t + s + 1 bodech. Idea algoritmu Algoritmus pro rychl´e n´ asoben´ı by mˇel pracovat n´asledovnˇe. Pro vstupn´ı polynomy A a B (stupˇ n˚ u s a t): 1. vybereme alespoˇ n s + t + 1 r˚ uzn´ ych bod˚ u a spoˇcteme hodnoty polynom˚ u A a B v tˇechto bodech. 2. pro kaˇzd´ y bod pak vyn´ asob´ıme hodnotu polynomu A v tomto bodˇe a hodnotu polynomu B v tomto bodˇe. Dostaneme tak hodnotu polynomu AB v tomto bodˇe. 3. z hodnot polynomu AB interpolujeme koeficienty a vr´at´ıme je jako v´ ysledek. Bod 2 lze prov´est s line´ arn´ı sloˇzitost´ı. Abychom dostali sloˇzitost lepˇs´ı neˇz O(n2 ), potˇrebujeme prov´est body 1. a 3. se sloˇzitost´ı lepˇs´ı neˇz O(n2 ). Vyhodnocen´ı polynomu a rychl´ a fourierova transformace Probl´em vyhodnocen´ı polynomu je n´ asleduj´ıc´ı: vstupem je polynom v reprezentaci pomoc´ı n koeficient˚ u. V´ ysledkem je jeho reprezentace pomoc´ı hodnot v n r˚ uzn´ ych bodech. Tyto body si m˚ uˇzeme zvolit libovolnˇe. Algoritmus, ve kter´em do polynomu pˇr´ısluˇsn´e hodnoty dosad´ıme a spoˇc´ıt´ame v´ ysledek, m´a sloˇzitost O(n2 ). Pro kaˇzd´ y bod totiˇz mus´ıme spoˇc´ıtat hodnoty O(n) ˇclen˚ u polynomu a bod˚ u je n. Pro naˇse u ´ˇcely je tedy tento algoritmus nevyhovuj´ıc´ı. Pro rychl´ y v´ ypoˇcet hodnot polynomu i interpolaci lze pouˇz´ıt Rychlou Fourierovu Transformaci (FFT). V dalˇs´ım budeme pˇredpokl´ adat, ˇze n je mocninou dvou. To n´as nijak neomezuje: (a) reprezentace pomoc´ı koefieficient˚ u m˚ uˇze rozˇs´ıˇr´ıt pˇrid´ an´ım nul na konec, (b) pro reprezentaci pomoc´ı hodnot m˚ uˇzeme pouˇz´ıt vˇetˇs´ı neˇz potˇrebn´ y poˇcet bod˚ u. Protoˇze body, pro kter´e chceme hodnoty polynomu spoˇc´ıtat si m˚ uˇzeme zvolit libovolnˇe, zvol´ıme body ±x0 , ±x1 , · · · ± xn/2−1 . 11

(1)

Pozdˇeji uvid´ıme, proˇc je takov´ a volba v´ yhodn´ a. Polynom rozdˇel´ıme na ˇcleny se sud´ ymi a s lich´ ymi mocninami A(x) = (a0 + a2 x2 + . . . ) + x(a1 + a3 x2 + . . . ) Vˇsimneme si, ˇze oba v´ yrazy v z´ avork´ ach jsou opˇet polynomy. V´ yraz (a0 + a2 x2 + . . . ) je polynom AS (z) = 2 a0 + a2 z + . . . , do kter´eho dosad´ıme x za z, a tedy (a0 + a2 x2 + . . . ) = AS (x2 ). Stejnou u ´vahou dostaneme pro polynom v prav´e z´avorce polynom AL (z) = a1 + a3 z + . . . , pro kter´ y plat´ı (a1 + a3 x2 + . . . ) = AL (x2 ). Polynomy AS a AL jsou reprezentov´ any n/2 koeficienty. Hodnoty polynomu A pro ±xi pak lze vyj´adˇrit jako A(xi ) = As (x2i ) + xi · Al (x2i ), A(−xi ) =

As (x2i )

− xi ·

Al (x2i ).

(2) (3)

Na vztaz´ıch vid´ıme, proˇc bylo v´ yhodn´e zvolit si dvojice opaˇcn´ ych bod˚ u. Plat´ı totiˇz, ˇze x2 = (−x)2 a tedy i 2 2 2 2 AS (x ) = AS ((−x) ) a AL (x ) = AL ((−x) ). K v´ ypoˇctu hodnot polynomu A v n bodech tedy potˇrebujeme vypoˇc´ıtat hodnoty polynom˚ u AS a AL v n/2 bodech. Na z´ akladˇe t´eto u ´vahy m˚ uˇzeme sestavit algoritmus, kter´ y pracuje n´asledovnˇe: 1. urˇc´ıme AS a AL 2. rekurzivnˇe spoˇc´ıt´ ame hodnoty polynom˚ u AS a AL v bodech x20 , x21 , . . . , x2n/2−1 . 3. pomoc´ı (2) a (3) spoˇcteme hodnoty polynomu A v bodech ±x0 , ±x1 , · · · ± xn/2−1 Pˇ r´ıklad Uvaˇzujme polynom 3x3 + 2x2 + x − 3. Pak algoritmus projde postupnˇe n´asleduj´ıc´ı strom polynom˚ u (AS vlevo, AL vpravo). Body, ve kter´ ych se hodnoty poˇc´ıtaj´ı jeˇstˇe neuvaˇzujeme. 3x3 + 2x2 + x − 3

2x2 − 3; As (z) = 2z − 3

AS (z) = −3 AL (z) = 2

x(3x2 + 1); AL (z) = 3z + 1

AS (z) = 1

AL (z) = 3

ˇ Reknˇ eme, ˇze v pˇredchoz´ım pˇr´ıkladˇe budeme cht´ıt spoˇc´ıtat hodnoty polynomu pro body ±x0 , ±x1 . Pˇri rekurzivn´ım vol´ an´ı pak mus´ıme spoˇc´ıtat hodnoty polynom˚ u (2z − 3) a (3z + 1) pro x20 a x21 . Probl´em je, ˇze x20 a x21 nemohou b´ yt opaˇcn´ a ˇc´ısla, protoˇze druh´e mocniny re´aln´ ych ˇc´ısel jsou vˇzdycky kladn´e. Abychom naˇsli takov´e body, jejichˇz druh´ a mocnina je z´ aporn´ a, mus´ıme pˇrej´ıt od re´aln´ ych ˇc´ısel ke komplexn´ım. Nejjednoduˇsˇs´ı je pˇr´ıpad, kdy je polynom stupnˇe 1 a hodnoty poˇc´ıt´ame pouze pro dvojici bod˚ u (kdyˇz je polynom jenom konstanta, je jeho hodnotou vˇzdy tato konstanta a tedy nem´a smysl volit body dvojici opaˇcn´ ych bod˚ u). Zvolme pro tuto u ´roveˇ n rekurze (tedy u ´roveˇ n stromu rekurze, na kter´e se vyskytuj´ı polynomy stupnˇe 1) body ±1. O u ´roveˇ n v´ yˇse (´ uroveˇ n, na kter´e se vyskytuj´ı polynomy stupnˇe 3) potˇrebujeme 2 p´ary bod˚ u, druh´a mocnina jednoho p´ aru se mus´ı rovnat 1, druh´ a mocnina druh´eho p´aru se mus´ı rovnat −1. Pˇrirozenˇe tyto body jsou ±1, ±i, kde i je imagin´ arn´ı jednotka. Opakov´ an´ım t´eto konstrukce z´ısk´ame body, pro kter´e potˇrebujeme spoˇc´ıtat hodnoty polynomu v koˇreni stromu rekurze (viz obr´ azek 3). Kaˇzd´ a z u ´rovn´ı stromu na obr´ azku 3 obsahuje pr´avˇe vˇsechny odmocniny z 1. Pˇresnˇ eji, je-li v dan´e u ´rovni n √ √ uzl˚ u, obsahuje pr´ avˇe vˇsechny n 1. Algoritmus FFT vyuˇz´ıv´a n´asleduj´ıc´ıch vlastnost´ı n 1. 12

(−

√ 2 2

+

√ 2 2 i)

(

√ 2 2

−

√ 2 2 i)

(−

−i

√ 2 2

−

√ 2 2 i)

(

√ 2 2

+

√ 2 2 i)

−i

1

−1

i

1

−1

i

1

−1 1

Obr´ azek 3: Idea nalezen´ı bod˚ u pro v´ ypoˇcet hodnoty polynomu pomoc´ı FFT. Potomci kaˇzd´eho uzlu jsou jeho druh´e odmocniny. Pro n = 2k plat´ı, ˇze (a) n-t´e odmocniny jedn´e jsou ω0 = 1, ω, ω2 , . . . , ωn−1 , kde ω = e

2πi n

.

n

(b) ω 2 +j = −ωj (c) Mnoˇzina druh´ ych mocnin

√ n 1 jsou pr´ avˇe {1, ω2 , (ω2 )2 , . . . , (ω2 )n/2−1 }, tedy n/2-t´e odmocniny 1.

√ Tyto vlastnosti n´ am umoˇzn ˇuj´ı iterovat pˇres vˇsechny n 1. Staˇc´ı spoˇc´ıtat ω a pak iterovat pˇres jej´ı mocniny. Konec iterace pozn´ ame podle toho, ˇze se dostaneme na hodnotu 1. Napˇr´ıklad pro n = 4 je ω√= i a jednotliv´e mocniny jsou postupnˇe ω2 = −1, ω3 = −i, ω4 = 1. Vlastnost (b) ˇr´ık´a, ˇze mnoˇzina vˇsech n 1 tvoˇr´ı opravdu dvojice opaˇcn´ ych bod˚ u a k jejich nalezen´ı staˇc´ı iterovat pouze pˇres polovinu mocnin. Druh´a polovina jsou pr´ avˇe opaˇcn´e body. Napˇr´ıklad pro n = 4 m´ ame ω = i a opaˇcn´ y bod je ω1+2 = ω3 = −i, pro ω2 = −1 je opaˇcn´ y bod ω2+2 = ω4 = 1. D´ıky (c) v rekurzivn´ıch vol´ an´ıch skuteˇcnˇe poˇc´ıt´ame s druh´ ymi mocninami bod˚ u. Algoritmus 3 Rychl´ a Fourierova transformace 1: procedure FFT(A[0, . . . , n − 1], ω) 2: if ω = 1 then 3: return A 4: for i ← 0 to n/2 − 1 do 5: AS [i] ← A[i · 2] 6: AL [i] ← A[i · 2 + 1] 7: S ← FFT(AS , ω2 ) 8: L ← FFT(AL , ω2 ) 9: x←1 10: for j ← 0 to n/2 − 1 do 11: R[j] ← S[j] + x · L[j] 12: R[j + n/2] ← S[j] − x · L[j] 13: x←x·ω 14: return R

. n je mocnina dvou . V tomto pˇr´ıpadˇe uˇz |A| = 1 . Koeficienty pro sud´e mocniny . Koeficienty pro lich´e mocniny

. Zaˇc´ın´ame od ω0 . Rovnice (2) . Rovnice (3) . Dalˇs´ı mocnina ω

Sloˇzitost FFT vyj´ adˇr´ıme pomoc´ı rekurence. V algoritmu jsou dvˇe rekurzivn´ı vol´an´ı, kaˇzd´emu z nich pˇred´av´ ame instanci o velikosti n/2. Zb´ yvaj´ıc´ı ˇc´ ast algoritmu (tedy cykly na ˇr´adc´ıch 4 aˇz 6 a 10 az 13) m´a sloˇzitost O(n). Rekurence je tedy T (n) = 2T (n/2) + O(n) T (1) = O(1) Podle master theoremu je pak sloˇzitost FFT vyj´adˇrena Θ(n log n). Pˇripomeˇ nme si, ˇze algoritmus pˇr´ım´ ym dosazen´ım do polynomu m´ a sloˇzitost O(n2 ). Nyn´ı si m˚ uˇzeme uk´ azat rychl´ y algoritmus pro n´asoben´ı polynom˚ u. Necht’ A a B jsou polynomy, kter´e chceme n´ asobit se stupni s a t. V´ ysledn´ y polynom AB bude m´ıt stupeˇ n s+t. Abychom tedy mohli interpolovat z hodnot 13

v´ ysledn´eho polynomu jeho koeficienty, potˇrebujeme jich zn´at nejm´enˇe s + t + 1. Pro potˇreby FFT ovˇsem mus´ı b´ yt poˇcet hodnot mocninou dvou, proto je skuteˇcnˇe poˇc´ıtan´ y poˇcet hodnot roven n = 2dlog2 (s+t+1)e , tedy nejbliˇzˇs´ı vˇetˇs´ı mocninˇe dvou. Algoritmus nejdˇr´ıve vol´a FFT, aby spoˇc´ıtal hodnoty A a B v n bodech, pot´e tyto body vyn´ asob´ı a z´ısk´ a hodnoty v tˇechto bodech pro AB. Posledn´ım krokem je interpolace koeficient˚ u. √ D´ıky vlastnostem n 1 ji lze vypoˇc´ıtat tak´e pomoc´ı FFT. Pro hodnoty AB(ω0 ), AB(ω), AB(ω2 ), . . . , AB(ωn−1 ) dostaneme koeficienty ab0 , ab1 , . . . , abn−1 pomoc´ı [ab0 , ab1 , . . . , abn−1 ] =

1 FFT([AB(ω0 ), AB(ω), AB(ω2 ), . . . , AB(ωn−1 )], ω−1 ). n

Algoritmus 4 Rychl´e n´ asoben´ı polynom˚ u 1: procedure FastPolyMultiply(A[0, . . . , s], B[0, . . . , t]) 2: n ← 2dlog2 (s+t+1)e 2πi 3: ω←e n 4: Doplˇ n pomoc´ı nul A i B na n prvk˚ u. 5: VA ←FFT(A, ω) 6: VB ←FFT(B, ω) 7: for i ← 0 to n − 1 do 8: VAB [i] ← VA [i] · VB [i] 9: return n1 FFT(VAB , ω−1 )

. Nuly pˇrid´av´am na konec . Hodnoty pro A . Hodnoty pro B . N´asoben´ı polynom˚ u . Interpolace pomoc´ı FFT

Sloˇzitost FastPolyMultiply je O(n log n). Algoritmus tˇrikr´at vol´a FFT se sloˇzitost´ı O(n log n). Zbyl´e ˇc´ asti maj´ı sloˇzitost O(n). Celkovˇe je tedy sloˇzitost dominov´ana FFT.

14

Dynamick´ e programov´ an´ı Jak dynamick´e programov´ an´ı funguje? Princip demonstrujeme na probl´emu v´ ypoˇctu n-t´eho Fibonacciho ˇc´ısla. Je to pˇr´ıklad specifick´ y v tom, ˇze ukazuje princip dynamick´eho programov´ an´ı v kontrastu k principu rozdˇel a panuj. Nen´ı ovˇsem obecn´e pravidlo, ˇze dynamick´e programov´ an´ı lze pouˇz´ıt pouze na probl´emy, pro kter´e princip rozdˇel a panuj vede k neefektivn´ımu algoritmu. Viz kapitola Proˇc dynamick´e programov´ an´ı funguje. Pˇripomeˇ nme si, ˇze Fibonacciho ˇc´ısla je definov´ana n´asleduj´ıc´ım rekurentn´ım vztahem F(n − 1) + F(n − 2) n > 2 F(n) = n n ∈ {0, 1}

(4)

Nab´ız´ı se pouˇz´ıt algoritmus rozdˇel a panuj, kter´ y n´asleduje Algoritmus 5 n-t´e Fibonacciho ˇc´ıslo pomoc´ı rozdˇel a panuj 1: procedure FibDQ(n) 2: if n = 0 or n = 1 then 3: return n 4: return FibDQ(n − 1) + FibDQ(n − 2) Sloˇzitost FibDQ m˚ uˇzeme vyj´ adˇrit jako rekurenci T (n) = T (n − 1) + T (n − 2) + O(1), odhadem jej´ıhoˇz ˇreˇsen´ı je O(2n ) (lze snadno vidˇet metodou stromu). Algoritmus m´a tedy velmi nev´ yhodnou sloˇzitost. Pokud si visualizujeme strom rekurzivn´ıho vol´an´ı, zjist´ıme, ˇze probl´em je v opakovan´em vol´an´ı procedury pro stejn´ y argument, viz. obr´ azek 4 (a). Probl´em odstran´ıme tak, ˇze si pro kaˇzd´e ˇc´ıslo, pro kter´e jednou zavol´ ame FibDQ, zapamatujeme v´ ysledek, kter´ y vr´atil. Pˇri opakovan´em rekurzivn´ım vol´an´ı pro tuto podinstanci zapamatovanou hodnotu pouˇzijeme. Algoritmus 6 n-t´e Fibbonaciho ˇc´ıslo s pamatov´an´ım si meziv´ ysledk˚ u 1: procedure PrepareTable(n) 2: t[0] ← 0 3: t[1] ← 1 4: for i ← 2 to n do 5: t[i] ← −1 6: return t 7: 8: 9:

procedure FibHelp(n, t) if t[n] = −1 then 10: t[n] ←FibTab(n − 1) + FibTab(n − 2) 11: return t[n] 12: 13: 14:

procedure FibTab(n) return FibHelp(n, PrepareTable(n))

Sloˇzitost FibTab je line´ arn´ı. Lze snadno vidˇet, ˇze k rekurzivn´ımu vol´an´ı na ˇr´adku 10 dojde pro kaˇzd´e ˇc´ıslo (a tedy pro kaˇzdou podinstanci) maxim´ alnˇe jedenkr´at. Ve zbyl´ ych pˇr´ıpadech je vr´acena v tabulce zapamatovan´ a hodnota. Strom rekurzivn´ıch vol´ an´ı pak vypad´a jako na obr´azku 4 (b). Sloˇzitost algoritmu m˚ uˇzeme jeˇstˇe zlepˇsit: ˇcasovou sloˇzitost o faktor 2, kter´ y z pohledu asymptotick´e notace nezanedbateln´ y (dostaneme ale mnohem hezˇc´ı algoritmus); pamˇet’ovou sloˇzitost zlepˇs´ıme z line´arn´ı (velikost tabulky) na konstantn´ı. Pozorov´ an´ı z pˇredchoz´ıho pˇr´ıkladu: 1. Omez´ıme opakovan´y v´ypoˇcet pro stejn´e instance, ke kter´emu doch´az´ı u pˇr´ıstupu rozdˇel a panuj tak, ˇze si v´ ysledky pamatujeme (napˇr´ıklad v tabulce). 15

F(6)

F(6)

F(5)

F(4)

F(4)

F(3) F(2)

F(1)

F(3)

F(2)

F(2)

F(1) F(0) F(1)

F(3) F(1)

F(0)

F(2)

F(1)

F(1)

F(5)

F(4)

F(2) F(1)

F(3)

F(0)

F(0)

F(2)

F(1)

F(4)

F(3)

F(2)

F(1)

F(1)

(a) FibDQ

(b) FibTab

Obr´ azek 4: Rekurzivn´ı strom vol´an´ı v´ ypoˇctu Fibbonaciho ˇc´ısla 2. instance, kter´e se v pr˚ ubˇehu v´ypoˇctu vyskytnou, vhodnˇe uspoˇr´ ad´ ame. Oznaˇcme jako Ii . Ij situaci, kdy k v´ ypoˇctu v´ ysledku instance Ij potˇrebujeme zn´at ˇreˇsen´ı instance Ii . Dynamick´e programov´an´ı m˚ uˇzeme pouˇz´ıt pouze tehdy, pokud v mnoˇzinˇe vˇsech instanc´ı uspoˇr´adan´e podle . nejsou cykly. To znamen´ a, ˇze neexistuje ˇz´ adn´ a instance, k jej´ımuˇz v´ ypoˇctu potˇrebujeme zn´at v´ ysledek j´ı samotn´e. Situaci lze visualizovat pomoc´ı orientovan´eho grafu. Za vrcholy grafu vezmeme vˇsechny instance, z Ii vede hrana do Ij pr´avˇe kdyˇz Ii . Ij . Pak lze dynamick´e programov´ an´ı pouˇz´ıt, pr´avˇe kdyˇz nejsou v tomto grafu cykly. Graf bez cykl˚ u totiˇz lze linearizovat. To znamen´ a, ˇze nalezneme takov´e line´arn´ı uspoˇr´ad´an´ı 6 instanc´ı, ˇze pro kaˇzd´e dvˇe instance plat´ı, ˇze pokud Ii . Ij , pak i Ii 6 Ij . Graf odpov´ıdaj´ıc´ı 6 je pak ˇretˇez. Situace je demonstrov´ ana na obr´ azku 5. 3. Instance ˇreˇs´ıme od nejmenˇs´ı podle jejich line´arn´ıho uspoˇr´ad´an´ı. Pˇredchoz´ı bod zajiˇst’uje, ˇze vˇzdy zn´ ame ˇreˇsen´ı vˇsech instanc´ı, kter´e jsou k sestaven´ı ˇreˇsen´ı pro aktu´aln´ı instanci potˇreba. 4. Ze vstupn´ı instance jsme schopni naj´ıt nejmenˇs´ı instance, pˇresnˇeji pro takov´e, kter´e jsou podle . minim´ aln´ı (v grafu do nich nevede ˇz´ adn´ a hrana). Toto je potˇreba, abychom mohli v´ ypoˇcet spustit. Hledat dalˇs´ı instance nen´ı nutn´e, lze je sestavovat aˇz v pr˚ ubˇehu v´ ypoˇctu. Proˇc dynamick´e programov´ an´ı funguje? Pokud pro v´ ypoˇcet v´ ysledku pro instanci I potˇrebujeme zn´at v´ ysledky instanc´ı Ij (pro nˇejak´a j, tˇechto instanc´ı m˚ uˇze b´ yt v´ıce), tak se ˇreˇsen´ı instance I pˇrekr´yv´ a s ˇreˇsen´ımi instanc´ı Ij . Napˇr´ıklad pro probl´em Fibonacciho ˇc´ısel: F(2) = F(0) + F(1) = 0 + 1 F(3) = F(1) + F(2) = 1 + (0 + 1) F(4) = F(2) + F(3) = (0 + 1) + (1 + (0 + 1)) F(5) = F(3) + F(4) = [1 + (0 + 1)] + [(0 + 1) + (1 + (0 + 1))] Algoritmus 7 n-t´e Fibonacciho ˇc´ıslo pomoc´ı dynamick´eho programov´an´ı 1: procedure FibIdeal(n) 2: if n = 0 then 3: return n 4: a←0 5: b←1 6: for n ← 2 to n − 1 do 7: c←a+b 8: a←b 9: b←c

16

c

d

a b

b

c

a

e

d

b

c

a

e

d

e

(a) Orientovan´ y graf bez cykl˚ u

(b) Line´ arn´ı uspoˇr´ ad´ an´ı vrchol˚ u

(c) Jeden z moˇ zn´ ych pr˚ ubˇ eh˚ u v´ ypoˇ ctu

Obr´ azek 5: Linearizovan´a podoba grafu F(5) se pˇrekr´ yv´ a s F(4) a F(3) (pˇrekr´ yv´ a se i s menˇs´ımi instancemi, to ale pro v´ ypoˇcet F(5) nen´ı podstatn´e). V pr˚ ubˇehu v´ ypoˇctu, kdy poˇc´ıt´ ame smˇerem od menˇs´ıch instanc´ı k vˇetˇs´ım (ve smyslu grafu z´avislost´ı mezi instancemi, viz obr´ azek 5), m˚ uˇzeme vyuˇz´ıt ˇreˇsen´ı menˇs´ıch instanc´ı (kter´e uˇz m´ame spoˇc´ıtan´e) jako ˇc´asti ˇreˇsen´ı vˇetˇs´ıch instanc´ı.

´ Uloha batohu ´ Uloha batohu (KNAPSACK), jej´ıˇz definice n´ asleduje, je optimalizaˇcn´ım probl´emem. Form´alnˇe je u ´loha batohu urˇcena n´ asledovnˇe: ´ Uloha batohu Instance:

{(b, w1 , . . . , wn ) | b, w1 , . . . , wn ∈ N}

Pˇr´ıpustn´ a ˇreˇsen´ı: Cena ˇreˇsen´ı:

sol(b, w1 , . . . , wn ) = {C ⊆ {1, . . . , n} | P cost(C, (b, w1 , . . . , wn )) = i∈C wi

C´ıl:

maximum

P i∈C

wi 6 b}

Pro instanci I = (b, w1 , . . . , w5 ), kde b = 29, w1 = 3, w2 = 6, w3 = 8, w4 = 7, w5 = 12, existuje jedin´e optim´ aln´ı ˇreˇsen´ı C = {1, 2, 3, 5} s cenou cost(C, I) = 29. Lze snadno ovˇeˇrit, ˇze vˇsechna ostatn´ı pˇr´ıpustn´a ˇreˇsen´ı maj´ı menˇs´ı cenu. Uvaˇzujme vstupn´ı instanci I = (b, w1 , . . . , wn ). Jako I(i, c), kde 0 6 i 6 n a 0 6 c 6 b, oznaˇc´ıme instanci (c, w0 , . . . , wi ). Pˇritom plat´ı, ˇze I = I(n, b) Mezi optim´ aln´ımi ˇreˇsen´ımi instanc´ı I(i, c) s i > 0 plat´ı: 1. Pokud poloˇzka i nepatˇr´ı do optim´ aln´ıho ˇreˇsen´ı instance I(i, c), pak je toto ˇreˇsen´ı shodn´e s optim´aln´ım ˇreˇsen´ım instance I(i − 1, c). 2. Pokud poloˇzka i patˇr´ı do optim´ aln´ıho ˇreˇsen´ı instance I(i, c) (a tedy nutnˇe plat´ı wi > c), pak toto ˇreˇsen´ı obdrˇz´ıme tak, ˇze k optim´ aln´ımu ˇreˇsen´ı instance I(i − 1, c − wi ) pˇrid´ame poloˇzku i. Pokud zn´ ame optim´ aln´ı ˇreˇsen´ı instanc´ı I(i − 1, c) a I(i − 1, c − wi ), m˚ uˇzeme spoˇc´ıtat optim´aln´ı ˇreˇsen´ı instance I(i, c). K tomu mus´ıme rozhodnout, jestli poloˇzka i do tohoto ˇreˇsen´ı patˇr´ı. To m˚ uˇzeme udˇelat na z´akladˇe cen optim´ aln´ıch ˇreˇsen´ı instanc´ı I(i − 1, c) a I(i − 1, c − wi ). Oznaˇcme jako OPT (i, c) cenu optim´aln´ıho ˇreˇsen´ı instance I(i, j). Pak plat´ı: 1. Pokud poloˇzka i do optim´ aln´ıho ˇreˇsen´ı nepatˇr´ı, pak OPT (i, c) = OPT (i − 1, c) 2. Pokud poloˇzka i do optim´ aln´ıho ˇreˇsen´ı patˇr´ı, pak OPT (i, c) = OPT (i − 1, c − wi ) + wi .

17

Pokud wi > c, pak poloˇzku i do ˇreˇsen´ı nem˚ uˇzeme d´at, protoˇze se tam nevejde. Jinak se rozhodneme na z´akladˇe toho, kter´e z ˇc´ısel OPT (i − 1, c) a OPT (i − 1, c − wi ) + wi je vˇetˇs´ı. Protoˇze u ´loha batohu je maximalizaˇcn´ı probl´em, vybereme tu moˇznost, kter´ a vede k ˇreˇsen´ı s vˇetˇs´ı cenou. Z pˇredchoz´ıho jde vidˇet, ˇze instance lze uspoˇr´ adat bez cykl˚ u. Plat´ı totiˇz, ˇze I(i − 1, c − wi ) . I(i, c) a souˇcasnˇe I(i − 1, c) . I(i, c). Minim´ aln´ı prvky vzhledem k tomuto uspoˇr´ad´an´ı jsou vˇzdycky • I(0, d) pro nˇejakou kapacitu d, coˇz odpov´ıd´a instanci, kde nem´ame ˇz´adn´e poloˇzky pro vkl´ad´an´ı do batohu. • I(i, 0) pro nˇejak´e i, coˇz odpov´ıd´ a pr´ azdn´e kapacitˇe (a nem´a cenu ˇreˇsit, kter´e prvky z w1 , . . . , wi−1 d´ am do ˇreˇsen´ı, protoˇze kapacita je pr´ azdn´ a) Algoritmus m˚ uˇzeme rozdˇelit do dvou ˇc´ ast´ı: 1. Spoˇc´ıt´ am OPT (i, j) pro 0 6 i 6 n a 0 6 c 6 b a v´ ysledky uloˇz´ım do tabulky. 2. Na z´ akladˇe tabulky spoˇc´ıt´ am optim´ aln´ı ˇreˇsen´ı. Z cen optim´ aln´ıho ˇreˇsen´ı instanc´ı I(i − 1, c) a I(i − 1, c − wi ) dostaneme cenu optim´aln´ıho ˇreˇsen´ı instance I(i, c): max(OPT (i − 1, c), OPT (i − 1, c − wi ) + wi ) pokud wi 6 c OPT (i, c)) = (5) OPT (i − 1, c) jinak D´ ale pro minim´ aln´ı prvky plat´ı, ˇze cost(I(0, d)) = 0 (nem´am prvky, kter´e bych do ˇreˇsen´ı zaˇradil) a cost(I(i, 0)) = 0 (pr´ azdn´ a kapacita a nem˚ uˇzu do ˇreˇsen´ı zaˇradit ˇz´adn´e prvky). Nyn´ı si uˇz m˚ uˇzeme napsat algoritmus, s pomoc´ı kter´eho spoˇc´ıt´ame cenu ˇreˇsen´ı I(n, b). Algoritmus si vytv´ aˇr´ı tabulku, jej´ıˇz ˇr´ adky odpov´ıdaj´ı jednotliv´ ym poloˇzk´am, kter´e chceme vloˇzit do batohu, uvaˇzujeme i jeden ˇr´ adek odpov´ıdaj´ıc´ı ˇz´ adn´e poloˇzce. Sloupce tabulky odpov´ıdaj´ı ˇc´ısl˚ um 0, 1, . . . , b, tedy vˇsem ˇc´ısl˚ um potenci´alnˇe se vyskytuj´ıc´ım jako kapacita nˇekter´e instance. Na m´ısto v tabulce na ˇr´adku odpov´ıdaj´ıc´ım poloˇzce i a ˇc´ıslu c spoˇc´ıt´ ame cenu optim´ aln´ıho ˇreˇsen´ı instance I(i, c). To m˚ uˇzeme tak, ˇze prvn´ı ˇr´adek a prvn´ı sloupec vypln´ıme nulami. Pot´e m˚ uˇzeme po ˇr´ adc´ıch doplˇ novat dalˇs´ı m´ısta tabulky podle vztahu (5). Nakonec na m´ıstˇe odpov´ıdaj´ıc´ım I(n, b) je cena ˇreˇsen´ı vstupn´ı instance I(n, b). Zb´ yv´ a si ˇr´ıci, jak nal´ezt skuteˇcn´e ˇreˇsen´ı, nikoliv jeho cenu. Toho lze dos´ahnout zpˇetn´ ym inˇzen´ yrstv´ım“ vztahu ” (5). Vezmeme cenu I(n, b), pokud b−wn < 0, pak n do ˇreˇsen´ı nepatˇr´ı a posuneme se k podinstanci I(n−1, b); v opaˇcn´em pˇr´ıpadˇe se pod´ıv´ ame na ceny x = OPT (n − 1, b − wn ) a y = OPT (n − 1, b). Pokud plat´ı, ˇze x + wn > y, pak wn do ˇreˇsen´ı patˇr´ı, pokud x + wn < y, pak wn do ˇreˇsen´ı nepatˇr´ı. Jsou-li si x a y rovny, m˚ uˇzeme zvolit jak chceme. Postup pot´e opakujeme pro tu podinstanci, jej´ıˇz cena byla vˇetˇs´ı. KnapsackDP vytv´ aˇr´ı tabulku o rozmˇerech n · b. Pro vyplnˇen´ı kaˇzd´eho pol´ıˇcka je potˇreba konstantn´ı poˇcet operac´ı. Sloˇzitost nalezen´ı ˇreˇsen´ı v hotov´e tabulce je je line´arn´ı vzhledem k n. M˚ uˇzeme tedy konstatovat, ˇze sloˇzitost algoritmu je O(n · b). Sloˇzitost algoritmu tedy nen´ı z´avisl´a jenom na velikosti instance mˇeˇren´e jako poˇcet ˇc´ısel w1 , . . . , wn , ale i na velikosti nejvˇetˇs´ıho ˇc´ısla se v instanci vyskytuj´ıc´ıho. Toto je zaj´ımav´a vlastnost. Pokud bychom napˇr´ıklad vyn´ asobili vˇsechna ˇc´ısla v instanci, kterou jsme si uvedli jako pˇr´ıklad, milionem, KnapsackDP by poˇc´ıtal ˇreˇsen´ı milionkr´ at d´ele. Intuitivnˇe bychom vˇsak ˇrekli, ˇze obˇe dvˇe instance jsou stejnˇe komplikovan´e.

18

´ Algoritmus 8 Uloha batohu pomoc´ı dynamick´eho programov´an´ı 1: procedure KnapsackDP(w1 , . . . , wn , b) 2: for i ← 0 to b do 3: M[0, i] ← 0 4: for i ← 0 to n do 5: M[i, 0] ← 0 6: for i ← 1 to n do 7: for c ← 1 to b do 8: if c < wi then 9: M[i, c] ← M[i − 1, c] 10: else 11: M[i, c] ← max(M[i − 1, c], M[i − 1, c − wi ] + wi ) 12: S←∅ 13: c←b 14: for i ← n to 0 do 15: if c − wi > 0 and M[i − 1, c] < M[i − 1, c − wi ] + wi then 16: S ← S ∪ {i} 17: c ← c − wi 18: return S

´ n´ı nejkratˇ Hleda s´ıch cest v grafu Definice 8. Cesta z uzlu s do uzlu t v orientovan´em grafu G je posloupnost vrchol˚ u a hran P = u0 , e0 , . . . , en−1 , un takov´ a, ˇze ei = (ui−1 , ui ), u0 = s, un = t, a kaˇzd´ y uzel u ∈ P se vyskytuje v cestˇe pr´avˇe jednou. Definice 9. Cena c(P) cesty P v ohodnocen´em grafu (G = (V, E), c) je suma ohodnocen´ı vˇsech hran vyskytuj´ıc´ıch se v cestˇe. Definice 10. Nejkratˇs´ı cesta z uzlu s do uzlu t v grafu G je takov´a cesta P, pro kterou plat´ı, ˇze c(P) 6 c(R) pro kaˇzdou cestu R z uzlu s do uzlu t. Nalezen´ı nejkratˇ s´ı cesty Instance:

orientovan´ y graf (G = (V, E), c), s, t ∈ V

Pˇr´ıpustn´ a ˇreˇsen´ı:

sol(G, s, t) = {P | P je cesta z uzlu s do uzlu t}

Cena ˇreˇsen´ı:

cost(P, G, s, t) = c(P)

C´ıl:

minimum

Floyd-Warshall algoritmus Vrcholy grafu oznaˇc´ıme V = {1, 2, . . . , n}. Jako I(i, j, k) oznaˇc´ıme instanci, s n´asleduj´ıc´ımi vlastnostmi: • Grafem je podgraf grafu G indukovan´ y vrcholy {1, . . . , k} ∪ {i, j}. Podgraf grafu G indukovan´ y mnoˇzinou vrchol˚ u F je graf s mnoˇzinou vrchol˚ u F a vˇsemi hranami z grafu G, kter´e maj´ı oba koncov´e vrcholy v mnoˇzinˇe F. • Poˇc´ ateˇcn´ı vrchol je i, c´ılov´ y vrchol je j. Cenu optim´ aln´ıho ˇreˇsen´ı I(i, j, k) oznaˇc´ıme jako OPT (i, j, k). Optim´aln´ı ˇreˇsen´ı instance I(i, j, k) m˚ uˇzeme urˇcit na z´ akladˇe n´ asleduj´ıc´ı u ´vahy. Pokud je nejkratˇs´ı cesta pro I(i, j, k) rozd´ıln´a (tj. kratˇs´ı) neˇz nejkratˇs´ı cestav pro I(i, j, k − 1), pak mus´ı nutnˇe v´est pˇres uzel k a plat´ı OPT (i, j, k) = OPT (i, k, k − 1) + OPT (k, j, k − 1),

19

protoˇze nov´ a cesta se skl´ ad´ a z cesty z uzlu i do uzlu k a z cesty z uzlu k do uzlu j. Pokud tedy zn´ame nejkratˇs´ı cesty (a jejich ceny) pro instance I(s, t, k − 1) pro vˇsechna s a t, m˚ uˇzeme rozhodnout o tom, jestli nejkratˇs´ı cesta pro I(s, t, k) vede pˇres uzel k. Je tomu tak, pr´ avˇe kdyˇz plat´ı, ˇze OPT (i, k, k − 1) + OPT (k, j, k − 1) < OPT (i, j, k − 1).

(6)

V tomto pˇr´ıpadˇe je totiˇz cesta, kterou obdrˇz´ıme spojen´ım optim´aln´ıho ˇreˇsen´ı instanc´ı I(i, k, k − 1) a I(k, j, k − 1), kratˇs´ı neˇz cesta, kter´ a nevede pˇres uzel k. Mus´ıme se vyrovat se situac´ı, kdy cesta z i do j v instanci I(i, j, k) neexistuje. Udˇel´ame to n´asledovnˇe: pokud cesta z i do j v instanci I(i, j, k) neexistuje, pak nastav´ıme OPT (i, j, k) = ∞. Pˇri re´aln´e implementaci nahrad´ıme ∞ nˇejak´ ym dostateˇcnˇe velk´ ym ˇc´ıslem, napˇr´ıklad ˇc´ıslem vˇetˇs´ım neˇz suma ohodnocen´ı vˇsech hran v grafu. Plat´ı pak, ˇze pokud OPT (i, j, k) = ∞, cesta mezi i a j neexistuje, protoˇze vˇsechny cesty v grafu maj´ı menˇs´ı cenu. Pˇredstavme si nyn´ı situaci, kdy cesta v instanci I(i, j, k − 1) neexistuje, tedy plat´ı OPT (i, j, k − 1) = ∞. Pak • Pokud OPT (i, k, k − 1) 6= ∞ a OPT (k, j, k − 1) 6= ∞ pak nerovnost (6) plat´ı, a najdeme cestu. • Ve vˇsech zb´ yvaj´ıc´ıch pˇr´ıpadech nerovnost neplat´ı a dostaneme, ˇze OPT (i, j, k) = ∞. Nerovnost (6) se tedy chov´ a spr´ avnˇe vzhledem k neexistuj´ıc´ım cest´am. Z pˇredchoz´ı diskuze je vidˇet, ˇze instance lze uspoˇr´adat podle tˇret´ı komponenty: k v´ ypoˇctu pro instanci I(, , k), potˇrebujeme zn´ at ˇreˇsen´ı instanc´ı I(, , k − 1). Minim´aln´ı prvky jsou pak instance I(i, j, 0). Pokud existuje hrana mezi uzly i a j, m´ ame OPT (i, j, 0) = c((i, j)), jinak nastav´ıme OPT (i, j, 0) = ∞. Algoritmus 9 Nejkratˇs´ı cesty v grafu 1: procedure Floyd-Warshall(G = (V, E), c) 2: for i ← 1 to n do: 3: for j ← 1 to n do: 4: D[i, j] = ∞ 5: P[i, j] = ∞ 6: for (i, j) ∈ E do: 7: D[i, j] = c((i, j)) 8: for k ← 1 to n do: 9: for i ← 1 to n do: 10: for j ← 1 to n do: 11: x ← D[i, k] + D[k, j] 12: if x < D[i, j] then 13: D[i, j] ← x 14: P[i, j] ← k 15: return hD, Pi 16: 17: 18: 19:

procedure GetPath(P,i,j) mid ← P[i, j] if mid = ∞ then 20: return [] 21: else 22: return GetPath(P, i, mid) + [mid]+GetPath(P, mid, j)

. i a j jsou spojeny jednou hranou

. + je zˇretezen´ı seznam˚ u

Algoritmus Floyd-Warshall pro vstupn´ı graf s n uzly vr´at´ı matici D o velikosti n × n, kde je na pozici (i, j) cena nejkratˇs´ı cesty mezi uzly i a j. D´ ale vrac´ı matici P o rozmˇerech n × n, kter´a na pozici (i, j) obsahuje uzel, pˇres kter´ y nejkratˇs´ı cesta z i do j vede. Tuto matici pot´e vyuˇz´ıv´a procedura GetPath, kter´a s jej´ı pomoc´ı cestu sestav´ı. Lze snadno vidˇet, ˇze algoritmus m´ a kubickou sloˇzitost Algoritmus nefunguje pro grafy, kter´e obsahuj´ı tzv. z´aporn´e cykly. Z´aporn´ y cyklus je takov´ y cyklus, jehoˇz suma hran je menˇs´ı neˇz 0. Opakov´ an´ım tohoto cyklu m˚ uˇzeme z´ıskat potenci´alnˇe nekoneˇcn´ y tah. Z´aporn´ y cyklus lze detekovat tak, ˇze zkontrolujeme diagon´ alu matice D. Pokud se na n´ı nach´az´ı z´aporn´e ˇc´ıslo, leˇz´ı uzel, kter´ y dan´emu m´ıstu v matici odpov´ıd´ a, na z´ aporn´em cyklu. 20

´m obchodn´ıho cestuj´ıc´ıho Proble ´ Probl´em si lze pˇredstavit n´ asledovnˇe. Je d´ ana mnoˇzina mˇest a pro kaˇzd´a dvˇe mˇesta vzd´alenost mezi nimi. Ukolem je nal´ezt takov´e uspoˇr´ ad´ an´ı mˇest, ˇze pokud je v tomto poˇrad´ı navˇst´ıv´ıme a pak se vr´at´ıme do poˇc´ateˇcn´ıho mˇesta, uraz´ıme nejkratˇs´ı moˇznou vzd´ alenost. Probl´ em obchodn´ıho cestuj´ıc´ıcho Instance:

u ´pln´ y neorientovan´ y graf s mnoˇzinou uzl˚ u V = {c1 , . . . , cn } a ohodnocen´ım hran δ

Pˇr´ıpustn´ a ˇreˇsen´ı:

kruˇznice (cyklus) proch´azej´ıc´ı pˇres vˇsechny uzly (tzv. Hamiltonovy kruˇznice)

Cena ˇreˇsen´ı:

souˇcet ohodnocen´ı hran na dan´e kruˇznici

C´ıl:

minimum

Algoritmus vyuˇz´ıv´ a n´ asleduj´ıc´ıho poznatku. Pokud pro kaˇzd´ y uzel c ∈ V − {c1 } oznaˇc´ıme cenu nejkratˇs´ı cesty z c1 do c vedouc´ı pˇres vˇsechny uzly jako OPT [V − {c1 }, c], pak jistˇe m˚ uˇzeme cenu optim´aln´ı cesty obchodn´ıho cestuj´ıc´ı nal´ezt jako min {OPT [V − {c1 }, c] + δ(c, c1 ) | c ∈ V − {c1 , c}} . Oznaˇcme jako S libovolnou nepr´ azdnou podmnoˇzinu mnoˇziny V − {c1 }. Jako OPT [S, c] oznaˇc´ıme d´elku nejkratˇs´ı cesty zaˇc´ınaj´ıc´ı v uzlu c1 , proch´ azej´ıc´ı vˇsemi uzly v S a konˇc´ıc´ı v uzlu c (pˇriˇcemˇz pˇredpokl´ad´ame, ˇze c ∈ S). Hodnotu OPT [S, c] m˚ uˇzeme spoˇc´ıtat podle n´ asleduj´ıc´ıho vztahu  δ(c1 , c) pokud |S| = 1 (tj. S = {c}), (7) OPT [S, c] = min {OPT [S − {c}, cj ] + δ(cj , c) | cj ∈ S − {c}} jinak. Prvn´ı ˇr´ adek pˇredchoz´ıho vztahu je trivi´ aln´ı. Z uzlu c1 do uzlu c existuje jenom jedna cesta (hrana z c1 do c) a jej´ı d´elka je δ(c1 , c). Ve druh´em ˇr´ adku pˇredpokl´ad´ame, ˇze zn´ame d´elky nejkratˇs´ıch cest z c1 do cj pro kaˇzd´e cj (tyto cesty vedou pˇres vˇsechny uzly v mnoˇzinˇe S − {c}). Tedy nevedou pˇres c. Kaˇzdou z takov´ ych cest m˚ uˇzeme prodlouˇzit na cestu z c1 do c (ted’ cesta vede pˇres uzly v S) tak, ˇze pˇrid´ame hranu z cj do c. Z takto vznikl´ ych cest (pro kaˇzd´ y uzel ci m´ ame jednu) vybereme tu nejkratˇs´ı (tj. ve vztahu urˇc´ıme jej´ı cenu). Pˇredchoz´ı u ´vahy vedou k n´ asleduj´ıc´ımu algoritmu k v´ ypoˇctu ceny optim´aln´ı cesty obchodn´ıho cestuj´ıc´ıho. Vlastn´ı cestu lze urˇcit pomoc´ı pamatov´ an´ı si uzlu cj , pro kter´ y byl druh´ y ˇr´adek (7) minim´aln´ı, pro kaˇzdou dvojici S, c a pot´e zpˇetn´e projit´ı tabulky (analogicky pˇredchoz´ım dvˇema algoritm˚ um). Algoritmus 10 Probl´em obchodn´ıho cestuj´ıc´ıho 1: procedure DynamicTSP(V = {c1 , . . . , cn }, δ) 2: for all c ∈ V − {c1 } do 3: OPT [{c}, c] = δ(c1 , c) 4: for j ← 2 to n − 1 do 5: for all S ⊆ V − {c1 } such that |S| = j do 6: for all c ∈ S do 7: OPT [S, c] = min {OPT [S − {c}, d] + δ(d, c) | d ∈ S − {c}} 8: return min{OPT [V − {c1 }, c] + δ(c, c1 ) | c ∈ V − {c1 }} Protoˇze algoritmus proch´ az´ı vˇsechny podmnoˇziny mnoˇziny V − {c1 } a pro kaˇzdou z nich provede operace se sloˇzitost´ı omezenou O(n2 ), je sloˇzitost algoritmu O(n2 2n ).

21

3

5

3

3

5

1

1 4

2

4

1

3 (a) Ohodnocen´ y graf

1

1

3

2

1

3

(b) Kostra s cenou 11

3

(c) Kostra s cenou 12

(d) Neni kostra

Obr´ azek 6: Pˇr´ıklady pojm˚ u z definice 11.

Greedy algoritmy Algoritmus navrˇzen´ y touto technikou proch´ az´ı pˇri sv´em bˇehu s´eri´ı voleb, pˇri kaˇzd´e z nichˇz vyb´ır´a tu moˇznost, kter´ a je v moment´ alnˇe nejlepˇs´ı (formulace toho, co znamen´a nejlepˇs´ı z´aleˇz´ı na konkr´etn´ım probl´emu). Volba nen´ı zaloˇzena na jej´ıch moˇzn´ ych d˚ usledc´ıch pro dalˇs´ı bˇeh algoritmu, je zaloˇzena pouze na jej´ı cenˇe v momentˇe volby. Odtud poch´ az´ı oznaˇcen´ı greedy (ˇzrav´e) algoritmy. Algoritmus bez rozmyslu, ˇzravˇe, vyb´ır´a tu aktu´ alnˇe nejlepˇs´ı moˇznost. Obecn´e sch´ema greedy algoritmu se d´ a shrnout do n´asleduj´ıc´ıch krok˚ u: 1. Pro vstupn´ı instanci I algoritmus provede volbu x a na jej´ım z´akladˇe vytvoˇri jednu menˇs´ı instanci I 0 . (Volba x je v tomto popisu abstraktn´ı pojem, v re´aln´em algoritmu to je re´aln´ y objekt, napˇr. hrana grafu, ˇc´ıslo, mnoˇzina, posloupnost bit˚ u apod.) ˇ sen´ı, kter´e z´ısk´ame pro I 0 pak zkombinujeme s volbou x 2. Algoritmus pot´e rekurzivnˇe aplikujeme na I 0 . Reˇ z pˇredchoz´ıho kroku a obdrˇz´ıme tak ˇreˇsen´ı pro I. 3. Rekurze konˇc´ı v okamˇziku, kdy je vstupn´ı instance dostateˇcnˇe mal´a. Protoˇze rekurze ve naznaˇcen´em sch´ematu je koncov´a (a je to tedy v podstatˇe jenom cyklus), lze algoritmus jednoduˇse pˇrev´est do iterativn´ı verze. Algoritmus pak tedy iterativnˇe prov´ad´ı kroky 1 a 2, pˇriˇcemˇz si zapamatuje jednotliv´e volby z kroku 1 a zkombinuje je do ˇreˇsen´ı aˇz po ukonˇcen´ı cyklu (tedy v momentˇe, kdy uˇz zpracov´av´ ame dostateˇcnˇe malou podinstanci a rekurze by uˇz skonˇcila). Nˇekdy lze jednotliv´e volby kombinovat do ˇreˇsen´ı pr˚ ubˇeˇznˇe (napˇr. pokud je ˇreˇsen´ım mnoˇzina prvk˚ u a volby v jednotliv´ ych kroc´ıch jsou prvky t´eto mnoˇziny).

´ ln´ı kostra grafu Minima Definice 11. Necht’ G = (V, E) je neorientovan´ y spojit´ y graf. Ohodnocen´ı hran grafu G je zobrazen´ı c : E → Q pˇriˇrazuj´ıc´ı hran´ am grafu jejich racion´ aln´ı hodnotu, c(e) je pak ohodnocen´ı hrany e ∈ E. Dvojici (G, c) ˇr´ık´ ame hranovˇe ohodnocen´ y graf. Kostra grafu G je podgraf G 0 = (V, E 0 ) (G 0 m´ a stejnou mnoˇzinu uzl˚ u jako G!) takov´ y, ˇze (a) G 0 neobsahuje kruˇznici, (b) G 0 je spojit´ y graf. Pro kaˇzdou dvojici uzl˚ u u, v plat´ı, ˇze mezi nimi existuje cesta Cena kostry G 0 = (V, E 0 ) v ohodnocen´em grafu je souˇcet ohodnocen´ı jej´ıch hran, tj.

P e∈E 0

c(e).

Na obr´ azku 6 m˚ uˇzeme vidˇet konkr´etn´ı pˇr´ıklady pojm˚ u z pˇredchoz´ı definice. V pˇr´ıkladu jsou dvˇe kostry s r˚ uzn´ ymi cenami. Vyˇreˇsit probl´em minim´ aln´ı kostry grafu znamen´a naj´ıt takovou kostru, jej´ıˇz cena je minim´ aln´ı, tj. takovou, ˇze neexistuje jin´ a kostra s menˇs´ı cenou. N´asleduje form´aln´ı definice probl´emu:

22

Minim´ aln´ı kostra grafu Instance:

Hranovˇe ohodnocen´ y graf (G, c), kde G = (V, E).

Pˇr´ıpustn´ a ˇreˇsen´ı: Cena ˇreˇsen´ı:

sol(G, c) = {(V, E 0 ) | (V, E 0 ) je kostra grafu G} P cost((V, E 0 ), G, c) = e∈E 0 c(e)

C´ıl:

minimum

Uk´ aˇzeme si jeden z nich, tzv. Kruskal˚ uv algoritmus. Protoˇze nalezen´ı minim´aln´ı kostry m˚ uˇzeme ch´apat jako nalezen´ı mnoˇziny hran E 0 z p˚ uvodn´ıho grafu, lze v jednotliv´ ych iterac´ıch krok˚ u 1 a 2 z obecn´eho popisu techniky, vyb´ırat vˇzdy jednu hranu. To znamen´ a, ˇze zaˇcneme s E 0 = ∅ a v kaˇzd´em kroku do E 0 jednu hranu pˇrid´ame. Pˇri v´ ybˇeru pˇridan´e hrany se ˇr´ıd´ıme jednoduch´ ym pravidlem: Vyber hranu s nejmenˇs´ı cenou, jej´ıˇz pˇr´ıd´ an´ı do E 0 nevytvoˇr´ı v (V, E 0 ) kruˇznici. Z p˚ uvodn´ıho grafu pot´e tuto hranu a vˇsechny hrany s menˇs´ı cenou, jejichˇz v´ ybˇer by vedl k vytvoˇren´ı kruˇznice, odstran´ıme. Iterujeme tak dlouho, dokud nenalezneme kostru. Testov´ an´ı vzniku kruˇznice - disjoint set structure Pˇri implementaci tohoto algoritmu je potˇreba nal´ezt efektivn´ı zp˚ usob hled´an´ı hrany s minim´aln´ı cenou a tak´e ovˇeˇren´ı existence kruˇznice. Prvn´ı probl´em lze vyˇreˇsit t´ım, ˇze si na zaˇc´atku algoritmu hrany vzestupnˇe setˇr´ıd´ıme. Efektivnˇe hledat kruˇznici lze s pomoc´ı vhodn´e datov´e struktury pro reprezentaci grafu. Touto strukturou je tzv. disjoint set structure. Jak napov´ıd´ a jej´ı n´azev, tato struktura slouˇz´ı k uloˇzen´ı kolekce S = {S1 , . . . , Sn } disjunktn´ıch mnoˇzin. Kaˇzdou z mnoˇzin S1 , . . . , Sn lze identifikovat pomoc´ı reprezentanta, vybran´eho prvku z dan´e mnoˇziny. Volba reprentanta je z´ avisl´ a na konkr´etn´ım pouˇzit´ı struktury, pro u ´ˇcely Kruskalova algoritmu na volbˇe reprezentanta nez´ aleˇz´ı. Jedinou podm´ınkou je, ˇze pokud strukturu nezmˇen´ıme nˇejakou operac´ı, je volba reprezentanta jednoznaˇcn´ a (tzn. pro dva dotazy na reprezentanta dostaneme stejnou opovˇed’). Nad strukturou lze prov´ adˇet n´ asleduj´ıc´ı operace. • MakeSet(x) pˇrid´ a do syst´emu novou mnoˇzinu, jej´ımˇz jedin´ ym prvkem je x. • Union(x, y) v syst´emu mnoˇzin sjednot´ı mnoˇzinu, kter´a obsahuje prvek x s mnoˇzinou obsahuj´ıc´ı prvek y (p˚ uvodn´ı mnoˇziny ze syst´emu odstran´ı a nahrad´ı je jejich sjednocen´ım). • FindSet(x) vr´ at´ı reprezentanta mnoˇziny obsahuj´ıc´ı x. Jednotliv´e mnoˇziny v syst´emu reprezentujeme pomoc´ı koˇrenov´ ych strom˚ u. V kaˇzd´em uzlu uchov´av´ame jeden prvek, ukazatel parent na pˇredka ve stromu (u koˇrene tento ukazatel ukazuje opˇet na koˇren) a rank, coˇz je horn´ı limit v´ yˇsky podstromu generovan´eho dan´ ym uzlem. V n´asleduj´ıc´ım pseudok´odu pˇredpokl´ad´ame, ˇze argumenty procedur jsou uzly stromu. Je tedy vhodn´e udrˇzovat vˇsechny uzly odpov´ıdaj´ıc´ı prvk˚ um z mnoˇzin, kter´e jsou v syst´emu, i v jin´em struktuˇre s pˇr´ım´ ym pˇr´ıstupem, napˇr. v poli. Funkce pro operace se strukturou pak pouze mˇen´ı ukazatele a ranky. Algoritmus 11 Operace nad disjoint set structure procedure MakeSet(x) x.parent ← x 3: x.rank ← 0 1: 2:

procedure FindSet(x) if x 6= x.parent then x.parent ←FindSet(x.parent) 4: return x.parent 1: 2: 3:

1: 2: 3: 4: 5: 6: 7: 8: 9:

procedure Union(x, y) rx ←FindSet(x) ry ←FindSet(y) if rx .rank > ry .rank then ry .parent ← rx else rx .parent ← ry if ry .rank = rx .rank then ry .rank = ry .rank + 1

Z pohledu sloˇzitosti je kritick´ a operace FindSet. Hled´ame v n´ı koˇren stromu pr˚ uchodem od uzlu ke koˇrenu. Sloˇzitost t´eto operace tedy z´ avis´ı na v´ yˇsce stromu, kter´ y reprezentuje mnoˇzinu (a v nejhorˇs´ım pˇr´ıpadˇe by mohla 23

r a r b c

c (a) P˚ uvodn´ı strom

b

a

(b) Strom po proveden´ı FindSet(c)

Obr´ azek 7: Heuristika v proceduˇre FindSet. b´ yt line´ arn´ı). V operac´ıch proto pouˇz´ıv´ ame heuristiky, kter´e zajiˇst’uj´ı, aby strom nebyl pˇr´ıliˇs vysok´ y. Prvn´ı z nich se nach´ az´ı v proceduˇre FindSet. Nejdˇr´ıve ˇretˇezem rekurzivn´ıch vol´an´ı najdeme koˇren stromu a pot´e pˇri n´avratu z rekurze (ˇr´ adek 3) nastav´ıme rodiˇce vˇsech navˇst´ıven´ ych uzl˚ u na koˇren a sn´ıˇz´ıme tak v´ yˇsku podstromu, ve kter´em se nach´ az´ı prvek v argumentu FindSet. Druh´a heuristika se uplat’nuje v proceduˇre Union. Tato procedura sjednot´ı dvˇe mnoˇziny tak, ˇze jednoduˇse pˇripoj´ı koˇren stromu reprezentuj´ıc´ı prvn´ı mnoˇzinu jako potomka ke koˇrenu stromu druh´e mnoˇziny. Pˇredpokl´ adejme nyn´ı, ˇze chceme spojit stromy s koˇreny x a y. Pokud je v´ yˇska x vˇetˇs´ı neˇz v´ yˇska y, pak pˇripojen´ım x jako potomka y zp˚ usob´ı to, ˇze v´ yˇska v´ ysledn´eho stromu o jedna vˇetˇs´ı neˇz v´ yˇska x. Pokud ale koˇreny pˇripoj´ıme naopak, bude v´ yˇskou v´ ysledn´eho stromu v´ yˇska x. Heuristika tedy spoˇc´ıv´ a v pˇripojen´ı niˇzˇs´ıho stromu jako potomka vyˇsˇs´ıho. Zaj´ımav´e je, ˇze poloˇzky rank v jednotliv´ ych uzlech nemus´ı odpov´ıdat re´ aln´e v´ yˇsce, protoˇze FindSet, kter´a mˇen´ı v´ yˇsky nˇekter´ ych uzl˚ u, tuto poloˇzku v˚ ubec nemˇen´ı. Ranky jsou tak pouze horn´ım omezen´ım re´ aln´e v´ yˇsky uzl˚ u. Sloˇzitost sekvence m operac´ı se strukturou, z nichˇz n operac´ı je MakeSet, je O(m·α(n)), kde α je velmi pomalu rostouc´ı funkce (asi jako inverzn´ı Ackermanova funkce), kter´a m´a pro n vyskytuj´ıc´ı v prakticky pˇredstaviteln´ ych aplikac´ıch hodnotu menˇs´ı neˇz 4. Kruskal˚ uv algoritmus Kruskal˚ uv algoritmus vyuˇz´ıv´ a disjoint set structure pro ukl´ad´an´ı mnoˇzin uzl˚ u grafu. Na zaˇc´atku algoritmu pˇrid´ ame do syst´emu pro kaˇzd´ y vrchol jednoprvkovou mnoˇzinu. Vˇzdy, kdyˇz v pr˚ ubˇehu algoritmu pˇrid´ame do ˇreˇsen´ı novou hranu, sjednot´ıme mnoˇziny, kter´e obsahuj´ı koncov´e vrcholy t´eto hrany. Indukc´ı lze dok´azat, ˇze v libovoln´em okamˇziku obsahuje kaˇzd´ a mnoˇzina pr´avˇe vrcholy jedn´e komponenty grafu tvoˇren´eho algoritmem zat´ım vybran´ ymi hranami. Protoˇze ˇz´ adn´ a z tˇechto komponent neobsahuje kruˇznici (protoˇze hrany tvoˇr´ıc´ı kruˇznici do ˇreˇsen´ı nepˇrid´ av´ ame) a protoˇze komponenty jsou spojit´e, lze test toho, jestli pˇrid´an´ım nov´e hrany vznikne kruˇznice prov´est jednoduˇse tak, ˇze otestujeme, jestli jsou oba koncov´e uzly t´eto hrany ve stejn´e mnoˇzinˇe. Pokud ano, pˇrid´ an´ım hrany by kruˇznice vznikla. Po pˇrid´an´ı takov´e hrany by totiˇz existovali dvˇe cesty mezi jej´ımi koncov´ ymi uzly, prvn´ı z nich tvoˇren´ a pr´ avˇe touto hranou, druh´a d´ıky tomu, ˇze uzly byli pˇred pˇrid´an´ım ve stejn´e komponentˇe. Nyn´ı si jiˇz m˚ uˇzeme uv´est pseudok´ od Kruskalova algoritmu. Pro jednoduchost z´apisu pˇredpokl´adejme, ˇze mnoˇzina vrchol˚ u V je tvoˇrena {0, 1, 2, . . . |V| − 1}. Spr´ avnost a optimalita Vˇ eta 3. Kruskal vrac´ı kostru grafu. D˚ ukaz. Mnoˇzina E 0 obsahuje |V| − 1 hran (ˇr´ adek 7 algoritmu) a neobsahuje cykly (ˇr´adek 9 algoritmu + diskuze v pˇredchoz´ım odstavci). Tvrzen´ı pak plyne ze souvislosti grafu G. Nyn´ı si m˚ uˇzeme dok´ azat optimalitu algoritmu. Vˇ eta 4. Kruskal vrac´ı minim´ aln´ı kostru. D˚ ukaz. Dok´ aˇzeme, ˇze po kaˇzd´em pˇrid´ an´ı hrany do E 0 existuje minim´aln´ı kostra T = (V, B) takov´a, ˇze obsahuje doposud algoritmem nalezen´e hrany. D˚ ukaz provedeme indukc´ı pˇres velikost E 0 . Oznaˇcme si jako Ei0 i-prvkovou mnoˇzinu hran, kterou z´ısk´ ame po pˇrid´ an´ı i-t´e hrany, kterou si oznaˇc´ıme ei . 24

Algoritmus 12 Kruskal˚ uv algoritmus 1: procedure Kruskal((G = (V, E), c)) 2: Vytvoˇr prioritn´ı frontu hran Q . hrany jsou setˇr´ızen´e vzestupnˇe podle ohodnocen´ı 3: Vytvoˇr |V| prvkov´e pole A . kaˇzd´ y prvek obsahuje poloˇzky rank a parent, A[i] odpov´ıd´a vrcholu i 4: for i ← 1 to |V| − 1 do 5: MakeSet(A[i]) . inicializujeme jednoprvkov´e komponenty 6: E0 ← ∅ 7: while |E 0 | < |V| − 1 do . iteruji dokud nem´am kostru 8: Odeber z Q hranu (u, v) 9: if FindSet(A[u]) 6= FindSet(A[v]) then . test toho, jestli jsou uzly ve stejn´e komponentˇe 10: E 0 ← E 0 ∪ {(u, v)} 11: Union(A[u], A[v]) . spoj´ım komponenty novˇe pˇridanou hranou 0 12: return (V, E )

Pro E00 = ∅ je situace trivi´ aln´ı, staˇc´ı vybrat libovolnou minim´aln´ı kostru. 0 Pˇredpokl´ adejme, ˇze tvrzen´ı plat´ı pro Ei−1 a T = (V, B) je odpov´ıdaj´ıc´ı minim´aln´ı kostra. Pokud ei ∈ B, je tvrzen´ı trivi´ aln´ı. Pokud ei ∈ / B, pak pˇrid´ an´ım ei do B vytvoˇr´ıme v T kruˇznici. Pak ale B obsahuje hranu ej ∈ / Ei0 , 0 0 kter´ a leˇz´ı na t´eto kruˇznici (jinak by algoritmus nemohl ei pˇridat do Ei−1 , v Ei by vznikla kruˇznice). Potom (V, B − {ej } ∪ {ei }) tvoˇr´ı kostru se stejnou cenou jako T . Staˇc´ı si uvˇedomit, ˇze po pˇridan´ı ei do B leˇz´ı obˇe hrany ei a ej na kruˇznici, a tud´ıˇz odstranˇen´ım jedn´e z nich dostaneme kostru. D´ale plat´ı, ˇze c(ei ) 6 c(ej ), protoˇze 0 v opaˇcn´em pˇr´ıpadˇe by si algoritmus vybral ej m´ısto ei . Skuteˇcnˇe, protoˇze Ei−1 ⊆ B tak by pˇrid´an´ım ej do 0 Ei−1 nevnikla kruˇznice (ej totiˇz neleˇz´ı na kruˇznici ani v T ) a algoritmus tedy ej nemohl v pˇredchoz´ıch iterac´ıch vynechat. Souˇcasnˇe T je minim´ aln´ı kostra, takˇze c(ej ) 6 c(ei ), odtud jiˇz dost´av´ame poˇzadovanou rovnost.

Zamysleme se nad sloˇzitost´ı algoritmu. Vytvoˇren´ı prioritn´ı fronty m´a za pˇredpokladu pouˇzit´ı tˇr´ıdˇen´ı porovn´av´ an´ım ˇ adek 3 se d´ sloˇzitost O(|E| log |E|). R´ a prov´est s line´arn´ı sloˇzitost´ı O(|V|). Pot´e algoritmus provede nejh˚ uˇre |V|+3|E| operac´ı nad disjoint sets structure, z nichˇz |V| operac´ı je MakeSet. Pokud budeme povaˇzovat α(|V|) za konˇ adky 9 a 11 stantu (viz diskuze ke sloˇzitosti operac´ı nad disjoint sets structure), dost´av´ame sloˇzitost O(|E|). R´ maj´ı konstatn´ı sloˇzitost. Protoˇze u spojit´eho grafu je |E| > |V| − 1, m˚ uˇzeme konstatovat, ˇze sloˇzitosti dominuje O(|E| log |E|).

´ du Sestaven´ı Huffmanova ko Huffman˚ uv k´ od je kl´ıˇcem k efektivn´ımu uloˇzen´ı ˇretˇezc˚ u nad urˇcitou abecedou pomoc´ı sekvence bit˚ u (a tedy efektivn´ı uloˇzen´ı tohoto ˇretezce v poˇc´ıtaˇci). ˇ Definice 12. K´ od nad abecedou Σ je injektivn´ı zobrazen´ı γ : Σ → {0, 1}∗ . Rekneme, ˇze k´od γ je jednoznaˇcn´ y, pokud existuje jednoznaˇcn´ y zp˚ usob, kter´ ym lze libovoln´e slovo w = w1 w2 . . . wk ∈ Σ∗ dek´odovat z jeho zak´ odov´ an´ı γ(w) = γ(w1 )γ(w2 ) . . . γ(wk ). Tato podm´ınka je ekvivalentn´ı tomu, ˇze kaˇzd´a dvˇe r˚ uzn´a slova maj´ı r˚ uzn´e zak´ odov´ an´ı. K´ od se naz´ yv´ a blokov´y, pokud pro kaˇzd´e dva znaky a, b ∈ Σ plat´ı, ˇze |γ(a)| = |γ(b)|. Pˇ r´ıklad 4. (a) Uvaˇzujme jednoduchou abecedu Σ = {x, y, z} a k´od γ dan´ y γ(x) = 0, γ(y) = 1, γ(z) = 01. Je snadno vidˇet, ˇze k´ od nen´ı blokov´ y. Tak´e nen´ı jednoznaˇcn´ y. Uvaˇzme napˇr´ıklad slovo xyz. Jeho zak´odov´ an´ı γ(xyz) = 0101 lze dek´ odovat tak´e jako xyxy. (b) ASCII tabulka je pˇr´ıkladem jednoznaˇcn´eho blokov´eho k´odu. Kaˇzd´ y z 256 moˇzn´ y znak˚ u, kter´e se v tabulce nach´ azej´ı m´ a pˇridˇelen unik´ atn´ı sekvenci 8 bit˚ u. Vˇsimnˇeme si, ˇze blokov´ y k´od je vˇzdy jednoznaˇcn´ y. ASCII tabulka je pˇr´ıkladem ˇsiroce pouˇz´ıvan´eho k´odu, kter´ y je standardem. D´ıky tomu je univerz´aln´ı a textov´e soubory v ASCII nemus´ı obsahovat k´ odovac´ı tabulku. Na druhou stranu je neefektivn´ı (jako kaˇzd´ y jin´ y blokov´ y k´ od) v tom, ˇze zanedb´ av´ a frekvenci v´ yskyt˚ u znak˚ u v ˇretezci a t´ım je zak´odov´an´ı ˇretezce delˇs´ı neˇz je nutn´e. Uv´ aˇz´ıme-li napˇr´ıklad ˇctyˇrprvkovou abecedu Σ = {a, b, c, d}, pak lze jednoduˇse vytvoˇrit blokov´ y k´od s d´elkou zak´ odov´ an´ı jednoho slova 2 bity. Uvaˇzme ˇretezec w nad Σ, kter´ y obsahuje 100 000 znak˚ u, a znak a v nˇem m´ a 10 000 v´ yskyt˚ u, b m´ a 50 000 v´ yskyt˚ u, c m´a 35 00 v´ yskyt˚ u a d m´a 5 000 v´ yskyt˚ u. Pokud zak´odujeme w 25

pomoc´ı zm´ınˇen´eho blokov´eho k´ odu, dostaneme 200000 bit˚ u. Pokud bychom ovˇsem sestrojili k´od, kter´ y ˇcasto vyskytuj´ımu se znaku pˇriˇrad´ı kratˇs´ı zak´ odov´ an´ı neˇz m´alo se vyskytuj´ıc´ım znak˚ um, m˚ uˇzeme w zak´odovat s pomoc´ı m´enˇe bit˚ u. Napˇr´ıklad pokud a zak´ odujeme pomoc´ı 3 bit˚ u, b pomoc´ı 1 bitu, c pomoc´ı 2 bit˚ u, d pomoc´ı 3 bit˚ u. Zak´ odov´ an´ı w pomoc´ı takov´eho k´ odov´ an´ı m´a pak 3 · 10000 + 1 · 50000 + 2 · 35000 + 3 · 5000 = 165000 bit˚ u. Uˇsetˇrili jsme tedy 35000 bit˚ u, coˇz je 17.5 procenta z p˚ uvodn´ı velikosti souboru. Pˇri pouˇzit´ı k´odu, kter´ y nen´ı blokov´ y si ovˇsem mus´ıme d´ at pozor na jednoznaˇcnost k´odu. Definice 13. Necht’ Σ je abeceda. K´ od γ je prefixov´y, pokud pro vˇsechna x, y ∈ Σ plat´ı, ˇze γ(x) nen´ı prefixem γ(y). Vˇ eta 5. Kaˇzd´y prefixov´y k´ od je jednoznaˇcn´y. D˚ ukaz. Staˇc´ı uk´ azat, ˇze existuje procedura pro jednoznaˇcn´e dek´odov´an´ı. Slovo w = w1 w2 . . . wn dek´odujeme ze sekvence γ(w) = b1 . . . bm n´ asleduj´ıc´ım postupem. 1. ˇcteme sekvenci zleva doprava 2. kdyˇz pˇreˇcteme sekvenci b1 . . . bj takovou, ˇze γ(w1 ) = b1 . . . bj pro dek´odujeme w1 3. smaˇzeme b1 . . . bj ze sekvence a pokraˇcujeme bodem 1. Iterujeme dokud nen´ı sekvence pr´azdn´a. D´ıky tomu, ˇze je γ prefixov´ y k´ od, nem˚ uˇzeme v bodˇe 1 dek´odovat jin´ y znak neˇz w1 (a v dalˇs´ıch iterac´ıch w2 , w3 , . . . ). Pˇ r´ıklad 5. Uvaˇzujme prefixov´ y k´ od γ dan´ y n´asleduj´ıc´ı tabulkou. Symbol a b c d e

γ 11 01 001 10 000

ˇ Retez cecab pak k´ odujeme pomoc´ı 0010000011101. Procedura z pˇredch´azej´ıc´ıho d˚ ukazu pak provede n´asleduj´ıc´ı kroky Krok 1 2 3 4 5

γ(cebab)

dek´odovan´ y znak

0010000011101 0000011101 0011101 1101 01

c e c a b

Pro x ∈ Σ je frekvence fx znaku x v textu w ∈ Σ∗ o n znac´ıch je pod´ıl poˇcet v´ yskyt˚ ux . n Vˇsimnˇeme si, ˇze n · fx je poˇcet v´ yskyt˚ u znaku x v textu, a jelikoˇz souˇcet poˇct˚ u v´ yskyt˚ u jednotliv´ ych znak˚ u z textu je n, je suma vˇsech frekvenc´ı znak˚ u vyskytuj´ıc´ıch se v textu rovna 1. Efektivitu k´odu mˇeˇr´ıme d´elkou zak´ odov´ an´ı vstupn´ıho ˇretˇezce. Protoˇze X X |γ(w)| = n · fx · |γ(x)| = n fx · |γ(x)| fx =

x∈S

x∈S

m˚ uˇzeme vypustit z´ avislost na d´elce |w| = n a mˇeˇrit efektivitu γ pomoc´ı pr˚ umˇern´e d´elky zak´odov´an´ı jednoho znaku X ABL(γ) = fx · |γ(x)|. x∈S

26

Pˇ r´ıklad 6. (a) Uvaˇzme prefixov´ y k´ od dan´ y n´ asleduj´ıc´ı tabulkou x

γ(x)

fx

a b c d e

11 01 001 10 000

.32 .25 .20 .18 .05

Pr˚ umˇern´ a d´ekla slova tohoto k´ odu je ABL(γ) = 0.32 · 2 + 0.25 · 2 + 0.20 · 3 + 0.18 · 2 + 0.05 · 3 = 2.25 Oproti blokov´emu k´ odu, kter´ y by mˇel d´elku ABL rovno 3 (proˇc?), jsme uˇsetˇrili 0.75 bitu. (b) Uvaˇzme prefixov´ y k´ od dan´ y n´ asleduj´ıc´ı tabulkou x

γ(x)

fx

a b c d e

11 10 01 001 000

.32 .25 .20 .18 .05

Pr˚ umˇern´ a d´ekla slova tohoto k´ odu je ABL(γ) = 0.32 · 2 + 0.25 · 2 + 0.20 · 2 + 0.18 · 3 + 0.05 · 3 = 2.23 Oproti blokov´emu k´ odu, kter´ y by mˇel d´elku 3, jsme uˇsetˇrili 0.77 bitu. Tento k´od je tak´e o 0.02 bitu lepˇs´ı neˇz ten z pˇredchoz´ıho pˇr´ıkladu. ˇ Definice 14. Necht’ Σ je abeceda znak˚ u vyskytuj´ıch se v textu s frekvencemi fx pro x ∈ Σ. Rekneme, ˇze 0 prefixov´ y k´ od γ k´ oduj´ıc´ı Σ je optim´ aln´ı, jesliˇze pro vˇsechny ostatn´ı prefixov´e k´ody γ plat´ı, ˇze ABL(γ) 6 ABL(γ 0 ). Optim´ aln´ı k´ od tak´e naz´ yv´ ame Huffman˚ uv k´ od. Nalezen´ı Huffmanova k´ odu je optimalizaˇcn´ı probl´em Nalezen´ı Huffmanova k´ odu Instance:

abeceda Σ, frekvence v´ yskytu jednotliv´ ych znak˚ u fx pro x ∈ Σ

Pˇr´ıpustn´ a ˇreˇsen´ı:

{γ | γ je prefixov´ y k´od pro Σ}

Cena ˇreˇsen´ı:

cost(γ, Σ, {fx | x ∈ Σ}) = ABL(γ)

C´ıl:

minimum

V algoritmu pro nalezen´ı Huffmanova k´ odu je tento k´od reprezentov´an koˇrenov´ ym stromem (a tato reprezentace je tak´e v´ yhodnˇejˇs´ı v d˚ ukazech spr´ avnosti a optimality algoritmu). Pro prefixov´ y k´od γ nad abecedou Σ oznaˇc´ıme takov´ y strom Tγ . Tento strom je bin´ arn´ı, jeho listy jsou tvoˇreny prvky Σ. Hrany z nelistov´ ych uzl˚ u k lev´emu potomku jsou oznaˇceny 0, k prav´emu potomku 1. Tγ lze setrojit n´asledovnˇe: 1. zaˇc´ın´ ame s koˇrenem 2. vˇsechny znaky x, jejichˇz prvn´ı bit γ(x) je 0 jsou listy v lev´em podstromu, ostatn´ı (prvn´ı bit γ(x) je 1) jsou listy v prav´em podstromu. 3. pˇredchoz´ı krok opakujeme pro lev´ y a prav´ y podstrom (s mnoˇzinami znak˚ u rozdˇelen´ ych podle bodu 2), pro γ(x) v nichˇz vynech´ ame prvn´ı bit k´ odu 4. pokud je γ(x) pr´ azn´ a sekvence, x je koˇrenem stromu 27

Pˇ r´ıklad 7. Prefixov´ y k´ od a j´ım indukovan´ y strom. x

γ(x)

a b c d e

11 10 01 001 000

0 0

1

e

d

0

1

1

0 c

b

1 a

Je-li d´ an Tγ je snadn´e zpˇet zpoˇc´ıtat γ. Pro kaˇzd´ y x ∈ Σ vypoˇcteme γ(x) tak, ˇze najdeme ve stromu Tγ cestu od listu x do koˇrene. Dostaneme tak sekvenci hran e1 , . . . , em (x m´a hloubku m), kterou podle oznaˇcen´ı hran pˇrevedeme na sekvenci bit˚ u b1 , . . . , bm . Pˇrevr´ acen´ım t´eto sekvence obdrˇz´ıme γ(x). D´elka k´ odov´eho slova γ(x) odpov´ıd´ a v Tγ hloubce listu x (ozn. depthT (x)). Pr˚ umˇernou d´elku k´odov´eho slova m˚ uˇzeme vyj´ adˇrit X ABL(T ) = fx · depthT (x) x∈Σ

Abychom nalezli algoritmus pro sestaven´ı stromu odpov´ıdaj´ıc´ıho Huffmanovˇe k´odu, projdeme si nˇekolik vlastnost´ı takov´ ych strom˚ u. Vˇ eta 6. Pro kaˇzd´y optim´ aln´ı prefixov´y k´ od γ plat´ı, ˇze kaˇzd´y nelistov´y uzel v Tγ m´ a stupeˇ n 2. D˚ ukaz. Dok´ aˇzeme sporem. Pˇredpokl´ adejme, ˇze ve stromˇe Tγ existuje uzel v s jedn´ım potomkem u. Pokud uzel v ze stromu smaˇzeme a nahrad´ıme jej uzlem u, obdrˇz´ıme strom s menˇs´ı pr˚ umˇernou hloubkou (vˇsechny listy v podstromu generovan´em uzlem u budou m´ıt o 1 menˇs´ı hloubku). Tento strom odpov´ıd´a prefixov´eho k´odu pro stejnou abecedu jako Tγ , protoˇze jsme neodstranili ˇz´adn´ y list. To je ale spor s t´ım, ˇze γ je optim´aln´ı k´od. Vˇ eta 7. Necht’ γ je optim´ aln´ı prefixov´y k´ od. Pak pro kaˇzd´e dva listy y, z ve stromu Tγ plat´ı, ˇze pokud depthTγ (z) > depthTγ (y), pak fy > fz . D˚ ukaz. Sporem Pokud fy < fz , pak prohozen´ım u z a y z´ısk´ame strom s menˇs´ı pr˚ umˇernou hloubkou, coˇz je Puzl˚ spor. Skuteˇcnˇe: Pod´ıv´ ame-li se na ˇcleny sumy x∈Σ fx · depthTγ (x) pro x ∈ {y, z}, pak zjist´ıme, ˇze • n´ asobek fy vzroste z depthTγ (y) na depthTγ (z) • n´ asobek fz klesne z depthTγ (z) na depthTγ (y) Zmˇena je tedy (rozd´ıl sumy pˇred a po v´ ymˇenˇe pro x, y): (fy · depthTγ (y) − fy · depthTγ (z)) + (fz · depthTγ (z) − fz · depthTγ (y)) = (depthTγ (y) − depthTγ (z))(fy − fz ) Posledn´ı v´ yraz je vˇzdy kladn´ y, proto m´ a nov´ y strom menˇs´ı pr˚ umˇernou hloubku. Vˇ eta 8. Existuje optim´ aln´ı prefixov´y k´ od γ takov´y, ˇze listy x, y v Tγ takov´e, ˇze fx a fy jsou dvˇe nejmenˇs´ı frekvence, jsou (a) v maxim´ aln´ı hloubce (b) sourozenci D˚ ukaz. (a) Plyne z pˇredchoz´ı vˇety. (b) Prohazov´ an´ım list˚ u, kter´e jsou ve stejn´e hloubce se nezmˇen´ı pr˚ umˇern´a hloubka list˚ u. Protoˇze v Tγ maj´ı vˇsechny nelistov´e uzly stupeˇ n 2, mus´ı existovat v maxim´aln´ı hloubce dva listy, kter´e jsou sourozenci. Tyto listy pak m˚ uˇzeme prohodit s x a y. 28

Pˇredchoz´ı vˇeta je z´ akladn´ı myˇslenkou greedy algoritmu pro konstrukci Tγ . Algoritmus si udrˇzuje mnoˇzinu strom˚ u, kter´e postupnˇe spojuje do v´ ysledn´eho stromu Tγ . Koˇren kaˇzd´eho takov´eho stromu m´a pˇriˇrazeno ˇc´ıslo — sumu frekvenc´ı znak˚ u abecedy, kter´e jsou listy stromu. Na zaˇc´atku algoritmu vytvoˇr´ıme pro kaˇzd´ y znak z abecedy jednoprvkov´ y strom, frekvence nastav´ıme na frekvence v´ yskyt˚ u odpov´ıdaj´ıch znak˚ u. Pot´e algoritmus greedy strategi´ı sestavuje v´ ysledn´ y strom: 1. Vybere dva stromy x, y s nejniˇzˇs´ımi frekvencemi koˇren˚ u fx a fy a spoj´ı je do nov´eho stromu tak, ˇze vytvoˇr´ı nov´ y koˇren w, nastav´ı jeho frekvenci na fw = fx + fy . Koˇreny strom˚ u x a y se pak stanou potomky w. 2. Opakuje pˇredchoz´ı krok, dokud nespoj´ı vˇsechny stromy do jednoho. Aby byl algoritmus jasnˇejˇs´ı, uvedeme ho i v pseudok´odu jako Algoritmus 13. Budeme pˇredpokl´adat, ˇze vstupem je pole znak˚ u abecedy Σ a pole frekvenc´ı v´ yskytu tˇechto znak˚ u F, a d´ale ˇze uzly strom˚ u maj´ı poloˇzky symbol, freq, left a right. Algoritmus 13 Sestaven´ı Huffmanova k´ odu 1: procedure Huffman(Σ, F) 2: Inicializuj prioritn´ı frontu S uspoˇr´ adanou podle frekvenc´ı 3: for i ← 0 to |Σ| − 1 do 4: Vytvoˇr uzel x 5: x.symbol ← Σ[i] 6: x.freq ← F[i] 7: x.left ← x.right ←NIL 8: Enqueue(S, x) 9: while Size(S) > 1 do 10: x ←Dequeue(S) 11: y ←Dequeue(S) 12: Vytvoˇr uzel w 13: w.freq ← x.freq + y.freq 14: w.left ← x 15: w.right ← y 16: Enqueue(S, w) 17: return Dequeue(S)

. Vytvoˇr´ıme jednoprvkov´ y strom

. Vloˇz´ıme strom do fronty . x, y jsou stromy s nejniˇzˇs´ımi frekvencemi

. Vloˇz´ım novˇe vytvoˇren´ y strom do fronty . Vr´at´ım jedin´ y strom v frontˇe

Sloˇzitost Huffman je O(|Σ| log |Σ|). Prioritn´ı frontu (ˇr´adky 2 aˇz 9) zkonstruujeme v ˇcase O(|Σ| log |Σ|). Pot´e |Σ|−1 kr´ at opakujeme cyklus (ˇr´ adky 10 aˇz 18), ve kter´em dvakr´at odebereme a jednou pˇrid´ame prvek do prioritn´ı fronty, tyto operace maj´ı logaritmickou sloˇzitost. Ostatn´ı operace v tomto cyklu maj´ı konstantn´ı sloˇzitost. Zb´ yv´ a dok´ azat, ˇze Huffman skuteˇcnˇe konstruuje strom pro optim´aln´ı k´od. Vˇ eta 9. Necht’ S = {x1 , . . . , xn } je abeceda znak˚ u s frekvencemi fx1 . . . fxn a S 0 = S − {xi , xj } ∪ {w}, kde xi , xj jsou znaky s nejmenˇs´ımi frekvencemi a w je nov´y znak s frekvenc´ı fw = fxi + fxj . Necht’ T 0 je strom optim´ aln´ıho k´ odu pro S 0 . Pak pro strom T , kter´y dostaneme z T 0 tak, ˇze nahrad´ıme w vnitˇrn´ım uzlem s potomky xi , xj plat´ı: (a) ABL(T 0 ) = ABL(T ) − fw (b) T je strom optim´ aln´ıho k´ odu pro abecedu S. D˚ ukaz. (a) Hloubky vˇsech list˚ u mimo xi a xj sou stejn´e v T i T 0 . Hloubka list˚ u xi a xj v T je o 1 vˇetˇs´ı neˇz

29

hloubka w v T 0 . Odtud m´ ame, ˇze X ABL(T ) = fx · depthT (x) x∈S

= fxi · depthT (xi ) + fxj · depthT (xj ) + =

X

(fxi + fxj )(1 + depthT 0 (w)) + X

= fw + fw · depthT 0 (w) + = fw +

X

X

fx · depthT 0 (x)

x6=xi ,xj

fx · depthT 0 (x)

x6=xi ,xj

fx · depthT 0 (x)

x6=xi ,xj

fx · depthT 0 (x) = fw + ABL(T 0 )

x∈S 0

(b) Sporem. Pˇredpokl´ adejme, ˇze k´ od odpov´ıdaj´ıc´ı T nen´ı optim´aln´ı. Pak existuje optim´aln´ı k´od se stromem Z tak, ˇze ABL(Z) < ABL(T ). Podle vˇety 8 m˚ uˇzeme bez obav pˇredpokl´adat, ˇze xi a xj jsou v Z sourozenci. Oznaˇcme jako Z 0 strom, kter´ y z´ısk´ ame ze Z n´ahradou podstromu generovan´ ym rodiˇcem uzl˚ u xi a xj pomoc´ı nov´ehu uzlu s frekvenc´ı fw = fxi + fxj . Pak podle (a) m´ame: ABL(Z 0 ) = ABL(Z) − fw < ABL(T ) − fw = ABL(T 0 ). To je ale spor s t´ım, ˇze T 0 je optim´ aln´ı. Vˇ eta 10. Hufmann vrac´ı optim´ aln´ı k´ od. D˚ ukaz. Staˇc´ı si vˇsimnout, ˇze jeden krok algoritmu odpov´ıd´a konstrukci z vˇety 9. Pˇ r´ıklad 8. Uvaˇzujme abecedu s frekvencemi v´ yskytu znak˚ u danou tabulkou x

fx

a b c d e

.32 .25 .20 .18 .05

Fronta strom˚ u v algoritmu pak postupnˇe projde n´asleduj´ıc´ımi stavy.

30

0.05

0.18

0.20

0.25

0.32

0.20

e

d

c

b

a

c

0.23

e

(a) inicializace

0.25

0.32

b

a

0.25

0.32

b

a

d

(b) Po 1. iteraci

0.43

0.43

c

0.57

b

c e

d

e

(c) Po 2. iteraci

d

(d) Po 3. iteraci

1

b

c e

d

(e) Po 4. iteraci

31

a

a

Metody zaloˇ zen´ e na hrub´ e s´ıle Metoda hrub´e s´ıly se d´ a popsat jednoduchou vˇetou zkus vˇsechny moˇznosti.“ U optimalizaˇcn´ıch probl´em˚ u to ” znamen´ a, ˇze k dan´e vstupn´ı instanci algoritmus vygeneruje vˇsechna pˇr´ıpustn´a ˇreˇsen´ı a pak z nich vybere to optim´ aln´ı. Napˇr´ıklad u u ´lohy batohu, kde chceme naj´ıt podmnoˇzinu vah takovou, ˇze jej´ı suma je maxim´aln´ı ze vˇsech podmnoˇzin, jej´ıchˇz suma je menˇs´ı neˇz kapacita, algoritmus pouˇz´ıvaj´ıc´ı hrubou s´ılu nejdˇr´ıve vygeneruje vˇsechny podmnoˇziny vah a pak najde tu nejlepˇs´ı. Technika hrub´e s´ıly je pouˇziteln´a i pro rozhodovac´ı probl´emy. Pokud pro danou instanci x rozhodovac´ıho probl´emu L (zde ch´apan´eho jako jazyk L), existuje vhodn´ y certifik´ at, na jehoˇz z´ akladˇe v´ıme, ˇze x ∈ L (tedy, odpovˇed je ano), algoritmus funguj´ıc´ı hrubou silou vygeneruje vˇsechny moˇzn´e kandid´ aty na takov´ y certifik´ at a pot´e se jej v t´eto mnoˇzinˇe pokus´ı naj´ıt. Uvaˇzme napˇr´ıklad probl´em SAT. Zde m˚ uˇzeme za certifik´ at povaˇzovat takov´e ohodnocen´ı v´ yrokov´ ych promˇenn´ ych, pˇri kter´em je vstupn´ı instance, tj. formule v´ yrokov´e logiky, pravdiv´ a. Algoritmus vygeneruje vˇsechna moˇzn´a ohodnocen´ı v´ yrokov´ ych promˇenn´ ych t´eto formule a pot´e ovˇeˇr´ı, jestli je pro nˇekter´e z nich formule pravdiv´a. Pokud takov´e ohodnocen´ı najde, je odpovˇed’ ano. Generov´ an´ı vˇsech moˇznost´ı vede ve vˇetˇsinˇe pˇr´ıpad˚ u ke generov´an´ı z´akladn´ıch kombinatorick´ ych struktur jako jsou permutace a variace. Zp˚ usob jejich generov´an´ı si m˚ uˇzeme uk´azat na klasick´em probl´emu tah´an´ı barevn´ ych m´ıˇck˚ u z pytl´ıku. Pˇredpokl´ adejme, ˇze m´ ame m´ıˇcky n barev oznaˇcen´ ych jako {0, 1, . . . , n − 1} a chceme vyt´ahnout k m´ıˇck˚ u. Algoritmus pro vygenerov´ an´ı vˇsech moˇznost´ı vytaˇzen´ı tˇechto m´ıˇck˚ u proch´az´ı n´asleduj´ıc´ı strom.

(0)

ku ´rovn´ı

(0, 0) (0, 1)

(1)

(n)

(0, n)

(0, n, . . . , 0) (0, n, . . . , 1)

(0, n, . . . , n)

k prvk˚ u Uzly stromu odpov´ıdaj´ı vytaˇzen´ı jednoho m´ıˇcku. Podle u ´rovn´ı stromu urˇc´ıme, kolik´at´ y m´ıˇcek v poˇrad´ı tah´ ame. Oznaˇc´ıme-li si generovanou sekvenci jako ha1 , . . . , ak i, pak 1. u ´roveˇ n (uzly v hloubce 1) odpov´ıd´a volbˇe a1 , 2. u ´roveˇ n odpov´ıd´ a volbˇe pro a2 a tak d´ ale. Pro kaˇzd´ y uzel plat´ı, ˇze uzly cestˇe od koˇrene k tomuto uzlu jednoznaˇcnˇe urˇcuj´ı odpov´ıdaj´ıc´ı ˇc´ ast generovan´e sekvence. Napˇr´ıklad u uzlu v hloubce 3 v´ıme, kter´e m´ıˇcky jsme vyt´ahli pro a1 , a2 a a3 . Na z´ akladˇe t´eto informace m˚ uˇzeme rozhodnout, jak´e m´ıˇcky zvol´ıme v dalˇs´ı vrstvˇe (jestli chceme, aby se m´ıˇcek v sekvenci opakoval, nebo ne). Uzly v hloubce k uˇz nemaj´ı potomky (a jsou tedy listy). Sekvence odpov´ıdaj´ıc´ı cest´ am z koˇrene do list˚ u jsou pak vygenerovan´e sekvence. Algoritmus pro generov´ an´ı proch´ az´ı strom do hloubky, m˚ uˇzeme proto pouˇz´ıt rekurzi. Argumenty procedury Generate jsou mnoˇzina m´ıˇck˚ u X, doposud sestaven´a ˇc´ast sekvence ha1 , . . . , ai i a poˇcet m´ıˇck˚ uvu ´pln´e sekvenci k. Procedura Filter slouˇz´ı k v´ ybˇeru toho, kter´e m´ıˇcky lze dosadit za ai+1 . Pokud Filter vˇzdy vr´at´ı X, Generate generuje k-prvkov´e variace s opakov´an´ım, pokud Filter vr´at´ı X − {a1 , . . . , ai }, Generate generuje variace bez opakov´ an´ı. Generov´ an´ı spust´ıme zavol´an´ım Generate s pr´azdnou sekvenc´ı a. Algoritmus 14 Generov´ an´ı variac´ı a permutac´ı 1: procedure Generate(X, ha1 , . . . , ai i, k) 2: if i = k then 3: Zpracuj a1 , . . . , ai 4: S ←Filter(X, ha1 , . . . , ai i) 5: for x ∈ S do 6: Generate(X, ha1 , . . . , ai , xi, k)

. Sekvence m´a k prvk˚ u, skonˇci rekurzi . Vyfiltruj prvky, kter´e lze dosadit za ai+1 . Doplˇ n sekvenci o x a pokraˇcuj v rekurzi

Pojmenov´ an´ı backtracking je inspirov´ ano principem, na kter´em Generate pracuje. Kdyˇz algoritmus nalezne jednu sekvenci (dostane se do listu stromu), vystoup´ı z rekurze o u ´roveˇ n nahoru (tj. posune se ve stromˇe po 32

cestˇe smˇerem ke koˇrenu) a generuje dalˇs´ı sekvence rekurzivn´ım vol´an´ım na ˇr´adku 7. Tento n´avrat nahoru“ m´ a ” anglick´e jm´eno backtrack. Pokud pouˇz´ıv´ ame backtracking pro ˇreˇsen´ı konkr´etn´ıho probl´emu, ˇcasto nemus´ıme generovat vˇsechny moˇznosti. Pˇredpokl´ adejme ˇze m´ ame vygenerov´ anu ˇc´ ast sekvence a = a1 , . . . , ai . Potom m˚ uˇzeme Generate obohatit o n´ asleduj´ıc´ı testy. I. test na ˇr´ adku 2 m˚ uˇzeme nahradit testem, kter´ y rozhodne, zda-li je a1 , . . . , ai uˇz ˇreˇsen´ım, nebo se d´a rychle doplnit na ˇreˇsen´ı (napˇr´ıklad libovoln´ ym v´ ybˇerem zbyl´ ych prvk˚ u sekvence). II. pˇred rekurzivn´ım vol´ an´ım na ˇr´ adku 7. m˚ uˇzeme testovat, jestli a1 , . . . , ai , x je prefixem sekvence, kterou chceme vygenerovat (tj. to, jestli m´ a smysl pokraˇcovat v generov´an´ı zbytku sekvence). Pokud ne, Generate uˇz rekurzivnˇe nevol´ ame. Oba pˇredchoz´ı testy se daj´ı pouˇz´ıt k oˇrez´ an´ı stromu rekurzivn´ıho vol´an´ı.

´ SAT solver Jednoduchy Jako uk´ azku si uvedeme algoritmus pro probl´em SAT. Pˇripomeˇ nme, ˇze SAT je definov´an jako SAT Instance:

formule v´ yrokov´e logiky v konjunktivn´ı norm´aln´ı formˇe ϕ

ˇ sen´ı: Reˇ

1 pokud je ϕ splniteln´a, jinak 0.

K sestaven´ı algoritmu pro SAT staˇc´ı upravit Generate. Algoritmus totiˇz generuje postupnˇe vˇsechna moˇzn´ a ohodnocen´ı v´ yrokov´ ych promˇenn´ ych. Uvaˇzme formuli ϕ, kter´a je konjunkc´ı m liter´al˚ u C1 , . . . , Cm a obsahuje k v´ yrokov´ ych promˇenn´ ych x1 , . . . , xk . Ohodnocen´ı tˇechto promˇenn´ ych m˚ uˇzeme ch´apat jako sekvenci ha1 , . . . , ak i sloˇzenou z 1 a 0, pˇritom ai je ohodnocen´ı promˇenn´e xi . D´ale si pro klauzuli Cj definujeme n´asleduj´ıc´ı dva predik´ aty - F(Cj , ha1 , . . . , ai i) je pravdiv´ y, pr´ avˇe kdyˇz promˇenn´e obsaˇzen´e v Cj patˇr´ı do {x1 , . . . , xi } a vzhledem k ohodnocen´ı ha1 , . . . , ai i neobsahuje Cj ˇz´ adn´ y pravdiv´ y liter´al, - T(Cj , ha1 , . . . , ai i) je pravdiv´ y, pokud liter´al alespoˇ n jedn´e promˇenn´e z Cj patˇr´ıc´ı do {x1 , . . . , xi } je pˇri ohodnocen´ı ha1 , . . . , ai i pravdiv´ y. S pomoc´ı F a T m˚ uˇzeme pro SAT jednoduˇse implementovat testy zm´ınˇen´e v bodech I a II. V´ıme, ˇze formule ϕ je pravdiv´ a, pr´ avˇe kdyˇz jsou pravdiv´e vˇsechny klausule, coˇz plat´ı, pr´avˇe kdyˇz je v kaˇzd´e klausuli alespoˇ n jeden pravdiv´ y liter´ al. Pokud je tedy T(Cj , ha1 , . . . , ai i) pravdiv´ y pro vˇsechny klausule, v´ıme, ˇze ϕ je pravdiv´ a pro libovoln´e doplnˇen´ı ha1 , . . . , ai i. Naopak, pokud je splnˇeno F(Cj , ha1 , . . . , ai i) alespoˇ n pro jednu klausuli, je tato klausule pro libovoln´e doplnˇen´ı ha1 , . . . , ai i nepravdiv´a, v d˚ usledku ˇcehoˇz je nepravdiv´a i ϕ. ˇ Casov´ a sloˇzitost EasySat je v nejhorˇs´ım pˇr´ıpadˇe exponenci´aln´ı vhledem k poˇctu promˇenn´ ych k. Pokud kaˇzd´ a klausule nesplniteln´e formule ϕ obsahuje liter´ al promˇenn´e xk , pak EasySat vygeneruje vˇsechna ohodnocen´ı. Tˇechto ohodnocen´ı je 2k . SAT je d˚ uleˇzit´ y nejen teoreticky (jak zjist´ıte v kurzu sloˇzitosti), ale tak´e pro praktick´e nasazen´ı. Mnoho v praxi d˚ uleˇzit´ ych u ´loh pˇrech´ az´ı na SAT (ovˇerov´ an´ı n´avrhu logick´ ych obvod˚ u, ovˇeˇrov´an´ı spr´avnosti model˚ u apod). Existuje dokonce kaˇzdoroˇcn´ı soutˇeˇz program˚ u, tzv. SAT solver˚ u, pro ˇreˇsen´ı SAT probl´emu. Mnoh´e z nich jsou vyv´ıjen´e velk´ ymi firmami a licencov´ any za nemal´ y pen´ız. EasySat je z tohoto pohledu velmi naivn´ım algoritmem (i kdyˇz vˇetˇsina SAT solver˚ u je v´ıce ˇci m´enˇe zaloˇzena na backtrackingu). Jednoduˇse ale demonstruje z´ akladn´ı princip oˇrez´ an´ı stromu rekurze.

´ Uloha n dam ´ ´ Uloha n dam je probl´em, kter´ y se ˇcasto vyskytuje v programovac´ıch nebo matematick´ ych soutˇeˇz´ıch. Ukolem je spoˇc´ıtat kolika zp˚ usoby lze um´ıstit n dam na ˇsachovnici tak, aby se vz´ajemnˇe neohroˇzovaly. Pˇritom pˇredpokl´ ad´ ame, ˇze d´ ama m˚ uˇze t´ ahnout jako v ˇsachu, tedy posunout se o libovoln´ y poˇcet pol´ı vodorovnˇe, svisle nebo diagon´ alnˇe. 33

Algoritmus 15 Jednoduch´ y SAT solver 1: procedure EasySat(ϕ = C1 ∨ · · · ∨ Cm , ha1 , . . . , ai i, k) 2: E ←true 3: for j ← 1 to m do 4: if not T(Cj , ha1 , . . . , ai i) then 5: E ←false 6: break 7: if E then 8: return true 9: for x ∈ {0, 1} do 10: E ←true 11: for j ← 1 to m do 12: if F(Cj , ha1 , . . . , ai , xi) then 13: E ←false 14: break 15: if E then 16: if EasySat(ϕ, ha1 , . . . , ai , xi, k) then 17: return true 18: return false

. Vˇsechny klauzule jsou pravdiv´e . Hled´am nesplnitelnou klausuli

. ϕ je pravdiv´a, algoritmus konˇc´ı . Obˇe rekurzivn´ı vol´an´ı vr´atila false

Naivn´ı pˇr´ıstup k ˇreˇsen´ı tohoto probl´emu by bylo vygenerovat vˇsechna moˇzn´a rozm´ıstˇen´ı dam na ˇsachovnici a pot´e pro kaˇzd´e rozm´ıstˇen´ı
otestovat, jestli je d´amy neohroˇzuj´ı. Tento pˇr´ıstup je ale velmi neefektivn´ı, protoˇze 2 2 ! takov´ ych rozm´ıstˇen´ı je nn = n!(nn2 −n)! . Uk´ aˇzeme si sofistikovanˇejˇs´ı pˇr´ıstup, ve kter´em vyuˇzijeme znalost´ı ˇsachov´ ych pravidel uˇz bˇehem generov´ an´ı. Sloupce a ˇr´ adky ˇsachovnice si oznaˇc´ıme ˇc´ısly 1 . . . n. Protoˇze d´ama t´ahne horizont´alnˇe, ve spr´avn´em rozestaven´ı mus´ı b´ yt na kaˇzd´em ˇr´ adku pr´ avˇe jedna d´ ama. Pozice tedy m˚ uˇzeme generovat jako sekvence ha1 , . . . , an i, kde ai je sloupec, ve kter´em se nach´ az´ı d´ ama na i-t´em ˇr´adku. Protoˇze v kaˇzd´em sloupci m˚ uˇze b´ yt pr´avˇe jedna d´ ama, m˚ uˇzeme jak kostru algoritmu vyuˇz´ıt Generate pro generov´an´ı permutac´ı. Jedin´a vˇec, kterou m˚ uˇzeme pˇridat, je test odpov´ıdaj´ı podm´ınce II. Pro a1 , . . . , ai otestujeme, jestli jestli se d´amy v prvn´ıch i ˇr´adc´ıch neohroˇzuj´ı diagon´ alnˇe. ´ Algoritmus 16 Uloha n dam 1: procedure Queens(ha1 , . . . , ai i, n) 2: if i=n then 3: return 1 4: S ← {1, . . . , n} \ {a1 , . . . , ai } 5: c←0 6: for ai+1 ∈ S do 7: p ←true 8: for j ← 1 to i do 9: if |j − (i + 1)| = |aj − ai+1 | then 10: p ←false 11: break 12: if p then 13: c ← c + Queens(ha1 , . . . , ai , ai+1 i, n) 14: return c Pˇ r´ıklad 9. (a) pro n = 4 existuj´ı 2 pozice, strom na n´asleduj´ıc´ım obr´azku je symetrick´ y

34

1

2

3

2

2

4

4

1

2

4

3

1

3

3

3

3

(a) pro n = 3 je v´ ysledek 0.

1

2

3

3

2

3

1

2

1

2

2

Sloˇzitost Queens nen´ı zn´ ama, nicm´enˇe je obrovsk´a. Jenom poˇcet moˇzn´ ych spr´avn´ ych pozic a tedy i vygenerovan´ ych u ´pln´ ych sekvenc´ı roste obrovsky rychle. Pˇresn´ y vzorec nen´ı zat´ım zn´am, nicm´enˇe pro n = 5 je spr´avn´ ych pozic 10, pro n = 24 je jich uˇz v´ıce neˇz 227 · 1012 .

Set Cover Na probl´emu Set Cover si uk´ aˇzeme jednoduchou techniku, jak proˇrezat strom rekurze pˇri ˇreˇsen´ı optimalizaˇcn´ıho ˇ probl´emu. Reknˇ emˇe, ˇze hled´ ame ˇreˇsen´ı instance I. Idea je, ˇze budeme generovat prvky x ∈ sol(I), poˇc´ıtat pro nˇe cenu cost(x, I) a vybereme ten optim´ aln´ı. Pokud si v pr˚ ubˇehu algoritmu pamatujeme cenu zat´ım nejlepˇs´ıho nalezen´eho ˇreˇsen´ı, lze za urˇcit´ ych podm´ınek proˇrezat strom rekurze a vyhnout se v´ ypoˇctu nˇekter´ ych prvk˚ u sol(I). Nutnou podm´ınkou je monotonie funkce cost vzhledem k tomu, jak rozˇsiˇrujeme hledanou sekvenci.

35

Pˇredpokl´ adejme tedy, ˇze cost je neklesaj´ıc´ı. To znamen´a, ˇze vˇzdycky plat´ı cost(ha1 , . . . , ai i, I) 6 cost(ha1 , . . . , ai , ai+1 i, I). Pak, pokud je I instance minimalizaˇcn´ıho probl´emu a cost(ha1 , . . . , ai i, I) je vˇetˇs´ı neˇz cena doposud nejlepˇs´ıho nalezen´eho ˇreˇsen´ı, tak ha1 , . . . , ai i nen´ı moˇzn´e doplnit na optim´aln´ı ˇreˇsen´ı (cena optim´aln´ı ˇreˇsen´ı je menˇs´ı nebo rovna cenˇe nejlepˇs´ıho doposud nalezen´eho ˇreˇsen´ı). Du´aln´ı princip plat´ı pro nerostouc´ı cenovou funkci a maximalizaˇcn´ı probl´emy. Pokud existuje efektivn´ı aproximaˇcn´ı algoritmus k dan´emu optimalizaˇcn´ımu probl´emu, je cenu ˇreˇsen´ı, kter´e tento algoritmus vr´ at´ı, moˇzn´e pouˇz´ıt k inicializaci ceny doposud nejlepˇs´ıho nalezen´eho ˇreˇsen´ı. Pˇr´ıstupy popsan´e v pˇredchoz´ıch dvou odstavc´ıch se v literatuˇre oznaˇcuj´ı jako branch-and-bound. Set cover je slavn´ y“ optimalizaˇcn´ı probl´em, hojnˇe studovan´ y pˇredevˇs´ım v oblasti aproximaˇcn´ıch algoritm˚ u. ” Jeho zad´ a n´ ı je jednoduch´ e . Jsou d´ a ny mnoˇ z ina X a syst´ e m jej´ ıch podmnoˇ z in S, kter´ y tuto mnoˇ z inu pokr´ y v´ a (tj. S ´ plat´ı S = X). Ukolem je nal´ezt co nejmenˇs´ı podmnoˇzinu S tak, aby st´ale pokr´ yvala X. Set Cover

Pˇr´ıpustn´ a ˇreˇsen´ı:

koneˇ a mnoˇzina X, syst´em podmnoˇzin S = {Si | Si ⊆ X} takov´ y, Scn´ ˇze Si ∈S Si = X S C ⊆ S takov´e, ˇze Si ∈C Si = X

Cena ˇreˇsen´ı:

cost(X, S, C) = |C|

C´ıl:

minimum

Instance:

Idea algoritmu je tedy generovat podmnoˇziny S, kter´e pokr´ yvaj´ı X a vybrat tu s nejmenˇs´ım poˇctem prvk˚ u. K tomuto u ´ˇcelu m˚ uˇzeme opˇet pouˇz´ıt jako kostru Generate. Podmnoˇziny n prvkov´e mnoˇziny totiˇz jednoznaˇcnˇe odpov´ıdaj´ı n prvkov´ ym variac´ım nad {0, 1}. Uvaˇzme mnoˇzinu Y. Pak pro kaˇzdou podmnoˇzinu Z t´eto mnoˇziny m˚ uˇzeme definovat jej´ı charakteristickou funkci µZ : Y → {0, 1} jako  0 y∈ /Z µZ (y) = 1 y∈Z Mezi charakteristick´ ymi funkcemi a podmnoˇzinami je jednoznaˇcn´ y vztah. Kaˇzd´a podmnoˇzina Z indukuje unik´ atn´ı charakteristickou funkci, a naopak, je-li d´ ana charakteristick´a funkce µ : Y → {0, 1} pak mnoˇzinu Set(µ), kter´ a tuto funkci indukuje nalezneme jako Set(µ) = {y ∈ Y | µ(y) = 1}. Pokud zafixujeme poˇrad´ı prvk˚ u v mnoˇzinˇe X, tj X = {x1 , x2 , . . . , xn }, d´a se kaˇzd´a podmnoˇzina Z ⊆ X jednoznaˇcnˇe zapsat jako sekvence hµZ (x1 ), µZ (x2 ), . . . , µZ (xn )i. Ke vygenerov´an´ı vˇsech podmnoˇzin S tedy staˇc´ı generovat vˇsechny n-prvkov´e sekvence nad {0, 1}. V dalˇs´ım budeme znaˇcit jako Set(ha1 , . . . , ai i) podmnoˇzinu, kter´ a odpov´ıd´ a sekvenci ha1 , . . . , ai i doplnˇen´e na konci potˇrebn´ ym poˇctem 0. Zamysleme se nad podm´ınkami, pomoc´ı nichˇz lze oˇrezat strom rekurze. Uvaˇzujme situaci, kdy m´ame vygenerov´ anu sekvenci ha1 , . . . , ai i. Potom m˚ uˇzeme vyuˇz´ıt n´asleduj´ıc´ı (nezapom´ınejme, ˇze pracujeme s mnoˇzinami, jejichˇz prvky jsou podmnoˇziny X, takˇze Set(ha1 , . . . , ai i) je podmnoˇzina S). S S - Pokud Set(ha1 , . . . , ai i) ∪ (S \ {S1 , . . . , Si }) 6= X, pak m˚ uˇzeme rekurzi ukonˇcit, protoˇze ha1 , . . . , ai i nen´ı moˇzn´e doplnit tak, aby pokryla celou mnoˇzinu X. S - Pokud Set(ha1 , . . . , ai i) = X, tak konˇc´ıme rekurzi, protoˇze hled´ame minim´aln´ı pokryt´ı X a pˇrid´ avat dalˇs´ı prvky do Set(ha1 , . . . , ai i) proto nem´a smysl. - Pokud je |Set(ha1 , . . . , ai i)| vˇetˇs´ı neˇz velikost doposud nejmenˇs´ıho nalezen´eho pokryt´ı, konˇc´ıme rekurzi. Hled´ ame minim´ aln´ı pokryt´ı a pokraˇcovat v pˇrid´av´an´ı prvk˚ u do Set(ha1 , . . . , ai i) nem´a smysl. V´ ypoˇcet optim´ aln´ıho ˇreˇsen´ı spust´ıme pomoc´ı OptimalSetCover(hi, S, X). Algoritmus si uchov´av´a v glob´ aln´ı promˇenn´e C zat´ım nejlepˇs´ı nalezen´e pokryt´ı, kter´e na zaˇc´atku nastav´ı na celou mnoˇzinu S Na ˇr´adku 5 pak testujeme, jestli jsme nalezli pokryt´ı. Pokud ano, je toto pokryt´ı urˇcitˇe lepˇs´ı neˇz C. Na ˇr´adku 9 totiˇz testujeme 36

Algoritmus 17 Set Cover pomoc´ı branch-and-bound 1: C ← S . Glob´ aln´ı promˇenn´a pro uchov´an´ı zat´ım nejlepˇs´ıho nalezen´eho pokryt´ı 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

procedure S OptimalSetCover(ha1 , . . . , ai i, F, X) Y ← Set(ha1 , . . . , ai i) if Y = X then C ← Set(ha1 , . . . , ai i) return S if Y ∪ F 6= X or |Set(ha1 , . . . , ai i)| = |C| − 1 then return OptimalSetCover (ha1 , . . . , ai , 1i, F \ {Si+1 }, X) OptimalSetCover (ha1 , . . . , ai , 0i, F \ {Si+1 }, X)

. test, jestli ha1 , . . . , ai i uˇz neindukuje pokryt´ı . ha1 , . . . , ai i je zat´ım nejlepˇs´ı pokryt´ı . nem˚ uˇzu vytvoˇrit lepˇs´ı pokryt´ı neˇz je C

velikost doposud vygenerovan´e podmnoˇziny. Pokud je jenom o 1 menˇs´ı neˇz C, tak ukonˇc´ıme rekurzi. Pˇrid´ an´ım dalˇs´ıho prvku bychom totiˇz mohli dostat jenom pokryt´ı, kter´e je alespoˇ n tak velk´e jako C. Na stejn´em ˇr´ adku tak´e testujeme, zda-li lze aktu´ aln´ı podmnoˇzinu rozˇs´ıˇrit na pokryt´ı. Pokud ne, rekurzi ukonˇc´ıme.

´ Uloha batohu Pouˇzit´ı backtrackingu vede vˇetˇsinou (u vˇsech pˇr´ıklad˚ u, kter´e jsme si uk´azali, tomu tak bylo) k algoritmu s horˇs´ı neˇz polynomickou sloˇzitost´ı. Toto je pˇrirozen´e, backtracking vˇetˇsinou pouˇz´ıv´ame k nalezen´ı (optim´aln´ıho) ˇreˇsen´ı probl´emu, kter´e povaˇzujeme za prakticky neˇreˇsiteln´ y (jako SAT, Set Cover nebo u ´loha n dam). Mohlo by se tedy zd´ at, ˇze bactracking nen´ı pro vˇetˇs´ı instance pˇr´ıliˇs pouˇziteln´ y. V t´eto kapitole si ale uk´aˇzeme, jak se d´ a backtracking zkombinovat s algoritmem navrˇzen´ ym jin´ ym zp˚ usobem a vylepˇsit tak jeho v´ ykon (tak, ˇze algoritmus spoˇc´ıt´ a ˇreˇsen´ı, kter´e je v pr˚ umˇern´em pˇr´ıpadˇe bliˇzˇs´ı optim´aln´ımu ˇreˇsen´ı). Uk´aˇzeme si to na pˇr´ıkladu u ´lohy batohu. Tento optimalizaˇcn´ı probl´em definovan´ y jako ´ Uloha batohu Instance:

{(b, w1 , . . . , wn ) | b, w1 , . . . , wn ∈ N}

Pˇr´ıpustn´ a ˇreˇsen´ı: Cena ˇreˇsen´ı:

sol(b, w1 , . . . , wn ) = {C ⊆ {1, . . . , n} | P cost(C, (b, w1 , . . . , wn )) = i∈C wi

C´ıl:

maximum

P i∈C

wi 6 b}

Idea algoritmu je n´ asleduj´ıc´ı. Pro k 6 n nejdˇr´ıve vygenerujeme vˇsechny podmnoˇziny mnoˇziny {1, . . . , n} do velikosti k, takov´e, ˇze pro kaˇzdou z nich je suma vah jim odpov´ıdaj´ıc´ıch prvk˚ u menˇs´ı neˇz b. V druh´e f´ azi algoritmu se kaˇzdou z podmnoˇzin pokus´ıme rozˇs´ıˇrit tak, ˇze budeme ˇzrav´ ym zp˚ usobem pˇrid´avat dalˇs´ı prvky {1, . . . , n}. Vybereme takovou rozˇs´ıˇrenou mnoˇzinu, suma jej´ıchˇz prvk˚ u je nejvˇetˇs´ı. Sloˇzitost algoritmu z´ avis´ı mimo velikosti vstupn´ı instance i na volbˇe k. Pokud k = 0 je KnapsackScheme jenom obyˇcen´ ym greedy algoritmem se sloˇzitost´ı O(n log n). Situace je podobn´a, pokud uvaˇzujeme k jako pevnˇe danou konstantu a poˇc´ıt´ ame sloˇzitost algoritmu z´ avislou jenom na n. Poˇcet kandid´at˚ u je pak totiˇz roste polynomicky, jejich poˇcet je vˇzdy omezen O(nk ) (kandid´ aty totiˇz poˇc´ıt´ame jako k prvkov´e variace bez opakov´an´ı) a tedy sloˇzitost cel´eho algoritmu je polynomick´ a v z´ avisloti na n. Z toho tak´e plyne, ˇze v z´avislosti na k roste sloˇzitost algoritmu exponenci´ alnˇe.

37

Algoritmus 18 Kombinace backtrackingu a greedy pˇr´ıstupu pro u ´lohu batohu 1: procedure GenerateCandidates(ha1 , . . . , ai i, (b, w1 , . . . , wn ), k) P 2: if i∈Set(ha1 ,...,ai i) wi > b then 3: return ∅ 4: if |Set(ha1 , . . . , ai i)| = k or i = n then 5: return {Set(ha1 , . . . , ai i)} 6: X ← GenerateCandidates(ha1 , . . . , ai , 1i, (b, w1 , . . . , wn ), k) 7: Y ← GenerateCandidates(ha1 , . . . , ai , 0i, (b, w1 , . . . , wn ), k) 8: return X ∪ Y 9: 10: 11: 12: 13: 14:

procedure ExtendCandidate(C, (b, w1 , . . . , wn )) Vytvoˇr prioritn´ı frontu Q z prvk˚ u 1, . . . , n uspoˇr´adanou sestupnˇe podle odpov´ıdaj´ıc´ıch prvk˚ u w1 , . . . , wn while Q nen´ı pr´ azdn´ a do Odeber z Q prvek P x if x ∈ / C and i∈C +wx 6 b then 15: C ← C ∪ {x} 16: return C

17: 18: 19: 20: 21: 22:

procedure KnapsakScheme((b, w1 , . . . , wn ), k) X ←GenerateCandidates(hi, (b, w1 , . . . , wn ), k) B←∅ for x ∈ X do A ←ExtendCandidate(x, (b, w1 , . . . , wn )) P P 23: if x∈A wx > x∈B wx then 24: B←A 25: return B

38