Dynamisk programmering er et konsept utviklet av Richard Bellman, en matematiker og økonom.
På den tiden lette Bellman etter en måte å løse komplekse optimaliseringsproblemer. Optimaliseringsproblemer krever at du velger den beste løsningen fra et sett med alternativer.
Et eksempel på et optimaliseringsproblem er Traveling salesman-problemet. Målet er å finne den korteste ruten slik at selgeren kan besøke hver by nøyaktig én gang og returnere til startbyen.
Bellmans tilnærming til disse problemene var å dele dem opp i mindre delproblemer og løse delproblemene fra de minste til de største. Deretter lagret han resultatene av delproblemene og brukte dem på nytt for å løse større delproblemer. Dette er hovedideen bak dynamisk programmering.
Innholdsfortegnelse
Hva er dynamisk programmering?
Dynamisk programmering løser optimaliseringsproblemer ved å bryte dem ned i mindre delproblemer, løse hvert delproblem én gang og lagre løsningene deres slik at de kan gjenbrukes og kombineres for å løse det større problemet. Problemene løses fra de minste til de største, slik at løsninger kan gjenbrukes.
Hvordan fungerer dynamisk programmering?
Å løse et problem ved hjelp av dynamisk programmering innebærer følgende trinn:
For å se dette i aksjon, beregner vi det 6. Fibonacci-tallet, F(6), ved å bruke denne prosessen.
Først definerer du underproblemene som må løses.
F(n) = F(n-1) + F(n-2) for n > 1
Derfor: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Det andre trinnet innebærer å løse hvert delproblem ved å bruke en rekursiv funksjon eller en iterativ prosess. Vi løser delproblemene fra de minste til de største, og gjenbruker resultater fra mindre delproblemer. Dette gir oss følgende:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Når vi løser hvert av underproblemene, lagrer vi løsningene i en matrise eller tabell slik at de kan gjenbrukes til å løse større underproblemer som slik:
Når alle delproblemene er løst, bruker vi løsningene til å konstruere løsningen på det opprinnelige problemet.
I dette tilfellet er løsningen på det opprinnelige problemet det 6. Fibonacci-tallet, som finnes ved å summere resultatene av F(5) og F(4), underproblemer identifisert fra det største problemet. Resultatet gir oss 8.
Hvor og hvorfor brukes dynamisk programmering?
Dynamisk programmering brukes i områder hvor vi har problemer som kan deles inn i mindre delproblemer, og deres løsninger brukes til å løse større problemer.
Disse områdene inkluderer informatikk, økonomi, matematikk og ingeniørfag. I informatikk brukes det til å løse problemer som involverer sekvenser, grafer og heltallsverdier og i konkurrerende programmering.
I økonomi brukes det til å løse optimaliseringsproblemer innen økonomi, produksjon og ressursallokering. I matematikk brukes dynamisk programmering i spillteori, statistikk og sannsynlighet, hvor det brukes til å løse optimaliseringsproblemer.
I ingeniørfag brukes det til å løse problemer innen ressursallokering, planlegging, produksjon, kommunikasjon og kontrollsystemer.
Det er flere fordeler med å bruke dynamisk programmering for å løse optimaliseringsproblemer:
Når det gjelder å løse optimaliseringsproblemer, er dynamisk programmering et svært nyttig verktøy for å sikre effektivitet i løsninger.
Tilnærminger som brukes i dynamisk programmering
I dynamisk programmering brukes to tilnærminger for å løse optimaliseringsproblemer. Dette er top-down-tilnærmingen og bottom-up-tilnærmingen.
Topp-ned-tilnærming
Denne tilnærmingen er også kjent som memoisering. Memoisering er en optimaliseringsteknikk som primært brukes til å gjøre dataprogrammer raskere ved å lagre resultatene av funksjonsanrop i hurtigbufferen og returnere de hurtigbufrede resultatene neste gang de trengs i stedet for å beregne dem på nytt.
Top-down-tilnærmingen innebærer rekursjon og caching. Rekursjon innebærer en funksjon som kaller seg selv med enklere versjoner av problemet som argument. Rekursjon brukes til å bryte ned problemet i mindre delproblemer og løse delproblemene.
Når et underproblem er løst, bufres resultatet og brukes på nytt når et lignende problem oppstår. Top-down er lett å forstå og implementere og løser bare et delproblem én gang. En ulempe med det er imidlertid at det tar opp mye minne på grunn av rekursjon. Dette kan føre til en stabeloverløpsfeil.
Bottom-up-tilnærming
Bottom-up-tilnærmingen, også kjent som tabulering, fjerner rekursjon, erstatter den med iterasjon, og unngår dermed stabeloverløpsfeil.
I denne tilnærmingen brytes et stort problem inn i mindre delproblemer, og løsningene for delproblemene brukes til å løse det større problemet.
Mindre underoppgaver løses først fra det største til det minste, og resultatene deres lagres i en matrise, matrise eller tabell, derav navnettabellen.
De lagrede resultatene løser større problemer som avhenger av delproblemene. Resultatet av det opprinnelige problemet blir så funnet ved å løse det største delproblemet ved å bruke tidligere beregnede verdier.
Denne tilnærmingen har fordelen av å være minne- og tidseffektiv ved å gjøre unna rekursjon.
Eksempler på problemer som kan løses ved dynamisk programmering
Følgende er noen programmeringsproblemer som kan løses ved hjelp av dynamisk programmering:
#1. Rullesekk problem
Kilde: Wikipedia
En ryggsekk er en veske laget av lerret, nylon eller lær som vanligvis er festet på ryggen og brukt av soldater og turgåere til å bære forsyninger.
I ryggsekkproblemet blir du presentert med en ryggsekk, og gitt dens bæreevne er du pålagt å velge gjenstander, hver med sin verdi. Ditt valg bør være slik at du får den maksimale totalverdien av varene plukket og vekten av varene er mindre enn eller lik ryggsekkens kapasitet.
Et eksempel på ryggsekkproblemet er gitt nedenfor:
Se for deg at du skal på fottur og har en ryggsekk med en kapasitet på 15 kilo. Du har en liste over gjenstander du kan ta med deg, sammen med deres verdier og vekt, som vist i tabellen nedenfor:
VareVerdi Vekt Telt2003Sovepose1502Komfyr501Mat1002Vannflaske100.5Førstehjelpsutstyr251
Velg et undersett av gjenstandene som skal bringes, slik at den totale verdien av gjenstandene maksimeres mens totalvekten er mindre enn eller lik ryggsekkens kapasitet, som er 15 kilo.
Reelle anvendelser av ryggsekkproblemet innebærer å velge verdipapirer for å legge til en portefølje for å minimere risiko og maksimere fortjeneste og finne de minst sløsede måtene å kutte råvarer på.
#2. Planleggingsproblem
Et planleggingsproblem er et optimaliseringsproblem der målet er å tilordne oppgaver optimalt til et sett med ressurser. Ressursene kan være maskiner, personell eller andre ressurser som brukes for å fullføre oppgavene.
Et eksempel på et planleggingsproblem er gitt nedenfor:
Tenk deg at du er en prosjektleder med ansvar for å planlegge et sett med oppgaver som må fullføres av et team med ansatte. Hver oppgave har en starttid, en sluttid og en liste over ansatte som er kvalifisert til å fullføre den.
Her er en tabell som beskriver oppgavene og deres egenskaper:
OppgaveStarttid SlutttidKvalifiserte ansatteT1911A, B, CT21012A, CT31113B, CT41214A, B
Tilordne hver oppgave til en ansatt for å minimere den totale gjennomføringstiden.
Planleggingsproblemet kan oppstå i produksjonsindustrien når man prøver å optimalisere allokeringen av ressurser som maskiner, materialer, verktøy og arbeidskraft.
Det kan også oppstå i helsevesenet når du optimaliserer bruken av senger, personell og medisinsk utstyr. Andre bransjer der dette problemet kan oppstå er prosjektledelse, forsyningskjedestyring og utdanning.
#3. Reisende selgerproblem
Kilde: Wikipedia
Dette er et av de mest studerte optimaliseringsproblemene som kan løses ved hjelp av dynamisk programmering.
Problemet med reisende selger gir en liste over byer og avstander mellom hvert bypar. Du må finne den korteste mulige ruten som besøker hver by nøyaktig én gang og returnerer til opprinnelsesbyen.
Et eksempel på et reisende selgerproblem er gitt nedenfor:
Tenk deg at du er en selger som trenger å besøke et sett med byer på kortest mulig tid. Du har en liste over byene du må besøke og avstandene mellom hvert bypar, som vist i tabellen nedenfor:
CityABCDEA010152030B100352515C153503020D202530010E301520100
Det reisende selgerproblemet kan blant annet støtes på i fritidsbransjen når man prøver å planlegge ruter for turister, logistikk når man planlegger frakt av varer, transport når man planlegger bussruter og i salgsbransjen.
Det er klart at dynamisk programmering har mange applikasjoner i den virkelige verden, noe som hjelper deg å lære mer om det.
Vurder følgende ressurser for å forklare kunnskapen din om dynamisk programmering.
Ressurser
Dynamisk programmering av Richard Bellman
Dynamisk programmering er en bok av Richard Bellman, som kom opp med dynamisk programmering og utviklet den i de tidlige stadiene.
Boken er skrevet på en lettfattelig måte som kun krever grunnleggende kunnskaper i matematikk og regning for å forstå teksten. I boken introduserer Bellman den matematiske teorien om en flertrinns beslutningsprosess som er nøkkelen i dynamisk programmering.
Boken undersøker deretter flaskehalsproblemer i flertrinns produksjonsprosesser, eksistens- og unikhetsteoremer, og den optimale lagerligningen.
Det beste med boka er at Bellman gir eksempler på mange komplekse problemer innen felt som logistikk, planleggingsteori, kommunikasjonsteori, matematisk økonomi og kontrollprosesser og viser hvordan dynamisk programmering kan løse problemene.
Boken er tilgjengelig i Kindle-, hardcover- og pocketversjoner.
Masterkurs i dynamiske programmeringsalgoritmer
Dette masterkurset for dynamiske programmeringsalgoritmer av Udemy tilbys av Apaar Kamal, en programvareingeniør hos Google, og Prateek Narang, som også jobbet med Google.
Kurset er optimalisert for å hjelpe elever til å utmerke seg i programmeringskonkurranse som inneholder mange problemer som krever dynamisk programmering.
Bortsett fra programmeringskonkurrenter, er kurset ideelt for programmerere som ønsker å forbedre sin forståelse av algoritmer og folk som forbereder seg til programmeringsintervjuer og online kodingsrunder.
Kurset, som er over 40 timer langt, dekker dynamisk programmering i dybden. Kurset tilbyr først en oppfriskning av begreper som rekursjon og tilbakesporing.
Den dekker deretter dynamisk programmering i spillteori, strenger, trær og grafer, matriseeksponentiering, bitmasker, kombinatorikk og undersekvenser, partisjonsproblemer og flerdimensjonal dynamisk programmering, blant mange andre konsepter.
Konkurransedyktig programmering Essentials, Master Algoritmer
Udemy tilbyr et Competitive Programming Essentials-kurs av Prateek Narang og Amal Kamaar som dekker dynamisk programmering, matematikk, tallteori og avanserte datastrukturer og algoritmer på en måte som er nyttig og relevant for konkurrerende programmerere.
Kurset tilbyr en oppfriskning av datastrukturer og algoritmer før du dykker ned i mer komplekse algoritmer og teknikker som kommer godt med i konkurrerende programmering.
Kurset dekker dynamisk programmering, matematikk, spillteori, mønstertilpasning, Bitmasking, og et mylder av avanserte algoritmer brukt og testet i programmeringskonkurranser.
Udemy-kurset er delt inn i 10 moduler og 42 seksjoner og gir mange øvelsesspørsmål etter hver seksjon. Dette bestselgerkurset er et must for alle som er interessert i konkurrerende programmering.
Siste ord
Dynamisk programmering er en fordelaktig ferdighet for enhver programmerer å lære å forbedre sin problemløsning av virkelige problemer. Derfor bør programmerere vurdere å gå gjennom de foreslåtte ressursene for å legge til dette viktige verktøyet i verktøykassen deres.
Deretter kan du sjekke ut programmeringsspråk du kan bruke i datavitenskap.