DYNAMISK PROGRAMMERING: EGENSKAPER, EKSEMPEL, FORDELER, ULEMPER - TEKNOLOGI - 2026

Den dynamiske programmeringen er en modellalgoritme som løser et komplekst problem ved å dele det opp i delproblemer, lagre resultatene derav for å unngå å måtte beregne resultatene på nytt.

Denne planen brukes når du har problemer som kan deles inn i lignende underproblemer, slik at resultatene kan brukes på nytt. For det meste brukes denne planen til optimalisering.

Dynamisk programmering. Underproblemer lagt over i Fibonacci-sekvensen. Kilde: Wikimedia commons, en: Bruker: Dcoatzee, sporet av Bruker: Stannert / Public domain

Før du løser det tilgjengelige delproblemet, vil den dynamiske algoritmen forsøke å undersøke resultatene fra de tidligere løste delproblemene. Løsningene til delproblemene kombineres for å oppnå den beste løsningen.

I stedet for å beregne det samme underproblemet om og om igjen, kan du lagre løsningen i litt minne når du støter på dette underproblemet. Når den vises igjen under løsningen av et annet underproblem, vil løsningen som allerede er lagret i minnet, tas.

Dette er en fantastisk idé for å fikse minnetid, hvor bruk av ekstra plass kan forbedre tiden som kreves for å finne en løsning.

Funksjoner ved dynamisk programmering

Følgende viktige egenskaper er det du må ha et problem med før dynamisk programmering kan brukes:

Optimal understruktur

Denne egenskapen uttrykker at et optimaliseringsproblem kan løses ved å kombinere de optimale løsningene av de sekundære problemene som omfatter det. Disse optimale understrukturer er beskrevet ved rekursjon.

For eksempel, i en graf vil en optimal understruktur bli presentert i den korteste banen r som går fra en toppunkt s til en toppunkt t:

Det vil si at på denne korteste veien kan noen mellomliggende toppunkt i tas. Hvis r virkelig er den korteste ruten, kan den deles inn i undergrensene r1 (fra s til i) og r2 (fra i til t), på en slik måte at disse igjen er de korteste rutene mellom de korresponderende toppunktene.

Derfor, for å finne de korteste stiene, kan løsningen lett formuleres rekursivt, og det er det Floyd-Warshall-algoritmen gjør.

Overlappende delproblemer

Underproblemrommet må være lite. Det vil si at enhver rekursiv algoritme som løser et problem, må løse de samme delproblemene om og om igjen, i stedet for å generere nye delproblemer.

For å generere Fibonacci-serien, kan vi for eksempel vurdere denne rekursive formuleringen: Fn = F (n - 1) + F (n - 2), som utgangspunkt som F1 = F2 = 1. Da vil vi ha: F33 = F32 + F31, og F32 = F31 + F30.

Som du ser, blir F31 løst inn i de rekursive undertrinnene til både F33 og F32. Selv om det totale antallet delproblemer virkelig er lite, vil du ende opp med å løse de samme problemene om og om igjen hvis du tar i bruk en rekursiv løsning som denne.

Dette tas i betraktning ved dynamisk programmering, så det løser hvert underproblem bare en gang. Dette kan oppnås på to måter:

Top-down tilnærming

Hvis løsningen på ethvert problem kan formuleres rekursivt ved bruk av løsningen av delproblemene, og hvis disse delproblemene overlapper hverandre, kan løsningene på delproblemene enkelt lagres eller lagres i en tabell.

Hver gang du søker i en ny delproblemløsning, vil tabellen sjekkes for å se om den tidligere ble løst. I tilfelle en løsning er lagret, vil den bli brukt i stedet for å beregne den igjen. Ellers vil delproblemet løses ved å lagre løsningen i tabellen.

Bottom-up tilnærming

Etter at løsningen av et problem er formulert rekursivt med tanke på delproblemene, er det mulig å prøve å omformulere problemet på en oppadgående måte: først vil vi prøve å løse delproblemene og bruke deres løsninger for å komme frem til løsninger på de større delproblemene.

Dette gjøres vanligvis i tabellform, og iterativt genererer løsninger for større og større delproblemer ved å bruke løsninger på mindre delproblemer. Hvis for eksempel F31 og F30 allerede er kjent, kan verdien av F32 beregnes direkte.

Sammenligning med andre teknikker

Et vesentlig trekk ved et problem som kan løses ved dynamisk programmering, er at det skal ha overproblemer som overlapper hverandre. Det er dette som skiller dynamisk programmering fra skillet og erobringsteknikken, der det ikke er nødvendig å lagre de enkleste verdiene.

Det ligner rekursjon, siden når beregningen av basissakene, kan den endelige verdien bestemmes induktivt. Denne bottom-up-tilnærmingen fungerer bra når en ny verdi bare avhenger av tidligere beregnede verdier.

Eksempel

Minimum trinn for å nå 1

For et hvilket som helst positivt heltall "e" kan et av de følgende tre trinn utføres.

- Trekk 1 fra tallet. (e = e-1).

- Hvis det kan deles med 2, er det delt med 2 (hvis e% 2 == 0, så e = e / 2).

- Hvis det er delbart med 3, er det delt med 3 (hvis e% 3 == 0, så e = e / 3).

Basert på trinnene ovenfor, skal minimum antall av disse trinnene være funnet å bringe e til 1. For eksempel:

- Hvis e = 1, resultat: 0.

- Hvis e = 4, resultat: 2 (4/2 = 2/2 = 1).

