Dynamické programování

V této poslední části se pustíme do dynamického programování. Pod tímto názvem si možná můžete představit něco trochu jiného, než co to ve skutečnosti je. V této části se to dozvíte.

Co je to dynamické programování

Dynamické programování je metoda pro řešení problému. Spočívá v tom, že se řešený problém rozdělý na menší podproblémy. Tyto podproblémy se potom zvlášť řeší a ukládá se jejich výsledek, aby se nemuseli řešit znovu. Tato metoda se nedá použít na všechny problémy, ale u některých problémů na které ji použít můžeme, dokáže hodně zlepšit efektivitu našeho kódu.

Dynamické programování můžeme použít jen na problémy, které se dají rozdělit na podproblémy, ale řešení těchto podproblémů se musí dát použít v problému opakovaně. Kromě toho musí problém mít optimální podstrukturu. To znamená, že se jeho optimální řešení musí dát zkonstruovat z optimálních řešení jeho podproblémů. Pokud to moc nechápete, tak nevadí, až se do dynamického programování pustíme, možná to pochopíte.

Jaký problém vyřešíme

Abychom si ukázali použití dynamického programování, tak si vyřešíme nějaký problém. Budeme chtít napsat funkci, která vrátí požadované číslo z Fibonacciho posloupnosti. Jedná se o matematickou posloupnost, začínající čísly 0 a 1. Každé další číslo je ve Fibonacciho posloupnosti součet dvou předcházejících čísel. Takže třetí číslo ve Fibonacciho posloupnosti bude 1, čtvrté 2, páté 3, šesté 5, a tak dále. Následující ukázka začátek Fibonacciho posloupnosti ukazuje.

Vyřešení problému bez dynamického programování

Než si ukážeme vytvoření funkce pro získání čísla z Fibonacciho posloupnosti pomocí dynamického programování, tak si ji nejdříve naprogramujeme bez dynamického programování. Alespoň uvidíme, jak nám dynamické programování může náš kód v některých případech udělat mnohem efektivnějším.

Následující ukázka ukazuje funkci fib, která pro získání požadovaného čísla z Fibonacciho posloupnosti používá rekurzy. Víme že první číslo Fibonacciho posloupnosti je 0, a druhé a třetí číslo je 1. Pokud do funkce tedy předáme hodnotu od 1 do 3, tak můžeme hned vrátit 0 nebo 1. Pokud ale do funkce předáme větší číslo než je 3, tak nevíme jaké pro něj máme vrátit Fibonacciho číslo. Víme ale, že Fibonacciho číslo získáme sečtením dvou předešlých čísel ve Fibonacciho posloupnosti a zavoláme tedy funkci fib rekurzivně pro dvě předešlá čísla, vrácené hodnoty sečteme a vrátíme výsledek.

function fib(n) {
    // první číslo ve Fibonacciho posloupnosti je 0, tak se vrátí, pokud je n 1
    if (n === 1) return 0;
    // druhé a třetí číslo ve Fibonacciho posloupnosti je 1, tak se vrátí, pokud je n 2 nebo 3
    if (n <= 3) return 1;
    // n-té číslo ve Fibonacciho posloupnosti se rovná součtu dvou předchozích čísel ve Fibonacciho
    // posloupnosti, takže funkce vrátí součet dvou předchozích čísel ve Fibonacciho posloupnosti
    return fib(n-1) + fib(n-2);
}

const vysledek = fib(6);
console.log("Šesté číslo ve Fibonacciho posloupnosti je: " + vysledek);

Vyřešení problému pomocí dynamického programování

Předchozí ukázka kódu ukazovala vytvoření funkce bez dynamického programování. Tento kód je ale velmi náročný, má časovou náročnost O(2ⁿ). Pokud se podíváte na graf z části Big O Notation, tak můžete vidět, že časová náročnost velmi vzroste i při malém zvýšení čísla. Raději si ani nezkoušejte volat funkci fib z minulé ukázky s nějakým větším číslem (např. 100), pokud si nechcete zasekat prohlížeč. Tento problém ale můžeme u naší funkce vyřešit pomocí dynamického programování.

Na začátku této části jsem psal, že dynamické programování se dá použít na problémy, které se dají rozdělit na podproblémy, ale řešení těchto podproblémů se musí dát při řešení problému použít opakovaně. U naší funkce toto pravidlo platí. Když se podíváte na následující graf znázorňující volání funkce fib, tak zjistíte, že například pro číslo 4 se funkce fib volá dvakrát.

