V tomto kurzu se dozvíte, co je dynamické programování. Také najdete srovnání mezi dynamickým programováním a chamtivými algoritmy k řešení problémů.
Dynamické programování je technika počítačového programování, která pomáhá efektivně řešit třídu problémů, které mají překrývající se dílčí problémy a optimální vlastnost podstruktury.
Takové problémy zahrnují opakované počítání hodnoty stejných dílčích problémů, aby se našlo optimální řešení.
Příklad dynamického programování
Vezměte případ generování fibonacciho sekvence.
Pokud je sekvence F (1) F (2) F (3) … F (50), řídí se pravidlem F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Všimněte si, jak existují překrývající se dílčí problémy, musíme vypočítat F (48), abychom vypočítali jak F (50), tak F (49). To je přesně ten druh algoritmu, kde svítí dynamické programování.
Jak funguje dynamické programování
Dynamické programování funguje tak, že ukládá výsledek dílčích problémů, takže když jsou požadována jejich řešení, jsou po ruce a nemusíme je přepočítávat.
Tato technika ukládání hodnoty dílčích problémů se nazývá memoizace. Uložením hodnot do pole ušetříme čas na výpočty dílčích problémů, na které jsme již narazili.
var m = mapa (0 → 0, 1 → 1) funkce fib (n), pokud klíč n není v mapě mm (n) = fib (n - 1) + fib (n - 2) návrat m (n)
Dynamické programování memoizací je přístup shora dolů k dynamickému programování. Obrácením směru, ve kterém algoritmus funguje, tj. Vycházením ze základního případu a prací na řešení, můžeme také implementovat dynamické programování způsobem zdola nahoru.
funkce fib (n), pokud n = 0 návrat 0 jinak var prevFib = 0, currentFib = 1 opakování n - 1 krát var newFib = prevFib + currentFib prevFib = currentFib currentFib = newFib návratový proudFib
Rekurze vs dynamické programování
Dynamické programování se většinou používá u rekurzivních algoritmů. To není náhoda, většina optimalizačních problémů vyžaduje rekurzi a pro optimalizaci se používá dynamické programování.
Ale ne všechny problémy, které používají rekurzi, mohou používat dynamické programování. Pokud nedochází k překrývajícím se subproblémům, jako je problém s posloupností fibonacci, může rekurze dosáhnout řešení pouze pomocí přístupu rozděl a panuj.
To je důvod, proč rekurzivní algoritmus, jako je Merge Sort, nemůže používat dynamické programování, protože dílčí problémy se nijak nepřekrývají.
Chamtivé algoritmy vs dynamické programování
Greedy Algorithms are similar to dynamic programming in the sense that they are both tools for optimization.
Chamtivé algoritmy však hledají lokálně optimální řešení nebo jinými slovy chamtivou volbu v naději na nalezení globálního optima. Proto chamtivé algoritmy mohou udělat odhad, který v té době vypadá optimálně, ale stává se nákladným a nezaručuje celosvětově optimální.
Dynamické programování na druhé straně najde optimální řešení pro dílčí problémy a poté provede informovanou volbu, aby spojilo výsledky těchto dílčích problémů a našlo nejoptimálnější řešení.
