DYNAAMINEN OHJELMOINTI: OMINAISUUDET, ESIMERKKI, EDUT, HAITAT - TEKNIIKKA - 2026

Dynaamista ohjelmointia on malli algoritmi, joka ratkaisee monimutkainen ongelma, jonka jakamalla se tulee osaongelmat, tulosten tallentamiseksi sen välttyä laskea tulokset.

Tätä aikataulua käytetään, kun sinulla on ongelmia, jotka voidaan jakaa samanlaisiin aliohjelmiin, jotta niiden tuloksia voidaan käyttää uudelleen. Tätä aikataulua käytetään pääosin optimointiin.

Dynaaminen ohjelmointi. Fibonacci-sekvenssin päällekkäisiä alioikeuksia. Lähde: Wikimedia commons, fi: Käyttäjä: Dcoatzee, käyttäjän jäljittämä: Stannered / Public domain

Ennen käytettävissä olevan alioikeuden ratkaisemista, dynaaminen algoritmi yrittää tutkia aiemmin ratkaistujen alioikeuksien tuloksia. Osaongelmien ratkaisut yhdistetään parhaan ratkaisun saavuttamiseksi.

Sen sijaan, että laskisi samaa aliohjelmaa yhä uudelleen, voit tallentaa ratkaisun johonkin muistiin, kun kohtaat tämän alioikeuden ensimmäisen kerran. Kun se ilmestyy jälleen toisen aliongelman ratkaisun aikana, muistiin jo tallennettu ratkaisu otetaan.

Tämä on hieno idea muistiajan asettamiseen, jossa lisätilan käyttäminen voi parantaa ratkaisun löytämiseen tarvittavaa aikaa.

Dynaamisen ohjelmoinnin ominaisuudet

Seuraavat olennaiset ominaisuudet ovat ne ongelmat, joita sinun täytyy olla, ennen kuin dynaamista ohjelmointia voidaan käyttää:

Optimaalinen rakenne

Tämä ominaisuus ilmaisee, että optimointitehtävä voidaan ratkaista yhdistämällä sitä muodostavien toissijaisten ongelmien optimaaliset ratkaisut. Nämä optimaaliset alirakenteet kuvataan rekursiolla.

Esimerkiksi kuvaajassa esitetään optimaalinen alarakenne lyhimmällä tiellä r, joka kulkee kärkipisteestä s kärkeen t:

Toisin sanoen tällä lyhimmällä reitillä r voidaan suorittaa mikä tahansa välipiste i. Jos r on todella lyhin reitti, niin se voidaan jakaa alireiteille r1 (s: stä i) ja r2: een (i: stä t) siten, että nämä ovat puolestaan ​​lyhin reitti vastaavien pisteiden välillä.

Siksi lyhimpien polkujen löytämiseksi ratkaisu voidaan formuloida helposti rekursiivisesti, mitä Floyd-Warshall-algoritmi tekee.

Päällekkäiset alioikeudet

Aliongelman tilan on oltava pieni. Toisin sanoen mikä tahansa toistuva algoritmi, joka ratkaisee ongelman, on ratkaistava samat alioikeudet uudestaan ​​ja uudestaan ​​uusien alioikeuksien luomisen sijasta.

Esimerkiksi Fibonacci-sarjan luomiseksi tätä rekursiivista formulaatiota voidaan pitää: Fn = F (n - 1) + F (n - 2) ottaen perustana tapaukseksi, että F1 = F2 = 1. Silloin meillä on: F33 = F32 + F31 ja F32 = F31 + F30.

Kuten näette, F31 on erotettavissa sekä F33: n että F32: n rekursiivisiksi alapuiksi. Vaikka alioikeuksien kokonaismäärä on todella pieni, jos valitset tällaisen rekursiivisen ratkaisun, päädyt ratkaisemaan samat ongelmat uudestaan ​​ja uudestaan.

Tämä otetaan huomioon dynaamisessa ohjelmoinnissa, joten se ratkaisee jokaisen alaongelman vain kerran. Tämä voidaan suorittaa kahdella tavalla:

Ylhäältä alas -lähestymistapa

Jos minkä tahansa ongelman ratkaisu voidaan formuloida rekursiivisesti käyttämällä sen alaongelmien ratkaisua, ja jos nämä alioikeudet ovat päällekkäisiä, niin alioikeuksien ratkaisut voidaan helposti muistaa tai tallentaa taulukkoon.

Joka kerta kun etsitään uutta alioikeusratkaisua, taulukko tarkistetaan, onko se aiemmin ratkaistu. Jos ratkaisu varastoidaan, sitä käytetään sen sijaan, että lasketaan uudelleen. Muutoin aliongelma ratkaistaan, ja tallennetaan ratkaisu taulukkoon.

