DINAMISKĀ PROGRAMMĒŠANA: RAKSTURLIELUMI, PIEMĒRS, PRIEKŠROCĪBAS, TRŪKUMI - TEHNOLOĢIJAS - 2025

Dinamiskā programmēšana ir modelis, algoritms, kas atrisina sarežģītas problēmas , ko sadalot to uz subproblems, uzglabājot tās rezultātiem, lai izvairītos no nepieciešamības pārrēķināt rezultātus.

Šis grafiks tiek izmantots, ja rodas problēmas, kuras var iedalīt līdzīgās apakšproblēmās, lai to rezultātus varētu izmantot atkārtoti. Šis grafiks lielākoties tiek izmantots optimizēšanai.

Dinamiskā programmēšana. Apakšproblemas, kas uzliktas Fibonači secībā. Avots: Wikimedia commons, lv: Lietotājs: Dcoatzee, izseko Lietotājs: Atzīmēts / Publiskais īpašums

Pirms pieejamās apakšproblēmas risināšanas dinamiskais algoritms mēģinās izpētīt iepriekš atrisināto apakšproblēmu rezultātus. Apakšproblēmu risinājumi tiek apvienoti, lai sasniegtu labāko risinājumu.

Tā vietā, lai atkal un atkal aprēķinātu vienu un to pašu apakšproblēmu, varat saglabāt savu risinājumu atmiņā, pirmo reizi saskaroties ar šo apakšproblēmu. Kad tas atkal parādās citas apakšproblēmas risināšanas laikā, tiks ņemts atmiņā jau saglabātais risinājums.

Šī ir lieliska ideja atmiņas laika fiksēšanai, kur papildu vietas izmantošana var uzlabot risinājuma atrašanai nepieciešamo laiku.

Dinamiskās programmēšanas iezīmes

Lai varētu izmantot dinamisko programmēšanu, jums ir jāatrisina šādas galvenās pazīmes:

Optimāla pamatkonstrukcija

Šis raksturlielums izsaka to, ka optimizācijas problēmu var atrisināt, apvienojot to veidojošo sekundāro problēmu optimālos risinājumus. Šīs optimālās apakšstruktūras raksturo ar rekursiju.

Piemēram, grafikā optimālā apakšstruktūra tiks parādīta īsākajā ceļā r, kas iet no virsotnes s uz virsotni t:

Tas ir, šajā īsākajā ceļā r var veikt jebkuru starpposma virsotni i. Ja r patiešām ir īsākais ceļš, tad to var sadalīt apakš maršrutos r1 (no s līdz i) un r2 (no i līdz t), tā, lai tie savukārt būtu īsākie maršruti starp attiecīgajām virsotnēm.

Tāpēc, lai atrastu īsākos ceļus, risinājumu var viegli formulēt rekursīvi, tieši to dara arī Floyd-Warshall algoritms.

Apakšproblēmu pārklāšanās

Apakšproblēmas atstarpei jābūt mazai. Tas ir, jebkuram rekursīvam algoritmam, kas atrisina problēmu, atkal un atkal būs jāatrisina tās pašas apakšproblemas, nevis jāģenerē jaunas apakšproblemas.

Piemēram, lai izveidotu Fibonači sēriju, mēs varam apsvērt šo rekursīvo formulējumu: Fn = F (n - 1) + F (n - 2), par bāzi ņemot, ka F1 = F2 = 1. Tad mums būs: F33 = F32 + F31 un F32 = F31 + F30.

Kā redzat, F31 tiek sadalīts gan F33, gan F32 rekursīvajos apakšgrupās. Lai gan kopējais apakšproblēmu skaits ir patiešām mazs, ja jūs pieņemat rekursīvu risinājumu, piemēram, šo, jūs atkal un atkal risināsit tās pašas problēmas.

Tas tiek ņemts vērā dinamiskajā programmēšanā, tāpēc tā katru apakšproblēmu risina tikai vienreiz. To var paveikt divos veidos:

Augšupēja pieeja

Ja kādas problēmas risinājumu var rekursīvi formulēt, izmantojot tās apakšproblēmu risinājumu, un ja šīs apakšproblēmas pārklājas, tad apakšproblēmu risinājumus var viegli iegaumēt vai saglabāt tabulā.

Katru reizi, kad tiek meklēts jauns apakšproblēmas risinājums, tabula tiks pārbaudīta, lai redzētu, vai tā iepriekš nav atrisināta. Gadījumā, ja risinājums tiek glabāts, tas tiks izmantots tā vietā, lai to atkal aprēķinātu. Pretējā gadījumā tiks atrisināta apakšproblēma, šķīdumu saglabājot tabulā.

