Playmath, Vol. IV No. 10, 2006.
Stručni rad
Dinamičko programiranje 2
Ivo Sluganović
Sažetak
U 7. broju PlayMath-a mogli ste pročitati
članak o dinamičkom programiranju. Budući da je ova metoda
rješavanja iznimno složena i primjenjiva na velik broj zadataka, u
prošlom sam broju uspio objasniti samo najjednostavnije
primjere, a nisam spomenuo jedan, možda i jednostavniji, pristup
rješavanju problema koji imaju svojstva potrebna da bi ih mogli
rješavati uz pomoć dinamičkog programiranja. Ideja je da zadatak
rješavamo rekurzijom, ali da na neki način izbjegnemo
bespotrebno računanje istih potproblema više puta.
To ćemo učiniti
tako što ćemo, kada jednom izračunamo rješenje nekog potproblema, to
rješenje zapamtiti i kada nam sljedeći puta zatreba, jednostavno ga
pročitati s mjesta gdje smo ga zapamtili. Ovakav način rješavanja
naziva se memoizacija.
Ključne riječi
memoizacija; rekurzija; algoritmi; dinamičko programiranje
Hrčak ID:
3599
URI
Datum izdavanja:
15.4.2006.
Posjeta: 1.744 *