- Når e = 7, resultat: 3 (7-1 = 6/3 = 2/2 = 1).

Fokus

Man kan tenke på å alltid velge trinnet som gjør n så lavt som mulig og fortsette slik, til det når 1. Imidlertid kan man se at denne strategien ikke fungerer her.

For eksempel, hvis e = 10, ville trinnene være: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 trinn). Imidlertid er den optimale formen: 10-1 = 9/3 = 3/3 = 1 (3 trinn). Derfor må alle mulige trinn som kan gjøres for hver verdi av n funnet, prøve, ved å velge minimum antall av disse mulighetene.

Det hele starter med rekursjon: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} hvis e> 1, tar utgangspunkt: F (1) = 0. Med gjentagelsesligningen kan du begynne å kode rekursjonen.

Imidlertid kan det sees at det har overlappende delproblemer. Videre avhenger den optimale løsningen for et gitt innspill av den optimale løsningen av delproblemene.

Som i memorering, der løsningene til delproblemene som er løst, lagres for senere bruk. Eller som i dynamisk programmering, du starter på bunnen, og jobber deg frem til den gitte e. Så begge kodene:

utenatlæring

Dynamisk programmering nedenfra og opp

Fordel

En av hovedfordelene ved å bruke dynamisk programmering er at det fremskynder behandlingen, siden referanser som tidligere ble beregnet blir brukt. Siden det er en rekursiv programmeringsteknikk, reduserer den kodelinjene i programmet.

Voracious algoritmer vs dynamisk programmering

Grådige algoritmer ligner dynamisk programmering ved at de begge er verktøy for optimalisering. Den grådige algoritmen ser imidlertid etter en optimal løsning på hvert lokalt trinn. Det vil si at den søker et grådig valg i håp om å finne et globalt optimum.

Derfor kan grådige algoritmer gjøre en antagelse som ser optimal ut den gang, men blir dyr i fremtiden og ikke garanterer et globalt optimalt.

På den annen side finner dynamisk programmering den optimale løsningen for delproblemene, og tar deretter et informert valg ved å kombinere resultatene fra disse delproblemene for å faktisk finne den mest optimale løsningen.

ulemper

- Det trengs mye minne for å lagre det beregnede resultatet av hvert underproblem, uten å kunne garantere at den lagrede verdien blir brukt eller ikke.

- Mange ganger lagres utgangsverdien uten å bli brukt i følgende underproblemer under utførelse. Dette fører til unødvendig minnebruk.

- I dynamisk programmering kalles funksjoner rekursivt. Dette gjør at minnet til stakken stadig øker.

Rekursjon vs dynamisk programmering

Hvis du har begrenset minne til å kjøre koden din og behandlingshastighet ikke er noe problem, kan du bruke rekursjon. For eksempel, hvis du utvikler en mobilapplikasjon, er minnet svært begrenset til å kjøre applikasjonen.

Hvis du vil at programmet skal kjøres raskere og har ingen minnebegrensninger, foretrekker det å bruke dynamisk programmering.

applikasjoner

Dynamisk programmering er en effektiv metode for å løse problemer som ellers kan virke ekstremt vanskelig å løse på rimelig tid.

Algoritmer basert på det dynamiske programmeringsparadigmet brukes i mange vitenskapsområder, inkludert mange eksempler innen kunstig intelligens, fra planlegging av problemløsing til talegjenkjenning.

Algoritmer basert på dynamisk programmering

Dynamisk programmering er ganske effektiv og fungerer veldig bra for en lang rekke problemer. Mange algoritmer kan sees på som grådige algoritmeapplikasjoner, for eksempel:

- Fibonacci-tallserie.

- Towers of Hanoi.

- Alle par kortere ruter gjennom Floyd-Warshall.

- Ryggsekkproblem.

- Prosjektplanlegging.

- Den korteste veien gjennom Dijkstra.

- Flykontroll og robotkontroll.

- Matematiske optimaliseringsproblemer.

- Timeshare: planlegge jobben for å maksimere CPU-bruken.

Fibonacci-tallserie

Fibonacci-tall er tallene som er funnet i følgende sekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

I matematisk terminologi er sekvensen Fn for Fibonacci-tall definert av gjentakelsesformelen: F (n) = F (n -1) + F (n -2), der F (0) = 0 og F ( 1) = 1.

Top-down tilnærming

I dette eksemplet initialiseres et søkearray med alle startverdiene med -1. Hver gang løsningen på et delproblem er nødvendig, blir denne søkematrisen først søkt.

Hvis den beregnede verdien er der, vil den verdien bli returnert. Ellers blir resultatet beregnet for å bli lagret i søkefeltet, slik at det kan gjenbrukes senere.

Bottom-up tilnærming

I dette tilfellet beregnes f (0) for den samme Fibonacci-serien først, deretter f (1), f (2), f (3) og så videre. Dermed blir løsningene til delproblemene konstruert nedenfra og opp.

referanser

1. Vineet Choudhary (2020). Introduksjon til dynamisk programmering. Developer Insider. Hentet fra: Developerinsider.co.
2. Alex Allain (2020). Dynamisk programmering i C ++. C-programmering. Hentet fra: cprogramming.com.
3. Etter akademiet (2020). Ideen om dynamisk programmering. Hentet fra: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamisk programmering og rekursjon - Forskjell, fordeler med eksempel. CSE Stack. Hentet fra: csestack.org.
5. Code Chef (2020). Opplæring for dynamisk programmering. Hentet fra: codechef.com.
6. Programiz (2020). Dynamisk programmering. Hentet fra: programiz.com.