Šajā apmācībā jūs uzzināsiet, kas ir dinamiska programmēšana. Jūs atradīsit arī dinamiskās programmēšanas un alkatīgu algoritmu salīdzinājumu problēmu risināšanai.
Dinamiskā programmēšana ir datorprogrammēšanas paņēmiens, kas palīdz efektīvi atrisināt tādu problēmu klasi, kurām ir apakšproblēmu pārklāšanās un optimāla apakšstruktūras īpašība.
Šādas problēmas ietver atkārtotu to pašu apakšproblēmu vērtības aprēķināšanu, lai atrastu optimālāko risinājumu.
Dinamiskās programmēšanas piemērs
Veikt fibonacci secības ģenerēšanas gadījumu.
Ja secība ir F (1) F (2) F (3)… F (50), tā ievēro likumu F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Ievērojiet, kā pastāv apakšproblēmas, kas pārklājas, mums jāaprēķina F (48), lai aprēķinātu gan F (50), gan F (49). Tas ir tieši tāds algoritms, kurā spīd dinamiskā programmēšana.
Kā darbojas dinamiskā programmēšana
Dinamiskā programmēšana darbojas, saglabājot apakšproblēmu rezultātu, lai, kad nepieciešami to risinājumi, tie būtu pie rokas, un mums tie nav jāpārrēķina.
Šo apakšproblēmu vērtības saglabāšanas paņēmienu sauc par piezīmēšanu. Saglabājot masīva vērtības, mēs ietaupām laiku jau sastapto apakšproblēmu aprēķināšanai.
var m = karte (0 → 0, 1 → 1) funkcija fib (n), ja taustiņš n neatrodas kartē mm (n) = fib (n - 1) + fib (n - 2) atgriešanās m (n)
Dinamiskā programmēšana, izmantojot piezīmes, ir pieeja no augšas uz leju dinamiskai programmēšanai. Apgriežot virzienu, kādā darbojas algoritms, ti, sākot no bāzes gadījuma un virzoties uz risinājumu, mēs varam arī ieviest dinamisko programmēšanu no apakšas uz augšu.
funkcija fib (n) ja n = 0 atgriešanās 0 cits var prevFib = 0, currFib = 1 atkārtojums n - 1 reizes var newFib = prevFib + currFib prevFib = currFib currFib = newFib atgriešanās strāvaFib
Rekursija pret dinamisko programmēšanu
Dinamiskā programmēšana galvenokārt tiek piemērota rekursīviem algoritmiem. Tā nav nejaušība, lielākajai daļai optimizācijas problēmu ir nepieciešama rekursija, un optimizēšanai tiek izmantota dinamiskā programmēšana.
Bet ne visas problēmas, kurās tiek izmantota rekursija, var izmantot dinamisko programmēšanu. Ja vien nepastāv pārklājas apakšproblēmas, piemēram, fibonacci secības problēmā, rekursija risinājumu var sasniegt tikai, izmantojot sadalīšanas un iekarošanas pieeju.
Tas ir iemesls, kāpēc rekursīvs algoritms, piemēram, sapludināšanas kārtojums, nevar izmantot dinamisko programmēšanu, jo apakšproblēmas nekādā veidā nepārklājas.
Alkatīgi algoritmi pret dinamisko programmēšanu
Mantkārīgi algoritmi ir līdzīgi dinamiskai programmēšanai tādā ziņā, ka tie abi ir optimizācijas rīki.
Tomēr alkatīgi algoritmi meklē vietēji optimālus risinājumus vai, citiem vārdiem sakot, mantkārīgu izvēli, cerot atrast globālu optimālu. Tādējādi alkatīgi algoritmi var uzminēt, kas tajā laikā izskatās optimāli, bet kļūst dārgi zem līnijas un negarantē globālu optimumu.
Savukārt dinamiskā programmēšana atrod optimālu risinājumu apakšproblēmām un pēc tam veic apzinātu izvēli apvienot šo apakšproblēmu rezultātus, lai atrastu optimālāko risinājumu.
