Dynamisk programmering er en teknik, der deler problemerne op i delproblemer, og gemmer resultatet til fremtidige formål, så vi ikke behøver at beregne resultatet igen. Delproblemerne er optimeret for at optimere den samlede løsning er kendt som optimal underbygningsegenskab. Hovedanvendelsen af dynamisk programmering er at løse optimeringsproblemer. Her betyder optimeringsproblemer, at når vi forsøger at finde ud af minimums- eller maksimumsløsningen af et problem. Den dynamiske programmering garanterer at finde den optimale løsning af et problem, hvis løsningen findes.
Definitionen af dynamisk programmering siger, at det er en teknik til at løse et komplekst problem ved først at bryde ind i en samling af enklere delproblemer, løse hvert delproblem kun én gang og derefter gemme deres løsninger for at undgå gentagne beregninger.
Lad os forstå denne tilgang gennem et eksempel.
Overvej et eksempel på Fibonacci-serien. Følgende serie er Fibonacci-serien:
powershell admin
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,...
Tallene i ovenstående serie er ikke tilfældigt beregnet. Matematisk kunne vi skrive hvert af termerne ved at bruge nedenstående formel:
F(n) = F(n-1) + F(n-2),
Med grundværdierne F(0) = 0, og F(1) = 1. For at beregne de øvrige tal følger vi ovenstående forhold. For eksempel er F(2) summen f(0) og f(1), som er lig med 1.
Hvordan kan vi beregne F(20)?
F(20)-leddet vil blive beregnet ved hjælp af den n'te formel i Fibonacci-serien. Nedenstående figur viser, hvordan F(20) beregnes.
if else sætning i java
Som vi kan observere i ovenstående figur, er F(20) beregnet som summen af F(19) og F(18). I den dynamiske programmeringstilgang forsøger vi at dele problemet op i de lignende delproblemer. Vi følger denne tilgang i ovenstående tilfælde, hvor F(20) ind i de lignende underproblemer, dvs. F(19) og F(18). Hvis vi opsummerer definitionen af dynamisk programmering, siger den, at det lignende underproblem ikke bør beregnes mere end én gang. Alligevel beregnes underproblemet i ovenstående tilfælde to gange. I ovenstående eksempel beregnes F(18) to gange; tilsvarende beregnes F(17) også to gange. Denne teknik er dog ret nyttig, da den løser de lignende underproblemer, men vi skal være forsigtige, mens vi gemmer resultaterne, fordi vi ikke er særlige med at gemme resultatet, som vi har beregnet én gang, så kan det føre til spild af ressourcer.
I ovenstående eksempel, hvis vi beregner F(18) i det højre undertræ, fører det til den enorme brug af ressourcer og reducerer den samlede ydeevne.
Løsningen på ovenstående problem er at gemme de beregnede resultater i et array. Først beregner vi F(16) og F(17) og gemmer deres værdier i et array. F(18) beregnes ved at summere værdierne af F(17) og F(16), som allerede er gemt i et array. Den beregnede værdi af F(18) gemmes i et array. Værdien af F(19) beregnes ved hjælp af summen af F(18) og F(17), og deres værdier er allerede gemt i et array. Den beregnede værdi af F(19) lagres i et array. Værdien af F(20) kan beregnes ved at tilføje værdierne af F(19) og F(18), og værdierne af både F(19) og F(18) gemmes i et array. Den endelige beregnede værdi af F(20) lagres i et array.
Hvordan fungerer den dynamiske programmeringstilgang?
Følgende er de trin, som den dynamiske programmering følger:
- Det nedbryder det komplekse problem i enklere delproblemer.
- Den finder den optimale løsning på disse delproblemer.
- Den gemmer resultaterne af underproblemer (memoisering). Processen med at gemme resultaterne af underproblemer er kendt som memorering.
- Det genbruger dem, så det samme delproblem beregnes mere end én gang.
- Beregn endelig resultatet af det komplekse problem.
Ovenstående fem trin er de grundlæggende trin for dynamisk programmering. Den dynamiske programmering er anvendelig, der har egenskaber som:
java retur array
De problemer, der har overlappende underproblemer og optimale understrukturer. Her betyder optimal understruktur, at løsningen af optimeringsproblemer kan opnås ved blot at kombinere den optimale løsning af alle underproblemerne.
I tilfælde af dynamisk programmering ville rumkompleksiteten blive øget, når vi gemmer de mellemliggende resultater, men tidskompleksiteten ville blive reduceret.
Tilgange til dynamisk programmering
Der er to tilgange til dynamisk programmering:
- Top-down tilgang
- Bottom-up tilgang
Top-down tilgang
Top-down-tilgangen følger husketeknikken, mens bottom-up-tilgangen følger tabuleringsmetoden. Her er memorering lig med summen af rekursion og caching. Rekursion betyder at kalde selve funktionen, mens caching betyder lagring af mellemresultaterne.
Fordele
- Det er meget nemt at forstå og implementere.
- Det løser kun underproblemerne, når det er påkrævet.
- Det er nemt at fejlfinde.
Ulemper
java boolesk streng
Den bruger rekursionsteknikken, der optager mere hukommelse i opkaldsstakken. Nogle gange, når rekursionen er for dyb, vil stackoverløbstilstanden forekomme.
Det optager mere hukommelse, hvilket forringer den samlede ydeevne.
Lad os forstå dynamisk programmering gennem et eksempel.
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)>