En introduktion til algoritmer: dynamisk programmering

Antag at du laver nogle beregninger ved hjælp af en passende række input. Der er nogle beregninger udført i hvert tilfælde for at få noget resultat. Du ved ikke, at du havde stødt på den samme output, da du havde leveret den samme input . Så det er som om du foretager genberegning af et resultat, der tidligere blev opnået med specifik input til dets respektive output.

Men hvad er problemet her? Ting er, at din dyrebare tid er spildt. Du kan nemt løse problemet her ved at føre poster, der kortlægger tidligere beregnede resultater. Såsom at bruge den relevante datastruktur. For eksempel kan du gemme input som nøgle og output som en værdi (del af kortlægning).

De, der ikke kan huske fortiden, dømmes til at gentage det. ~ Dynamisk programmering

Nu ved at analysere problemet skal du gemme dets input, hvis det er nyt (eller ikke i datastrukturen) med dets respektive output. Kontroller ellers denne inputnøgle, og få den resulterende output fra dens værdi. På den måde, når du foretager nogle beregninger og kontrollerer, om dette input eksisterede i datastrukturen, kan du direkte få resultatet. Således kan vi relatere denne tilgang til dynamiske programmeringsteknikker.

Dykker ned i dynamisk programmering

I en nøddeskal kan vi sige, at dynamisk programmering primært bruges til optimering af problemer, hvor vi ønsker at finde den “bedste” måde at gøre noget på.

Et bestemt scenario er som om der er gentagne delproblemer, som igen har deres egne mindre delproblemer. I stedet for at forsøge at løse disse genoptrædende underproblemer foreslår dynamisk programmering igen og igen, at man kun løser hvert af de mindre delproblemer en gang. Derefter registrerer du resultaterne i en tabel, hvorfra en løsning på det oprindelige problem kan opnås.

For eksempel har Fibonacci-numrene 0,1,1,2,3,5,8,13,…en simpel beskrivelse, hvor hvert udtryk er relateret til de to termer før det. Hvis det F(n)er den ntredje periode i denne serie, har vi det F(n) = F(n-1) + F(n-2). Dette kaldes en rekursiv formel eller et gentagelsesforhold. Det skal tidligere beregninger være beregnet for at beregne en senere periode.

De fleste problemer med dynamisk programmering kan kategoriseres i to typer:

  1. Optimeringsproblemer.
  2. Kombinatoriske problemer.

Optimeringsproblemerne forventer, at du vælger en mulig løsning, så værdien af ​​den nødvendige funktion minimeres eller maksimeres. Kombinatoriske problemer forventer, at du finder ud af antallet af måder at gøre noget på eller sandsynligheden for, at en begivenhed sker.

En tilgang til løsning: top-down vs bottom-up

Der er følgende to forskellige måder at løse problemet på:

Top-down: Du starter fra toppen og løser problemet ved at nedbryde det. Hvis du ser, at problemet allerede er løst, skal du bare returnere det gemte svar. Dette kaldes Memoization.

Bottom-up: Du begynder direkte at løse de mindre delproblemer, der tager dig til toppen for at udlede den endelige løsning på det ene store problem. I denne proces er det garanteret, at delproblemerne løses, før problemet løses. Dette kan kaldes Tabulation ( tabelfyldningsalgoritme ).

I reference til iteration vs rekursion bruger bottom-up iteration og top-down bruger rekursion.

Her er der en sammenligning mellem en naiv tilgang og en DP-tilgang. Du kan se forskellen ved begge tiders kompleksitet.

Memoization: Glem ikke

Jeff Erickson beskriver i sine noter for Fibonacci-tal:

Den åbenlyse grund til den rekursive algoritmes manglende hastighed er, at den beregner de samme Fibonacci-tal igen og igen og igen.

Vi kan fremskynde vores rekursive algoritme betydeligt bare ved at nedskrive resultaterne af vores rekursive opkald. Så kan vi slå dem op igen, hvis vi har brug for dem senere.

Memoization henviser til teknikken til caching og genbrug af tidligere beregnede resultater.

Hvis du bruger memoization til at løse problemet, gør du det ved at vedligeholde et kort over allerede løste delproblemer (som vi tidligere talte om kortlægning af nøgle og værdi). Du gør det “ top-down ” i den forstand, at du først løser “top” -problemet (som typisk vender tilbage for at løse delproblemerne).

Pseudokode til memoization :

Så ved hjælp af rekursion udfører vi dette med ekstra overheadhukommelse (dvs. her opslag) for at gemme resultater. Hvis der er en værdi gemt i opslaget, returnerer vi den direkte, eller vi tilføjer den til opslag efter det specifikke indeks.

Husk, at der er en afvejning af ekstra omkostninger med hensyn til tabuleringsmetoden.

Men hvis du vil have flere visualiseringer til memoization, så foreslår jeg at se på denne video.

Tabulering: Udfyldning i tabelform

Men når vi først ser, hvordan arrayet (memoized solution) er udfyldt, kan vi erstatte rekursionen med en simpel sløjfe, der med vilje udfylder arrayet i rækkefølge i stedet for at stole på den komplicerede rekursion for at gøre det for os 'tilfældigt'.

Tabulering gør det på “nedenfra og op” måde. Det er mere ligetil, det beregner alle værdier. Det kræver mindre omkostninger, da det ikke behøver at vedligeholde kortlægning og gemmer data i tabelform for hver værdi. Det kan også beregne unødvendige værdier. Dette kan bruges, hvis alt, hvad du vil, er at beregne alle værdier til dit problem.

Pseudokode til tabulering:

Som du kan se pseudokode (højre side) i et billede, udfører det iteration (dvs. løkker over til slutningen af ​​et array). Det starter simpelthen med fib (0), fib (1), fib (2), ... Så med tabuleringsmetoden kan vi eliminere behovet for rekursion og blot returnere resultatet med looping over elementer.

Ser tilbage i historien

Richard bellman var manden bag dette koncept. Han kom op med dette, da han arbejdede for RAND Corporation i midten af ​​1950'erne. Årsagen til, at han valgte dette navn "dynamisk programmering", var at skjule det matematiske arbejde, han udførte for denne forskning. Han var bange for, at hans chefer ville være imod eller ikke lide enhver form for matematisk forskning.

Okay, så ordet 'programmering' er bare en henvisning til at præcisere, at dette var en gammeldags måde at planlægge eller planlægge på, typisk ved at udfylde en tabel (på en dynamisk måde snarere end på en lineær måde) over tiden i stedet for alt på en gang.

Afslutter

Det er det. Dette er del 2 af algoritmeserien, jeg startede sidste år. I mit tidligere indlæg diskuterede vi om, hvad der søger og sorterer algoritmer. Undskyld, at jeg ikke kunne levere dette på kortere tid. Men jeg er villig til at gøre tingene hurtigere i de kommende måneder.

Håber du kunne lide det, og jeg vil snart se på at tilføje en tredje i serien snart. God kodning!

Ressourcer:

Introduktion til dynamisk programmering 1 Tutorials & Notes | Algoritmer | HackerEarth

Billedet ovenfor siger meget om dynamisk programmering. Så gentager de ting, som du allerede har ... www.hackerearth.com Community - Konkurrenceprogrammering - Konkurrenceprogrammeringsvejledninger - Dynamisk programmering: Fra ...

Fællesskab - Konkurrenceprogrammering - Konkurrenceprogrammeringsvejledninger - Dynamisk programmering: Fra nybegynder til avanceret www.topcoder.com

//www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Særlige rekvisitter til Jeff Erickson og hans noter til algoritme - //jeffe.cs.illinois.edu/