DINAMINIS PROGRAMAVIMAS: CHARAKTERISTIKOS, PAVYZDYS, PRANAŠUMAI, TRŪKUMAI - TECHNOLOGIJA - 2025

Dinaminio programavimo yra modelis algoritmas, kuris išsprendžia sudėtinga problema iki dalijant jį į subproblems, rezultatus saugoti jų išvengti būtinybės perskaičiuoti rezultatus.

Šis tvarkaraštis naudojamas, kai kyla problemų, kurias galima suskirstyti į panašias antrines problemas, kad jų rezultatus būtų galima pakartotinai panaudoti. Dažniausiai šis grafikas naudojamas optimizavimui.

Dinaminis programavimas. Subproblemos, uždėtos Fibonačio seka. Šaltinis: „Wikimedia commons“, en: Vartotojas: „Dcoatzee“, sekamas vartotojo: Pažymėtas / viešas domenas

Prieš išspręsdamas turimą antrinę problemą, dinaminis algoritmas bandys ištirti anksčiau išspręstų antrinių problemų rezultatus. Subproblemų sprendimai yra derinami, kad būtų pasiektas geriausias sprendimas.

Užuot skaičiavę tą pačią antrinę problemą vėl ir vėl, pirmą kartą susidūrę su antrine problema galite išsaugoti savo sprendimą tam tikroje atmintyje. Kai jis vėl pasirodys sprendžiant kitą antrinę problemą, bus imtasi atmintyje jau išsaugoto sprendimo.

Tai nuostabi idėja, kaip pritvirtinti atminties laiką, kai papildomos vietos naudojimas gali sutrumpinti laiką, reikalingą sprendimo paieškai.

Dinaminio programavimo ypatybės

Kad galėtumėte pritaikyti dinaminį programavimą, turite susidurti su šiomis pagrindinėmis savybėmis:

Optimalus pagrindas

Ši savybė išreiškia, kad optimizavimo problemą galima išspręsti derinant optimalius ją sudarančių antrinių problemų sprendimus. Šios optimalios struktūros apibūdinamos rekursijos būdu.

Pvz., Grafike optimalus postruktūra bus pateiktas per trumpiausią kelią r, einantį iš viršūnės s į viršūnę t:

Tai yra, šiuo trumpiausiu keliu r gali būti paimta bet kuri tarpinė viršūnė i. Jei r yra trumpiausias maršrutas, tada jį galima suskirstyti į paprogrames r1 (nuo s į i) ir r2 (nuo i iki t) tokiu būdu, kad tai savo ruožtu yra trumpiausias maršrutas tarp atitinkamų viršūnių.

Todėl norint rasti trumpiausius kelius, sprendimą galima lengvai suformuluoti rekursyviai - tai daro Floydo-Varšalo algoritmas.

Iš dalies sutampančios antrinės problemos

Priemonės dalis turi būti maža. T. y., Bet kuris rekursinis algoritmas, išsprendžiantis problemą, turės vėl ir vėl spręsti tas pačias problemas, o ne generuoti naujas poproblemas.

Pavyzdžiui, norėdami sugeneruoti „Fibonacci“ seriją, galime apsvarstyti šią rekursinę formuluotę: Fn = F (n - 1) + F (n - 2), kaip pagrindinį atvejį laikydami, kad F1 = F2 = 1. Tada turėsime: F33 = F32 + F31 ir F32 = F31 + F30.

Kaip matote, F31 yra išskaidomas į retrospektyvius F33 ir F32 požemius. Nors bendras subproblemų skaičius yra tikrai mažas, jei priimsite tokį rekursyvų sprendimą, jūs vėl ir vėl spręsite tas pačias problemas.

Į tai atsižvelgiama atliekant dinaminį programavimą, todėl kiekviena papildoma problema išspręsta tik vieną kartą. Tai galima padaryti dviem būdais:

Metodas „iš viršaus į apačią“

Jei bet kurios problemos sprendimas gali būti rekursyviai suformuluotas, naudojant jos poproblemų sprendimą, ir jei šios poproblemos sutampa, tada poproblemų sprendimus galima lengvai įsiminti arba laikyti lentelėje.

Kiekvieną kartą ieškant naujojo antrinės problemos sprendimo, lentelė bus patikrinta, ar ji buvo išspręsta anksčiau. Jei tirpalas bus saugomas, jis bus naudojamas užuot skaičiavus dar kartą. Priešingu atveju bus išspręsta papildoma problema, sprendimas saugomas lentelėje.

