Ako memoizácia zvyšuje účinnosť dynamických programovacích algoritmov?

Memoizácia dramaticky zvyšuje účinnosť dynamických programovacích algoritmov tým, že sa vyhýba redundantným výpočtom. Dynamické programovanie rieši problémy tým, že ich rozdeľuje na menšie prekrývajúce sa podpísanie, vyrieši každý podproblém iba raz a ukladá svoje riešenia. Memoizácia je prístup zhora nadol na dosiahnutie tohto cieľa.

Takto to funguje:

1. rekurzívna štruktúra: Problémy s dynamickým programovaním sa často hodia k rekurzívnym riešeniam. Naivná rekurzívna implementácia by opakovane vypočítala riešenia rovnakých podskupín, čo by viedlo k exponenciálnej časovej zložitosti.

2. Ukladanie výsledkov: Memoizácia zavádza dátovú štruktúru (zvyčajne tabuľku hash alebo pole) na ukladanie riešení už vypočítaných podskupín. Táto štruktúra sa často nazýva „poznámka“ alebo „vyrovnávacia pamäť“.

3. Kontrola poznámky: Pred rekurzívnym vyriešením podpísanu algoritmus najskôr skontroluje poznámku. Ak je riešenie už prítomné (čo znamená, že subproblem bol vyriešený už predtým), je získaný priamo z poznámky, čím sa vyhýba rekomputácii.

4. Ukladanie výsledku: Ak sa riešenie nenachádza v memorande, algoritmus rekurzívne vyrieši podproblém a potom * uloží * výsledok do poznámky pred jeho vrátením.

Príklad:

Zvážte výpočet sekvencie fibonacci. Naivný rekurzívny prístup má exponenciálnu zložitosť, pretože prepočítava mnoho fibonacciho čísel viackrát. S memoizáciou:

`` `Python

memo ={} # inicializujte poznámku

def fibonacci_memo (n):

Ak n v memore:

return memo [n] # načítať z poznámky, ak už je vypočítaný

ak n <=1:

návrat n

inak:

Výsledok =fibonacci_memo (n-1) + fibonacci_memo (n-2)

Memo [n] =výsledok # uložte výsledok do poznámky

výsledok návratnosti

tlač (fibonacci_memo (5)) # výstup:5

`` `

V tomto príklade „Memo` ukladá vypočítané čísla fibonacci. Keď sa volá `fibonacci_memo (5)`, rekurzívne volá `fibonacci_memo (4)` a `fibonacci_memo (3)`. `Fibonacci_memo (3)` Rekurzívne volá `fibonacci_memo (2)` a `fibonacci_memo (1)`. Avšak, keď sa vypočíta a uloží v `memorandum, vypočíta sa a uloží„ fibonacci_memo (1) `alebo` fibonacci_memo (2) `. To znižuje časovú zložitosť z exponenciálneho na lineárne.

Memoizácia v podstate transformuje potenciálne exponenciálny rekurzívny algoritmus na lineárny čas (alebo polynomický čas v iných prípadoch) algoritmom využitím sily vyrovnávacej pamäte predtým vypočítané výsledky. Je to výkonná optimalizačná technika, ktorá sa často používa v spojení s dynamickým programovaním na zlepšenie efektívnosti.

• Predchádzajúca strana: Aká akcia by nebola súčasťou programu CAD? 
• Ďalšia strana: Môžete vysvetliť rozdiel medzi ukazovateľmi a premennými v programovacích jazykoch?