Dinaminis programavimas - tai metodas, dažnai naudojamas optimizavimo uždaviniams spręsti. Šiame straipsnyje panagrinėsime, kaip šis metodas gali būti pritaikytas įvairiems uždaviniams, aptarsime optimalaus sprendinio struktūros nustatymą, algoritmo sudėtingumą ir atminties sąnaudas.
Svarbu skirti sąvokas sprendinys ir sprendinio vertė. Sprendinys yra pats eksponatų rinkinys. Panagrinėkime konkretų pavyzdį, siekiant iliustruoti dinaminio programavimo principus.
Kuprinės Uždavinys
Kuprinės uždavinys yra klasikinis optimizavimo pavyzdys. Tarkime, turime eksponatų, kurių kiekvienas sveria tam tikrą svorį ir turi atitinkamą vertę. Vagis turi kuprinę, sveriančią ne daugiau kaip kilogramų. Tikslas - sudėti į kuprinę eksponatus taip, kad jų bendra vertė būtų maksimali (t. y. vertės ir svorio santykis kuo didesnis).
Kuprinės uždavinio iliustracija
Galima būtų išbandyti visus įmanomus sprendinius ir iš jų išrinkti optimalų. Tačiau šis metodas netaikomas, nes yra labai neefektyvus, t. y. labai lėtas. Vietoj to, dinaminio programavimo pagrįsti algoritmai yra efektyvūs.
Optimalaus Sprendinio Struktūros Nustatymas
Pradėsime nuo optimalaus sprendinio struktūros nustatymo. Tarkime, turime eksponatų, kurių svoriai ir vertės išreikšti sveikaisiais skaičiais. Mūsų užduotis - rasti eksponatų rinkinį, kurio bendras svoris neviršytų ir kuris turėtų maksimalią vertę.
Algoritmas
Naudosime dinaminio programavimo algoritmą. Tarkime, kad turime lentelę D, kurioje saugosime tarpinius sprendinius. Lentelės elementas D[k, r] reikš maksimalią vertę, kurią galima pasiekti renkantis iš pirmųjų k eksponatų ir neviršijant svorio r.
Panagrinėkime konkretų pavyzdį. Tarkime, turime tris eksponatus, kurių svoriai yra 2, 3 ir 4 kilogramai, o vertės - 4, 5 ir 7. Kuprinės talpa yra 6 kilogramai. Sudarysime lentelę D ir užpildysime ją pagal šias taisykles:
- Jei svoris[k] <= r, tai D[k, r] = max(D[k - 1, r], D[k - 1, r - svoris[k]] + vertė[k]).
- Jei svoris[k] > r, tai D[k, r] = D[k - 1, r].
Šios reikšmės lentelėje pažymėtos pilku fonu. Algoritmas, įsimindamas tarpinius sprendinius, apskaičiuoja šią reikšmę.
Pavyzdžio atveju maksimali vertė lygi 33. Norėdami rasti, kuriuos eksponatus reikia įtraukti, galime peržiūrėti lentelę atgaline tvarka. Jei D[n, S] > D[n - 1, S], tai reikš, kad n-ąjį eksponatą įtraukti reikia.
| Eksponatas | Svoris | Vertė |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 3 | 5 |
| 3 | 4 | 7 |
Eksponatų duomenys
Ilgiausio Didėjančio Posekio Uždavinys
Kitas pavyzdys - ilgiausio didėjančio posekio uždavinys. Duota skaičių seka, pavyzdžiui, (10, 22, 9, 33, 21, 50, 41, 60, 80). Mūsų tikslas - rasti ilgiausią didėjantį posekį. Šiuo atveju, vienas iš ilgiausių didėjančių posekių yra (10, 22, 33, 50, 60, 80).
Optimalaus Sprendinio Struktūros Nustatymas
Pradėsime nuo optimalaus sprendinio struktūros nustatymo. Tarkime, kad žinome ilgiausią didėjantį posekį iki i-tojo nario. Kaip rasti ilgiausią didėjantį posekį iki i+1-ojo nario?
Tegu tai būtų ilgiausias didėjantis posekis iki i-tojo nario. Kad i+1-asis narys būtų įtrauktas į šį posekį, jis turi būti mažesnis už . Tai yra dinaminio programavimo metodo žingsnis. Šiuo atveju, mes pildome lentelę iš apačios į viršų.
Kiti Uždaviniai ir Dinaminis Programavimas
Dinaminis programavimas gali būti pritaikytas įvairiems uždaviniams spręsti. Pavyzdžiui, "Teisingų dalybų" uždaviniui spręsti, kai reikia padalinti dovanas dviem asmenims taip, kad jų vertės būtų kuo panašesnės. Arba "Lentynos paskirstymo" uždaviniui, kai reikia paskirstyti knygas keliems darbuotojams taip, kad kiekvienas gautų panašų kiekį knygų.
Dinaminis programavimas
Kada Verta Naudoti Dinaminį Programavimą?
Prieš pradedant taikyti dinaminį programavimą, svarbu įvertinti, ar tai tikrai tinkamas metodas. Ar uždavinyje aprašyto objekto elementai yra surikiuoti? Ar galime išspręsti uždavinį su elementų, jei žinome sprendimus tik su mažesniais parametrais? Ar tarpiniai uždaviniai kartotis? Jei ne - dinaminio programavimo taikyti neverta.
Taip pat dažnai reikia atsižvelgti į atminties sąnaudas. Jei sudėtingumas atminties atžvilgiu yra per didelis, dinaminio programavimo taikyti nepavyktų. Tačiau kartais galima sutaupyti atminties ir rasti efektyvesnį atminties atžvilgiu algoritmą.