Co je to

dynamické programování?

Dynamické programování

Dynamické programování je postup řešení úloh, který počítá výsledky z menších podvýsledků. Využíváme ho tehdy, když můžeme výsledek celé úlohy jednoduše spočítat z řešení menších částí úlohy. Často tedy například z řešení pro n prvků vytvoříme řešení pro n+1 prvků (pokud ses někdy setkal(a) s matematickou indukcí, může ti tahle myšlenka být povědomá).

Fibonacciho čísla

Ukázkovým příkladem dynamického programování je výpočet n-tého čísla ve Fibonacciho posloupnosti. To je posloupnost, jejíž první dva členy jsou jednička (F_1 = 1, F_2 = 1) a každý další člen je součet dvou předchozích, tedy F_n=F_{n-1}+F_{n-2}.

Kdybychom chtěli počítat Fibonacciho čísla, mohli bychom to udělat pomocí následující rekurzivní funkce (rekurzivní znamená, že funkce volá sama sebe).

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Pomocí této funkce vypíšeme prvních sto Fibonacciho čísel následovně:

for i in range(1, 100):
    print(i, fibonacci(i))

A nebo ne? Problém s naší funkcí je, že její výpočetní složitost dramaticky roste. Výpočet F_n jsme totiž převedli na dva menší výpočty F_{n-1} a F_{n-2}. Každý z nich jsme opět převedli na dva menší výpočty: F_{n-1} jsme převedli na výpočet F_{n-2} a F_{n-3}, zatímco výpočet F_{n-2} jsme převedli na výpočet F_{n-3} a F_{n-4}. Protože v každém rekurzivním kroku zdvojnásobujeme počet volaných funkcí, roste výpočetní složitost exponenciálně. Pokud tedy spustíš program nahoře, dostaneš bleskově prvních pár desítek Fibonacciho čísel, ale po chvíli se postup v podstatě zastaví.

Existuje jednoduchý trik, jak tento problém napravit. Stačí si počítat Fibonacciho čísla postupně v pořadí od prvního čísla až po n-té. Ve chvíli, kdy počítáme n-té číslo F_n, využijeme, že již známe hodnotu F_{n-1} a F_{n-2}. Hodnotu F_n dostaneme jednoduše sečtěním těchto dvou čísel. Nový program vypadá velice podobně jako původní rekurzivní řešení, v čem je rozdíl? Pokud jsme v předchozím řešení počítali hodnotu F_n, převedli jsme tento výpočet na výpočet menších Fibonacciho čísel, ale každé z nich jsme museli spočítat mnohokrát. V novém řešení pro každé Fibonacciho číslo uděláme jen jeden výpočet, a složitost nového algoritmu je proto lineární, tj. výpočet prvních n Fibonacciho čísel zabere O(n) času.

fibonacciho_cisla = [1, 1] # první dvě Fibonacciho čísla mají hodnotu 1
for i in range(2, 100):
    # Výsledek počítáme z menších podvýsledků
    dalsi_cislo = fibonacciho_cisla[i - 1] + fibonacciho_cisla[i - 2]

    fibonacciho_cisla.append(dalsi_cislo)

for i in range(0, 100): # Vypíšeme prvních 100 Fibonacciho čísel
    print(i + 1, fibonacciho_cisla[i])

Chceš-li si vyřešit nějakou úlohu, která dynamické programování využívá, doporučujeme úlohu Lampy na ulici nebo úlohu Evoluce. Pro odvážné se nabízí také úloha Nákup.

Podrobnější vysvětlení a další příklady využití dynamického programování můžeš také najít v kuchařce KSP o dynamickém programování.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)