Augšupvērsta pieeja

Pēc tam, kad problēmas risinājums ir formulēts rekursīvi attiecībā uz tā apakšproblēmām, ir iespējams mēģināt pārformulēt problēmu augšupvērstā veidā: vispirms mēs centīsimies atrisināt apakšproblemas un izmantot to risinājumus, lai rastu risinājumus lielākām apakšproblēmām.

Parasti tas tiek darīts arī tabulas veidā, iteratīvi ģenerējot risinājumus lielākām un lielākām apakšproblēmām, izmantojot risinājumus mazākām apakšproblēmām. Piemēram, ja F31 un F30 vērtības jau ir zināmas, F32 vērtību var tieši aprēķināt.

Salīdzinājums ar citām metodēm

Viena no būtiskām problēmas iezīmēm, ko var atrisināt ar dinamiskās programmēšanas palīdzību, ir tāda, ka tai ir jābūt apakšproblēmām, kas pārklājas. Tas atšķir dinamisko programmēšanu no dalīšanas un iekarošanas tehnikas, kur nav nepieciešams uzglabāt vienkāršākās vērtības.

Tas ir līdzīgs atkārtojumam, jo, aprēķinot bāzes gadījumus, galīgo vērtību var noteikt induktīvi. Šī augšupējā pieeja darbojas labi, ja jauna vērtība ir atkarīga tikai no iepriekš aprēķinātām vērtībām.

Piemērs

Minimālie soļi, lai sasniegtu 1

Jebkuram pozitīvam skaitlim "e" var veikt jebkuru no šīm trim darbībām.

- Atņemiet skaitli 1. (e = e-1).

- Ja tas ir dalāms ar 2, tas tiek dalīts ar 2 (ja e% 2 == 0, tad e = e / 2).

- Ja tas ir dalāms ar 3, tas tiek dalīts ar 3 (ja e% 3 == 0, tad e = e / 3).

Balstoties uz iepriekšminētajām darbībām, jāatrod minimālais šo darbību skaits, lai sasniegtu e līdz 1. Piemēram:

- Ja e = 1, rezultāts: 0.

- Ja e = 4, rezultāts: 2 (4/2 = 2/2 = 1).

- Kad e = 7, rezultāts: 3 (7-1 = 6/3 = 2/2 = 1).

Fokuss

Varētu domāt vienmēr izvēlēties soli, kas padara n pēc iespējas zemāku, un turpināt šādi, līdz tas sasniedz 1. Tomēr var redzēt, ka šī stratēģija šeit nedarbojas.

Piemēram, ja e = 10, soļi būtu šādi: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 soļi). Tomēr optimālā forma ir: 10-1 = 9/3 = 3/3 = 1 (3 soļi). Tāpēc ir jāizmēģina visas iespējamās darbības, kuras var veikt katrai atrastajai n vērtībai, izvēloties šo iespēju minimālo skaitu.

Viss sākas ar atkārtošanos: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, ja e> 1, ņemot par pamata gadījumu: F (1) = 0. Ja rodas atkārtojuma vienādojums, jūs varat sākt rekursijas kodēšanu.

Tomēr redzams, ka tai ir apakšproblēmu pārklāšanās. Turklāt optimālais risinājums konkrētajam ievadim ir atkarīgs no tā apakšproblēmu optimālā risinājuma.

Tāpat kā iegaumēšanā, kur atrisinātie apakšproblēmu risinājumi tiek glabāti vēlākai izmantošanai. Vai tāpat kā dinamiskajā programmēšanā, jūs sākat no apakšas, strādājot līdz dotajam e. Tad abi kodi:

Iegaumēšana

Dinamiska augšupēja programmēšana

Priekšrocība

Viena no galvenajām dinamiskās programmēšanas izmantošanas priekšrocībām ir tā, ka tā paātrina apstrādi, jo tiek izmantotas iepriekš aprēķinātās atsauces. Tā kā tas ir rekursīvs programmēšanas paņēmiens, tas samazina koda rindiņas programmā.

Neveiksmīgi algoritmi salīdzinājumā ar dinamisko programmēšanu

Mantkārīgi algoritmi ir līdzīgi dinamiskajai programmēšanai, jo tie abi ir optimizācijas rīki. Tomēr mantkārīgais algoritms katrā vietējā solī meklē optimālu risinājumu. Tas ir, tas meklē mantkārīgu izvēli cerībā atrast globālu optimālu.