„Iš apačios į viršų“ metodas

Po to, kai problemos sprendimas yra rekursyviai suformuluotas atsižvelgiant į jo poproblemas, galima pabandyti pertvarkyti problemą kylančia tvarka: pirmiausia bandysime išspręsti antrines problemas ir panaudosime jų sprendimus, norėdami rasti didesnių subproblemų sprendimus.

Paprastai tai daroma lentelės forma, pakartotinai generuojant didesnių ir didesnių antrinių problemų sprendimus, naudojant mažesnių antrinių problemų sprendimus. Pavyzdžiui, jei F31 ir F30 vertės jau žinomos, F32 vertę galima apskaičiuoti tiesiogiai.

Palyginimas su kitais būdais

Vienas reikšmingas problemos, kurią galima išspręsti naudojant dinaminį programavimą, bruožas yra tas, kad joje turėtų būti sutampančios antrinės problemos. Būtent tai išskiria dinaminį programavimą nuo dalijimo ir užkariavimo būdo, kai nereikia saugoti paprasčiausių verčių.

Tai panašu į rekursiją, nes skaičiuojant bazinius atvejus galutinę vertę galima nustatyti induktyviai. Šis metodas „iš apačios į viršų“ veikia gerai, kai nauja vertė priklauso tik nuo anksčiau apskaičiuotų verčių.

Pavyzdys

Minimalūs žingsniai norint pasiekti 1

Bet kuriam teigiamam skaičiui „e“ galima atlikti bet kurį iš šių trijų žingsnių.

- Atimkite iš skaičiaus 1. (e = e-1).

- Jei jis dalijamas iš 2, jis dalijamas iš 2 (jei e% 2 == 0, tada e = e / 2).

- Jei ji dalijama iš 3, ji dalijama iš 3 (jei e% 3 == 0, tada e = e / 3).

Remiantis aukščiau aprašytais žingsniais, turėtų būti rastas mažiausias šių žingsnių skaičius, kad e būtų lygi 1. Pavyzdžiui:

- Jei e = 1, rezultatas: 0.

- Jei e = 4, rezultatas: 2 (4/2 = 2/2 = 1).

- Kai e = 7, rezultatas: 3 (7-1 = 6/3 = 2/2 = 1).

Dėmesys

Galima galvoti apie tai, kad visada pasirenkate žingsnį, kuris n tampa kuo mažesnis, ir tęskite taip, kol pasieksite 1. Tačiau galima pastebėti, kad ši strategija čia neveikia.

Pvz., Jei e = 10, žingsniai būtų: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 žingsniai). Tačiau optimali forma yra: 10–1 = 9/3 = 3/3 = 1 (3 žingsniai). Todėl reikia išbandyti visus įmanomus veiksmus, kuriuos galima atlikti kiekvienai rastai n reikšmei, pasirenkant mažiausią šių galimybių skaičių.

Viskas prasideda nuo rekursijos: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, jei e> 1, imant pagrindinį atvejį: F (1) = 0. Turėdami pasikartojimo lygtį, galite pradėti koduoti rekursiją.

Tačiau galima pastebėti, kad joje yra iš dalies sutampančių problemų. Be to, optimalus tam tikros įvesties sprendimas priklauso nuo optimalaus jo antrinių problemų sprendimo.

Kaip ir įsimenant, kur išspręsti subproblemų sprendimai saugomi vėlesniam naudojimui. Arba kaip ir dinaminio programavimo atveju, jūs pradedate nuo apačios, dirbdami iki nurodytos e. Tada abu kodai:

Įsiminimas

Dinaminis programavimas „iš apačios į viršų“

Privalumas

Vienas pagrindinių dinaminio programavimo pranašumų yra tai, kad jis pagreitina apdorojimą, nes naudojamos nuorodos, kurios buvo anksčiau apskaičiuotos. Kadangi tai yra rekursinis programavimo būdas, tai sumažina kodo eilutes programoje.

Įvairūs algoritmai ir dinaminis programavimas

Gretūs algoritmai yra panašūs į dinaminį programavimą, nes jie abu yra optimizavimo įrankiai. Tačiau godus algoritmas kiekviename vietiniame žingsnyje ieško optimalaus sprendimo. T. y., Jis siekia godumo, tikėdamasis rasti visuotinį optimalumą.

