3. Lacný polozisk vzorové riešenie

3 5
0 6 3 -2 9
3 6 -1 8 2
5 -7 1 2 0

37

Za úlohu sme mali prejsť z ľavého horného do pravého dolného políčka mriežky tak, aby sme maximalizovali súčet hodnôt prejdených políčok. Mohli sme pri tom chodiť iba hore, dole a doprava.

Jednoducho, neefektívne, funkčne

Ak nevieme, čo s úlohou, niet lepšieho nápadu, ako napísať riešenie hrubou silou. Možno si potom niečo všimneme a budeme takéto riešenie vedieť prerobiť na nejaké rýchlejšie.

Nuž, keďže chceme hrubú silu, vyskúšajme všetky možnosti. Ináč povedané, skúsme postupne každú možnú cestu z ľavého horného, na pravé dolné políčko. Samozrejme, chceme skúšať iba tie cesty, kde nechodíme doľava, pretože to predsa nesmieme. Pre každú cestu zrátame súčet hodnôt prejdených políčok. Z nich nakoniec vypíšeme maximum.

Ako niečo takého naprogramovať? Jednoduchým riešením je rekurzia. O každom políčku si budeme pamätať, či už sme cez neho prešli, alebo nie. Tiež si budeme pamätať, na ktorom políčku aktuálne stojíme.

Aké máme možnosti, keď stojíme na políčku \([r, c]\)? Môžeme sa pohnúť hore, teda na políčko \([r - 1, c]\), dole, teda na políčko \([r + 1, c]\), alebo doprava, teda na políčko \([r, c + 1]\). Samozrejme, ak je dané políčko už označené ako navštívené, alebo ak neexistuje (teda je mimo mriežky), tak naň stúpiť nemôžeme. Ktorú možnosť si vybrať? Keďže skúšame všetky možnosti, tak si postupne vyberieme všetky. Políčko, na ktoré sa rozhodneme ísť označíme ako navštívené. K aktuálnemu súčtu si pripočítame hodnotu daného políčka a rekurzívne sa zavoláme na to políčko. Ked sa vrátime z rekurzie, označíme ho opäť ako nenavštívené a skúsime ďalšiu možnosť. Takto postupne preveríme všetky 3 možnosti pre dané políčko.

Samozrejme, ak sa rekurziou zavoláme až na políčko \([R - 1, C - 1]\), tak sa ďalej nevoláme, ale iba si zapamätáme maximum z doterajšieho maxima a aktuálneho súčtu políčok a vrátime sa z rekurzie.

Technika, ktorú sme použili sa volá rekurzívny backtracking a na napísanie riešenia hrubou silou sa dá použiť veľmi často.

Akú to má zložitosť? Keďže skúšame všetky cesty, tak to určite bude aspoň toľko, koľko je ciest. A koľko to je? Nuž, to nie je celkom jednoduché.

Ľahko však spravíme horný odhad. Na každom z \(RC\) políčok skúšame 3 možnosti. Každú cestu aj naozaj prejdeme. Najdlhšia možná cesta má nanajvýš \(RC\) políčok. Horný odhad teda bude \(O(RC \cdot 3^{RC})\).

Môžeme spraviť aj dolný odhad. Keby sme chodili iba dole a doprava, tak by sme dokopy vždy spravili \(R + C\) krokov. Práve \(R\) z nich bude doprava. Počet takýchto ciest teda bude \((R + C) \cdot {R+C \choose R}\). Tým, že pridáme možnosť chodiť aj hore nám počet týchto ciesť nezníži.

Časová zložitosť nášho programu je niekde medzi tým. Malo by to stačiť na prvú sadu.

Pamäť je \(O(RC)\).

Z hrubej sily vzorák?

Ako sme už povedali, niekedy stačí malé pozorovanie, aby sme z riešenia hrubou silou spravili vzorák.

Skúsme si pre každé políčko zrátať, koľko by sme zarobili, keby sme na ňom začínali, ale nemohli stúpiť na políčko \([r, c]\).

Naša nová rekurzia si okrem súradníc políčka, na ktorom stojíme, pamätá aj to, na ktoré políčko nesmieme stúpiť. Nepotrebujeme teda už veľké dvojrozmerné pole navštívených políčok. Totiž, ak si pamätáme iba to, na ktorom políčku sme boli bezprostredne predtým, ako sme sa dostali na to aktuálne, tak určite na žiadne políčko nestúpime dvakrát. Je to kvôli tomu, že nemôžeme chodiť doľava. Rozmyslite si, že nám táto informácia naozaj stačí.

Dokonca nepotrebujeme ani súradnice predchádzajúceho políčka. Stačí nám vedieť smer, z ktorého sme prišli, čo si môžeme reprezentovať napríklad číslami 1, 2, 3. Naša rekurzia má teda stav riadok, stlpec, odkial.

Všimnime si teraz veľmi užitočnú vec. Ak už niekedy zrátame odpoveď pre nejaký stav riadok, stlpec, odkial, tak už nikdy ho nemusíme rátať znova. Stačí, ak si zapamätáme výsledok a keď ho budeme potrebovať zrátať nabudúce, iba sa pozrieme na ten výsledok, ktorý máme uložený.

Vnútro našej rekruzívnej funkcie teda bude vyzerať asi tak, že sa najskôr pozrieme, či už nie sme na pravom dolnom políčku. Ak áno vrátime ako odpoveď 0. Ak nie sme, tak sa pozrieme, či už nemáme výsledok pre aktuálny stav uložený. Ak áno, tak ho vrátime. Ak ho nemáme uložený, tak sa rekurzívne zavoláme do tých dvoch, alebo troch smerov, do ktorých môžeme. Skúšame totiž 3, ale z jedného sme možno prišli, takže tam nepôjdeme. Nakoniec si iba zapamätáme odpoveď pre aktuálny stav a vrátime ju.

Na konci iba vypíšeme odpoveď pre stav 0, 0, -1.

Akú to má zložitosť? Každý stav zrátame v \(O(1)\), pretože sa iba dvakrát rekurzívne zavoláme. Stavov je \(R \cdot C \cdot 3\). Celková časová zložitosť teda bude \(O(RC)\). Pamätáme si vstup a odpovede pre všetky stavy, takže aj pamäť bude \(O(RC)\).

Jeden problém, ktorý sa môže vyskytnúť je hĺbka rekurzie. Môže nám totiž dôjsť miesto na zásobníku. To má ale jednoduché riešenie. Nezavoláme sa hneď na výsledný stav, ale budeme sa postupne volať od posledných stavov až k tomu, ktorý nás najviac zaujíma.

Technika zapamätávania si už zrátaných výsledkov sa zvykne označovať ako dynamické programovanie. My sme tu použili jeho rekurzívnu formu, ktorá sa často nazýva rekurzia s memoizáciou. Samozrejme, táto úloha sa dá riešiť rovnako jednoducho aj iteratívne, rekurzia je však pre množstvo ľudí o niečo intuitívnejšia.