Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : DynamickéProgramování

Matfiz: DynamickéProgramování

Dynamické programování

Dle Holanovy přednášky z Programování 23. dubna.

Rada do života;): Když «přirozený» algoritmus má exponenciální složitost, měli bychom se zamyslet nad řešením pomocí dynamického programování.

Vhodné na optimalizační úlohy, kdy se optimální řešení skládá z optimálních řešení «menších» úloh.

Motivační úlohy

Více méně podle stoupající složitosti (tzn. v pořadí, v němž byly řešeny na přednášce):

  1. Úloha Záhony
  2. Úloha Děti Do Skupin
  3. Úloha Nejdelší Rostoucí Podposloupnost
  4. Úloha Editační Vzdálenost
  5. (násobení několika matic, tohle si nepíšu, už jsme to dělali na cvičeních, doplňte to někdo...)
  6. Úloha Optimální Vyhledávací Strom

Často, když mám řešení rekurzí a přidám do něj cachování výsledků, získám ekvivalent dynamického řešení (jenom tak trochu z druhého konce, taky ale nemusím řešit pořadí vyplňování tabulky, protože se mi vyřeší samo).