Dynaaminen ohjelmointi on tekniikka, joka jakaa ongelmat osaongelmiin ja tallentaa tuloksen tulevaa käyttöä varten, jotta meidän ei tarvitse laskea tulosta uudelleen. Aliongelmat optimoidaan kokonaisratkaisun optimoimiseksi tunnetaan optimaalisena alirakenteen ominaisuutena. Dynaamisen ohjelmoinnin pääasiallinen käyttötarkoitus on optimointiongelmien ratkaiseminen. Tässä optimointiongelmat tarkoittavat sitä, että yritämme löytää ongelman minimi- tai maksimiratkaisun. Dynaaminen ohjelmointi takaa optimaalisen ratkaisun löytämisen ongelmaan, jos ratkaisu on olemassa.
Dynaamisen ohjelmoinnin määritelmä sanoo, että se on tekniikka monimutkaisen ongelman ratkaisemiseksi murtautumalla ensin kokoelmaan yksinkertaisempia osaongelmia, ratkaisemalla jokainen osaongelma vain kerran ja sitten tallentamalla niiden ratkaisut toistuvien laskelmien välttämiseksi.
Ymmärretään tämä lähestymistapa esimerkin kautta.
Harkitse esimerkkiä Fibonacci-sarjasta. Seuraava sarja on Fibonacci-sarja:
java laskuri
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
Yllä olevan sarjan lukuja ei ole laskettu satunnaisesti. Matemaattisesti voisimme kirjoittaa jokaisen termin käyttämällä alla olevaa kaavaa:
F(n) = F(n-1) + F(n-2),
Perusarvoilla F(0) = 0 ja F(1) = 1. Muiden lukujen laskemiseksi noudatamme yllä olevaa suhdetta. Esimerkiksi F(2) on summa f(0) ja f(1), joka on yhtä suuri kuin 1.
Kuinka voimme laskea F(20)?
F(20)-termi lasketaan Fibonacci-sarjan n:nnen kaavan avulla. Alla oleva kuva näyttää, kuinka F(20) lasketaan.
ymail
Kuten yllä olevasta kuvasta voidaan havaita, F(20) lasketaan F(19) ja F(18) summana. Dynaamisessa ohjelmoinnin lähestymistavassa yritämme jakaa ongelman vastaaviin osaongelmiin. Noudatamme tätä lähestymistapaa yllä olevassa tapauksessa, jossa F(20) liittyy samanlaisiin osaongelmiin, eli F(19) ja F(18). Jos toistamme dynaamisen ohjelmoinnin määritelmän, se sanoo, että samanlaista aliongelmaa ei pitäisi laskea useammin kuin kerran. Silti yllä olevassa tapauksessa osaongelma lasketaan kahdesti. Yllä olevassa esimerkissä F(18) lasketaan kahdesti; samoin F(17) lasketaan kahdesti. Tämä tekniikka on kuitenkin varsin hyödyllinen, koska se ratkaisee samanlaiset aliongelmat, mutta meidän on oltava varovaisia tallentaessamme tuloksia, koska emme ole erityisiä tallentaessamme kerran laskettua tulosta, jolloin se voi johtaa resurssien tuhlaukseen.
Yllä olevassa esimerkissä, jos laskemme oikean alipuun F(18), se johtaa valtavaan resurssien käyttöön ja heikentää yleistä suorituskykyä.
Ratkaisu yllä olevaan ongelmaan on tallentaa lasketut tulokset taulukkoon. Ensin lasketaan F(16) ja F(17) ja tallennetaan niiden arvot taulukkoon. F(18) lasketaan summaamalla F(17) ja F(16) arvot, jotka on jo tallennettu taulukkoon. F(18):n laskettu arvo tallennetaan taulukkoon. F(19):n arvo lasketaan F(18):n ja F(17):n summalla, ja niiden arvot on jo tallennettu taulukkoon. F(19):n laskettu arvo tallennetaan taulukkoon. F(20):n arvo voidaan laskea laskemalla yhteen F(19):n ja F(18):n arvot, ja sekä F(19):n että F(18):n arvot tallennetaan taulukkoon. F(20):n lopullinen laskettu arvo tallennetaan taulukkoon.
Miten dynaaminen ohjelmointitapa toimii?
Seuraavat ovat vaiheet, joita dynaaminen ohjelmointi seuraa:
- Se jakaa monimutkaisen ongelman yksinkertaisempiin osaongelmiin.
- Se löytää optimaalisen ratkaisun näihin osaongelmiin.
- Se tallentaa aliongelmien tulokset (muistiinpanon). Aliongelmien tulosten tallennusprosessi tunnetaan nimellä muistaminen.
- Se käyttää niitä uudelleen niin, että sama osaongelma lasketaan useammin kuin kerran.
- Lopuksi laske monimutkaisen ongelman tulos.
Yllä olevat viisi vaihetta ovat dynaamisen ohjelmoinnin perusvaiheita. Dynaamista ohjelmointia voidaan soveltaa, jolla on ominaisuuksia, kuten:
linux isäntä
Ne ongelmat, joissa on päällekkäisiä aliongelmia ja optimaalisia alirakenteita. Tässä optimaalinen alirakenne tarkoittaa, että optimointiongelmien ratkaisu voidaan saada yksinkertaisesti yhdistämällä kaikkien osaongelmien optimaalinen ratkaisu.
Dynaamisen ohjelmoinnin tapauksessa tilan monimutkaisuus kasvaisi välituloksia tallentaessa, mutta aikamonimutkaisuus pienenisi.
Dynaamisen ohjelmoinnin lähestymistavat
Dynaamiseen ohjelmointiin on kaksi lähestymistapaa:
- Ylhäältä alas -lähestymistapa
- Alhaalta ylös -lähestymistapa
Ylhäältä alas -lähestymistapa
Ylhäältä alas -lähestymistapa noudattaa muistitekniikkaa, kun taas alhaalta ylös -lähestymistapa seuraa taulukkomenetelmää. Tässä muistaminen on yhtä suuri kuin rekursion ja välimuistin summa. Rekursio tarkoittaa itse funktion kutsumista, kun taas välimuisti tarkoittaa välitulosten tallentamista.
muuntaa merkkijono json-objektiksi
Edut
- Se on erittäin helppo ymmärtää ja toteuttaa.
- Se ratkaisee osaongelmat vain tarvittaessa.
- Se on helppo korjata.
Haitat
Se käyttää rekursiotekniikkaa, joka vie enemmän muistia puhelupinossa. Joskus kun rekursio on liian syvä, esiintyy pinon ylivuototila.
Se vie enemmän muistia, mikä heikentää yleistä suorituskykyä.
Ymmärretään dynaaminen ohjelmointi esimerkin kautta.
int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of 'n' increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td> </tr><tr><td>Bottom-Up</td> </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let's understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let's understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>