Alhaalta ylöspäin suuntautuva lähestymistapa

Kun ongelman ratkaisu on muotoiltu rekursiivisesti sen alioikeuksien suhteen, on mahdollista yrittää muotoilla ongelma ylöspäin: ensin yritämme ratkaista alioikeudet ja käyttää niiden ratkaisuja päästäkseen ratkaisuihin suurempiin alioikeuksiin.

Tämä tehdään yleensä myös taulukkomuodossa generoimalla toistuvasti ratkaisuja suurempiin ja suurempiin alioikeuksiin käyttämällä ratkaisuja pienempiin alioikeuksiin. Esimerkiksi, jos F31: n ja F30: n arvot ovat jo tiedossa, F32: n arvo voidaan laskea suoraan.

Vertailu muihin tekniikoihin

Yksi merkittävä ongelman ominaisuus, joka voidaan ratkaista dynaamisella ohjelmoinnilla, on, että siinä tulisi olla aliprobleemeja päällekkäin. Tämä erottaa dynaamisen ohjelmoinnin jako- ja valloitustekniikasta, jossa ei tarvitse tallentaa yksinkertaisimpia arvoja.

Se on samanlainen kuin rekursiointi, koska perustasoja laskettaessa lopullinen arvo voidaan määrittää induktiivisesti. Tämä alhaalta ylöspäin suuntautuva lähestymistapa toimii hyvin, kun uusi arvo riippuu vain aiemmin laskettuista arvoista.

esimerkki

Vähimmäisvaiheet 1: n saavuttamiseksi

Mikä tahansa positiivinen kokonaisluku "e" voidaan suorittaa jokin seuraavista kolmesta vaiheesta.

- Vähennä 1 numerosta. (e = e-1).

- Jos se on jaollinen kahdella, se jaetaan kahdella (jos e% 2 == 0, niin e = e / 2).

- Jos se on jaollinen 3: lla, se jaetaan 3: lla (jos e% 3 == 0, niin e = e / 3).

Yllä olevien vaiheiden perusteella tulisi löytää näiden vaiheiden vähimmäismäärä tuomaan e arvoon 1. Esimerkiksi:

- Jos e = 1, tulos: 0.

- Jos e = 4, tulos: 2 (4/2 = 2/2 = 1).

- Kun e = 7, tulos: 3 (7-1 = 6/3 = 2/2 = 1).

fokus

Voidaan ajatella, että valitset aina vaiheen, joka tekee n: stä niin alhaisen kuin mahdollista, ja jatketaan tällä tavoin, kunnes se saavuttaa 1. Kuitenkin voidaan nähdä, että tämä strategia ei toimi täällä.

Esimerkiksi, jos e = 10, vaiheet olisivat: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 vaihetta). Optimaalinen muoto on kuitenkin: 10-1 = 9/3 = 3/3 = 1 (3 vaihetta). Siksi kaikki mahdolliset vaiheet, jotka voidaan suorittaa jokaiselle löydetylle n arvolle, tulisi kokeilla valitsemalla näiden mahdollisuuksien vähimmäismäärä.

Kaikki alkaa rekursiolla: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, jos e> 1, ottaen perustana oleva tapaus: F (1) = 0. Kun toistuvuus yhtälöllä, voit aloittaa rekursion koodaamisen.

Voidaan kuitenkin nähdä, että siinä on päällekkäisiä alioikeuksia. Lisäksi optimaalinen ratkaisu annetulle tulolle riippuu sen alioikeuksien optimaalisesta ratkaisusta.

Kuten muistiinpanossa, jossa ratkaisetut alioikeudet ratkaistaan ​​myöhempää käyttöä varten. Tai kuten dynaamisessa ohjelmoinnissa, aloitat alaosasta työskentelemällä tietäsi kohti annettua e. Sitten molemmat koodit:

ulkoa

Dynaaminen alhaalta ylös-ohjelmointi

Etu

Yksi dynaamisen ohjelmoinnin käytön tärkeimmistä eduista on, että se nopeuttaa käsittelyä, koska käytetään aiemmin laskettuja referenssejä. Koska se on rekursiivinen ohjelmointitekniikka, se vähentää koodirivit ohjelmassa.

Äärelliset algoritmit vs. dynaaminen ohjelmointi

Ahne algoritmit ovat samanlaisia ​​kuin dynaaminen ohjelmointi siinä mielessä, että ne molemmat ovat optimointityökaluja. Ahne algoritmi etsii kuitenkin optimaalisen ratkaisun jokaisessa paikallisessa vaiheessa. Toisin sanoen se etsii ahneta valintaa toiveessaan löytää globaali optimi.