Dynamické programování spočívá v tom, že si pamatujeme řešení podproblémů a když se stejný podproblém vyskytne znovu, tak už pro něj máme řešení a nemusíme jej řešit ještě jednou. Náš kód můžeme předělat tak, aby se výsledky volání funkce fib někam ukládali a když potom budeme funkci fib volat ještě jednou, s argumentem se kterým jsme ji již v minulosti volali, tak se jen najde výsledek a hned se vrátí.

Předěláme si funkci fib tak, aby jako parametr kromě čísla přijímala také pole uchovávající výsledky jejího volání. Tento parametr bude volitelný, takže pokud jej při volání funkce nepředáme, nastaví se jako nové prázdné pole. Do tohoto pole budeme uvnitř funkce fib ukládat výsledky jejího volání a když funkci fib budeme ve funkci rekurzivně volat, tak budeme pole předávat (pole se předává adresou, nevytváří se nové). Když později zjistíme, že jsme funkci fib s nějakým parametrem již volali, tak můžeme v poli jen najít výsledek a vrátit jej.

// funkce fib nyní bere jako parametr také pole (odkaz na pole v paměti), které uchovává výsledky volání funkce fib
function fib(n, memo = []) {
    // pokud se funkce fib s tímto parametrem již v minulosti volala, tak se jen vrátí výsledek uložený v poli memo
    if (memo[n] !== undefined) return memo[n];
    if (n === 1) return 0;
    if (n <= 3) return 1;
    const result = fib(n-1, memo) + fib(n-2, memo);
    // výsledek volání funkce fib s argumentem n se uloží do pole memo pod indexem n
    memo[n] = result;
    return result;
}

const vysledek = fib(6);
console.log("Šesté číslo ve Fibonacciho posloupnosti je: " + vysledek);

V předchozí ukázce jsme pro funkci na získání čísla z Fibonacciho posloupnosti použili dynamické programování. Zapamatovávali jsme si výsledky operací, které jsme provedli, abychom je mohli v budoucnu použít a nezískávat je znovu. Díky tomu jsme snížili časovou náročnost naší funkce na O(n), což je o dost lepší než O(2ⁿ).

Top-Down vs. Bottom-Up

K dynamickému programování existují dva přístupy: Top-Down a Bottom-Up. Top-Down přístup jsme již použili a znamená to, že začneme u nejsložitějšího problému a řešíme stále jednodušší podproblémy. Nejprve funkci fib zavoláme s nějakým číslem, pro které chceme získat Fibonacciho číslo a poté se ve funkci funkce fib rekurzivně volá pro stále menší čísla. Bottom-Up je opakem Top-Down. Bottom-Up znamená, že začneme s nejjednodušším podproblémem a řešíme stále složitější problémy. Pokud bychom tedy chtěli naši funkci fib předělat na Bottom-Up přístup, tak musíme nejdříve začít s výpočtem nejmenších Fibonacciho čísel a postupovat směrem nahoru k číslu, pro které chceme Fibonacciho číslo získat.

Následující ukázka ukazuje, jak bychom mohli naši funkci fib předělat, aby používala Bottom-Up přístup. Namísto rekurze je použit cyklus, který postupně zaplňuje pole, které se na začátku funkce vytváří, Fibonacciho posloupností.

function fib(n) {
    // do tohoto pole se budou postupně ukládat Fibonacciho čísla
    const fibNums = [0, 1, 1];
    // protože má první Fibonacciho číslo v poli fibNums index 0, tak se číslo n sníží o 1
    n--;
    // tento cyklus postupně zaplní pole fibNums Fibonacciho posloupností až k číslu, pro které se má Fibonacciho číslo získat
    for (let i = 3; i <= n; i++) {
        // do pole fibNums se přidá další číslo z Fibonacciho posloupnosti sečtením dvou posledních položek pole
        fibNums[i] = fibNums[i-1] + fibNums[i-2];
    }
    // vrácení požadovaného Fibonacciho čísla z pole fibNums
    return fibNums[n];
}

const vysledek = fib(6);
console.log("Šesté číslo ve Fibonacciho posloupnosti je: " + vysledek);

Myslím že Bottom-Up přístup se pro naši funkci hodí více. Vypadá lépe a navíc zabere méně paměti, protože nepoužívá rekurzy. Vlastně by mohla využít ještě méně paměti, protože v podstatě vždy potřebujeme znát jen poslední dvě čísla ve Fibonacciho posloupnosti abychom mohli vypočítat další. Tím už se ale zabývat nebudeme, cílem bylo jen ukázat rozdíl mezi Top-Down a Bottom-Up přístupem při dynamickém programování.