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í.