Tāpēc mantkārīgi algoritmi var izdarīt pieņēmumu, kas tajā laikā izskatās optimāls, bet nākotnē kļūst dārgs un negarantē globālu optimālu.

No otras puses, dinamiskā programmēšana atrod optimālo risinājumu apakšproblēmām un pēc tam izdara apzinātu izvēli, apvienojot šo apakšproblēmu rezultātus, lai faktiski atrastu optimālāko risinājumu.

Trūkumi

- Lai saglabātu katras apakšproblēmas aprēķināto rezultātu, ir nepieciešams daudz atmiņas, nespējot garantēt, ka saglabātā vērtība tiks izmantota.

- Daudzas reizes izvades vērtība tiek saglabāta, nekad neizmantojot to izpildes laikā. Tas noved pie nevajadzīgas atmiņas izmantošanas.

- Dinamiskajā programmēšanā funkcijas tiek sauktas rekursīvi. Tas nepārtraukti palielina kaudzes atmiņu.

Rekursija vs dinamiskā programmēšana

Ja jums ir ierobežota atmiņa koda palaišanai, un apstrādes ātrums neuztrauc, varat izmantot rekursiju. Piemēram, ja jūs izstrādājat mobilo programmu, programmas palaišanai ir ļoti ierobežota atmiņa.

Ja vēlaties, lai programma darbotos ātrāk un tai nebūtu atmiņas ierobežojumu, ieteicams izmantot dinamisko programmēšanu.

Lietojumprogrammas

Dinamiskā programmēšana ir efektīva tādu problēmu risināšanas metode, kuras savādākā laika posmā varētu šķist ārkārtīgi sarežģītas.

Algoritmi, kuru pamatā ir dinamiskās programmēšanas paradigma, tiek izmantoti daudzās zinātnes jomās, ieskaitot daudzus mākslīgā intelekta piemērus, sākot no problēmu risināšanas plānošanas līdz runas atpazīšanai.

Algoritmi, kuru pamatā ir dinamiska programmēšana

Dinamiskā programmēšana ir diezgan efektīva un ļoti labi piemērota plaša spektra problēmu risināšanai. Daudzus algoritmus var uzskatīt par mantkārīgiem algoritmu lietojumiem, piemēram:

- Fibonači numuru sērija.

- Hanojas torņi.

- Visi īsāku maršrutu pāri pa Floyd-Warshall.

- mugursomas problēma.

- Projekta plānošana.

- Īsākais ceļš caur Dijkstru.

- lidojuma un robotikas vadība.

- Matemātiskās optimizācijas problēmas.

- Daļlaika lietojums īpašumā: ieplānojiet darbu, lai maksimāli izmantotu CPU.

Fibonači numuru sērija

Fibonači skaitļi ir skaitļi, kas atrodami šādā secībā: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 utt.

Matemātiskajā terminoloģijā Fibonači skaitļu secību Fn nosaka pēc atkārtošanās formulas: F (n) = F (n -1) + F (n -2), kur F (0) = 0 un F ( 1) = 1.

Augšupēja pieeja

Šajā piemērā meklēšanas masīvs ar visām sākotnējām vērtībām tiek inicializēts ar -1. Ikreiz, kad ir nepieciešams apakšproblēmas risinājums, vispirms tiks meklēta šī meklēšanas matrica.

Ja aprēķinātā vērtība ir tur, tā tiks atgriezta. Pretējā gadījumā rezultāts tiks aprēķināts, lai to saglabātu meklēšanas masīvā, lai vēlāk to varētu atkārtoti izmantot.

Augšupvērsta pieeja

Šajā gadījumā tai pašai Fibonači sērijai vispirms tiek aprēķināta f (0), pēc tam f (1), f (2), f (3) utt. Tādējādi apakšproblēmu risinājumi tiek veidoti no apakšas uz augšu.

Atsauces

1. Vineet Choudhary (2020). Ievads dinamiskajā programmēšanā. Izstrādātāja iekšējā informācija, ņemts no: developerinsider.co.
2. Alekss Allains (2020). Dinamiska programmēšana C ++. C programmēšana. Paņemts no: cprogramming.com.
3. Pēc akadēmijas (2020). Dinamiskās programmēšanas ideja. Iegūts no: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dinamiska programmēšana un rekursija - atšķirība, priekšrocības ar piemēru. CSE steks. Paņemts no: csestack.org.
5. Koda šefpavārs (2020). Pamācība dinamiskai programmēšanai. Paņemts no: codechef.com.
6. Programiz (2020). Dinamiskā programmēšana. Paņemts no: programiz.com.