Todėl godūs algoritmai gali padaryti prielaidą, kuri tuo metu atrodo optimali, tačiau ateityje tampa brangi ir negarantuoja visuotinio optimalumo.

Kita vertus, dinaminis programavimas suranda optimalų antrinių problemų sprendimą ir tada priima pagrįstą sprendimą derindamas tų antrinių problemų rezultatus, kad iš tikrųjų rastų optimaliausią sprendimą.

Trūkumai

- Norint išsaugoti apskaičiuotą kiekvienos antrinės problemos rezultatą, reikia daug atminties, negalint garantuoti, kad išsaugota reikšmė bus naudojama ar ne.

- Daugybė kartų išvesties reikšmė saugoma niekada nenaudojant jos vykdymo metu šiose subproblemose. Tai lemia nereikalingą atminties naudojimą.

- Dinaminio programavimo metu funkcijos vadinamos rekursyviai. Tai leidžia nuolat didinti krūvos atmintį.

Rekursija ir dinaminis programavimas

Jei turite nedaug atminties, kad galėtumėte paleisti savo kodą, ir apdorojimo greitis nekelia rūpesčių, galite naudoti rekursiją. Pvz., Jei kuriate mobiliąją programą, programos paleidimas yra labai ribotas.

Jei norite, kad programa veiktų greičiau ir neturėtumėte jokių atminties apribojimų, geriau naudoti dinaminį programavimą.

Programos

Dinaminis programavimas yra veiksmingas problemų sprendimo būdas, kuris priešingu atveju gali atrodyti nepaprastai sunkus per pagrįstą laiką.

Algoritmai, pagrįsti dinaminio programavimo paradigma, yra naudojami daugelyje mokslo sričių, įskaitant daugybę dirbtinio intelekto pavyzdžių, pradedant nuo problemų sprendimo planavimo ir baigiant kalbos atpažinimu.

Algoritmai, pagrįsti dinaminiu programavimu

Dinaminis programavimas yra gana efektyvus ir labai gerai veikia daugelį problemų. Daugelis algoritmų gali būti vertinami kaip godus algoritmų taikymas, pavyzdžiui:

- „Fibonačio“ serijos.

- Hanojaus bokštai.

- Visos poros trumpesnių maršrutų per Floyd-Warshall.

- Kuprinės problema.

- Projektų planavimas.

- Trumpiausias kelias per Dijkstrą.

- Skrydžio ir robotikos valdymas.

- Matematinio optimizavimo problemos.

- Pakaitinis naudojimasis turtu: suplanuokite darbą, kad maksimaliai išnaudotumėte procesorių.

„Fibonači“ skaičių serija

Fibonačio skaičiai yra skaičiai, rasti tokia seka: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ir kt.

Matematinėje terminijoje Fibonacci skaičių seka Fn apibrėžiama pasikartojimo formule: F (n) = F (n -1) + F (n -2), kur F (0) = 0 ir F ( 1) = 1.

Metodas „iš viršaus į apačią“

Šiame pavyzdyje paieškos masyvas su visomis pradinėmis reikšmėmis yra inicijuojamas -1. Kai reikia papildomos problemos sprendimo, pirmiausia bus ieškoma šios paieškos matricos.

Jei apskaičiuota vertė yra, tada ji bus grąžinta. Priešingu atveju rezultatas bus apskaičiuojamas kaip saugomas paieškos masyve, kad vėliau jį būtų galima vėl panaudoti.

„Iš apačios į viršų“ metodas

Tokiu atveju tai pačiai Fibonacci serijai pirmiausia apskaičiuojamas f (0), tada f (1), f (2), f (3) ir pan. Taigi subproblemų sprendimai yra kuriami iš apačios į viršų.

Nuorodos

1. Vineet Choudhary (2020). Įvadas į dinaminį programavimą. „Developer Insider“, paimta iš: developerinsider.co.
2. Aleksas Allainas (2020 m.). Dinaminis programavimas C ++. C programavimas. Paimta iš: cprogramming.com.
3. Po akademijos (2020). Dinaminio programavimo idėja. Paimta iš: afteracademy.com.
4. Aniruddha Chaudhari (2019 m.). Dinaminis programavimas ir rekursija - skirtumas, pranašumai su pavyzdžiu. TPP krūva. Paimta iš: csestack.org.
5. „Code Chef“ (2020). Vadovas dinaminiam programavimui. Paimta iš: codechef.com.
6. Programiz (2020). Dinaminis programavimas. Paimta iš: programiz.com.