2.óra - Dinamikus programozás 1.
ELMÉLET
Belekezdtünk az alább olvasható feladat megoldásába. Egy általánosan alkalmazható algoritmustervezési stratégiát próbálunk megérteni a feladat elemzése révén. A módszer neve: dinamikus programozás.
A módszer alapelveit az Algoritmusok c. könyv alapján foglaljuk össze:
A dinamikus programozás éppúgy, mint az oszd meg és uralkodj módszer, a feladatot részfeladatokra való osztással oldja meg. Az oszd meg és uralkodj módszer felosztja a feladatot független részfeladatokra, melyeket ismételten megold, és a részfeladatok megoldásait az eredeti feladat megoldása céljából egyesíti. Ezzel szemben a dinamikus programozás akkor alkalmazható, ha a részproblémák nem függetlenek, azaz közös részproblémák vannak. Ilyen helyzetben az oszd meg és uralkodj módszer a szükségesnél többet dolgozik, mert ismételten megoldja a részproblémák közös részproblémáit. A dinamikus programozás minden egyes részfeladatot és annak minden részfeladatát pontosan egyszer oldja meg, az eredményt egy táblázatban tárolja, és ezáltal elkerüli az ismételt számítást, ha a részfeladat megint felmerül.
A dinamikus programozást optimalizálási feladatok megoldására használjuk. Ilyen feladatoknak sok megengedett megoldása lehet, ezek közül elegendő egy optimális (minimális vagy maximális) értékűt megtalálni.
Az algoritmus kifejlesztése négy lépésre bontható:
- Jellemezzük az optimális megoldás szerkezetét.
- Rekurzív módon definiáljuk az optimális megoldás értékét.
- Kiszámítjuk az optimális megoldás értékét alulról felfelé történő módon.
- A kiszámított információk alapján megszerkesztünk egy optimális megoldást.