Siksi ahne algoritmit voivat tehdä oletuksen, joka näyttää optimaaliselta silloin, mutta tulee tulevaisuudessa kalliiksi eikä takaa globaalia optimaalisuutta.

Toisaalta dynaaminen ohjelmointi löytää optimaalisen ratkaisun aliohjelmiin ja tekee sitten tietoisen valinnan yhdistämällä näiden alioikeuksien tulokset oikean ratkaisun löytämiseksi.

haitat

- Jokaisen alioikeuden lasketun tuloksen tallentamiseksi tarvitaan paljon muistia, ilman että pystymme takaamaan, että tallennettua arvoa käytetään vai ei.

- Usein lähtöarvo tallennetaan käyttämättä sitä seuraavissa aliohjelmissa suorituksen aikana. Tämä johtaa tarpeettomaan muistin käyttöön.

- Dynaamisessa ohjelmoinnissa toimintoja kutsutaan rekursiivisesti. Tämä pitää pinon muistin kasvamaan jatkuvasti.

Rekursio vs dynaaminen ohjelmointi

Jos muistisi on rajoitettua koodin suorittamiseen ja käsittelynopeus ei ole huolenaihe, voit käyttää rekursiota. Esimerkiksi, jos olet kehittämässä mobiilisovellusta, muisti on erittäin rajallinen sovelluksen ajamiseen.

Jos haluat ohjelman toimivan nopeammin ja sillä ei ole muistirajoituksia, on suositeltavaa käyttää dynaamista ohjelmointia.

Sovellukset

Dynaaminen ohjelmointi on tehokas tapa ratkaista ongelmia, jotka muuten saattavat tuntua erittäin vaikealta ratkaista kohtuullisessa ajassa.

Dynaamiseen ohjelmointiparadigmaan perustuvia algoritmeja käytetään monilla tieteen aloilla, mukaan lukien monia esimerkkejä tekoälystä, ongelmanratkaisusta suunnittelusta puhetunnistukseen.

Dynaamiseen ohjelmointiin perustuvat algoritmit

Dynaaminen ohjelmointi on varsin tehokasta ja toimii erittäin hyvin monenlaisissa ongelmissa. Monia algoritmeja voidaan pitää ahneina algoritmisovelluksina, kuten:

- Fibonacci-sarjasarja.

- Hanoin tornit.

- Kaikki parit lyhyempiä reittejä Floyd-Warshallin läpi.

- Reput.

- Projektien aikataulut.

- Lyhin tie läpi Dijkstra.

- Lennonohjaus ja robottihallinta.

- Matemaattiset optimointitehtävät.

- Aikaosa: ajoita työ maksimoidaksesi prosessorin käytön.

Fibonacci-sarjasarja

Fibonacci-numerot ovat numeroita, jotka löytyvät seuraavasta järjestyksestä: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 jne.

Matemaattisessa terminologiassa Fibonacci-lukujen sekvenssi Fn määritetään toistuvan kaavan avulla: F (n) = F (n -1) + F (n -2), jossa F (0) = 0 ja F (1) = 1.

Ylhäältä alas -lähestymistapa

Tässä esimerkissä hakukenttä kaikilla alkuarvoilla alustetaan -1: llä. Aina kun on tarpeen löytää ratkaisu alaongelmaan, etsitään ensin tätä matriisia.

Jos laskettu arvo on olemassa, arvo palautetaan. Muutoin tulos lasketaan tallennettavaksi hakukenttään, jotta sitä voidaan käyttää myöhemmin uudelleen.

Alhaalta ylöspäin suuntautuva lähestymistapa

Tässä tapauksessa samalle Fibonacci-sarjalle lasketaan ensin f (0), sitten f (1), f (2), f (3) ja niin edelleen. Siten alioikeuksien ratkaisuja rakennetaan alhaalta ylöspäin.

Viitteet

1. Vineet Choudhary (2020). Johdatus dynaamiseen ohjelmointiin. Kehittäjän sisäpiiri, otettu: developerinsider.co.
2. Alex Allain (2020). Dynaaminen ohjelmointi C ++: ssa. C-ohjelmointi. Otettu: cprogramming.com.
3. Akatemian jälkeen (2020). Idea dynaamisesta ohjelmoinnista. Otettu: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynaaminen ohjelmointi ja rekursio - ero, edut esimerkillä. CSE-pino. Kuvannut: csestack.org.
5. Code Chef (2020). Opastus dynaamiseen ohjelmointiin. Otettu: codechef.com.
6. Programiz (2020). Dynaaminen ohjelmointi. Otettu: programiz.com.