Efektívne algoritmy a zložitosť - 04 - Dynamické programovanie

Zhrnutie prednášky

Prednáška úvodom ukazuje úlohu o lodičkách s utečencami, kde z dvoch po sebe idúcich lodičiek možno prijať iba jednu a cieľom je zachrániť čo najviac ľudí. Na príkladoch (napr. 1, 60, 100, 60) sa ukazuje, že greedy výber lodičky s najväčším počtom utečencov nevedie k optimu. Riešením je dynamické programovanie: úloha sa rozloží na podproblémy N_i pre prvých i lodičiek a rozborom prípadov (i-tá lodička pristane alebo sa vráti) vznikne rekurencia N_i = max(A_i + N_{i-2}, N_{i-1}) so základnými prípadmi N_0 = 0 a N_1 = A_1. Algoritmus plní pole zľava doprava v jedinom cykle, a preto má časovú zložitosť Θ(n), čo je ukázané na krokovom príklade.

• - Greedy výber lodičky s najviac utečencami nemusí viesť k optimálnemu riešeniu.
• - Podproblém N_i je najväčší počet zachránených utečencov pre lodičky A_1 až A_i.
• - Rozbor prípadov pre poslednú lodičku: buď pristane (A_i + N_{i-2}), alebo sa vráti späť (N_{i-1}).
• - Rekurencia: N_i = max(A_i + N_{i-2}, N_{i-1}).
• - Základné prípady: N_0 = 0 a N_1 = A_1.
• - Podproblémy sa počítajú v poli od najmenšieho po najväčší a výsledkom je N_n.
• - Časová zložitosť algoritmu je Θ(n), keďže ide o jeden cyklus s konštantnými operáciami.

Zhrnutie pripravené s pomocou AI z prepisu videa.