Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2004-2005‎ > ‎

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.

FELADATOK


Comments