ADŠ prednáška 19: Dynamické programovanie 3 - max. rastúca podpostupnosť, rekonštrukcia opt riešenia

Zhrnutie prednášky

Prednáška pokračuje v téme dynamického programovania a rekapituluje postup riešenia: najprv rekurzívne riešenie hrubou silou ako matematická funkcia, potom využitie optimálnej substruktúry a memoizácia, ktorá znižuje exponenciálnu zložitosť na polynomiálnu. Na úlohe o počte ciest po mriežke Manhattanu s blokovanými križovatkami sa porovnáva rekurzívny prístup s memoizáciou a iteratívny prístup vypĺňajúci tabuľku. Iteratívne riešenie je v praxi rýchlejšie, pretože nemá réžiu volania funkcií a je priateľské k cache procesora vďaka sekvenčnému prístupu do pamäte po riadkoch. Rekurzívne riešenie má naopak výhodu v tom, že vyhodnotí len podproblémy, ktoré sú pre výsledok skutočne potrebné. Názov prednášky naznačuje, že ďalej nasleduje najdlhšia rastúca podpostupnosť a rekonštrukcia optimálneho riešenia.

• - Postup riešenia: rekurzívny backtracking ako funkcia, hľadanie optimálnej substruktúry, pridanie memoizácie.
• - Memoizácia mení exponenciálnu časovú zložitosť na polynomiálnu, ak sa podproblémy opakujú.
• - Iteratívne DP vyžaduje usporiadať podproblémy tak, aby každý závisel len od predchádzajúcich.
• - Obe implementácie úlohy o cestách po mriežke majú rovnakú asymptotickú zložitosť úmernú počtu políčok.
• - Iteratívne riešenie je rýchlejšie v konštantnom faktore: nemá réžiu volania funkcií a lepšie využíva cache pri prechode po riadkoch.
• - Rekurzívne riešenie počíta len relevantné podproblémy, takže pri veľkom počte prekážok môže ušetriť prácu.
• - Pri dvojrozmerných poliach záleží na poradí prechodu (po riadkoch vs. po stĺpcoch), lebo pole leží v pamäti súvisle po riadkoch.

Zhrnutie pripravené s pomocou AI z prepisu videa.