Dynamisk programmering er et koncept udviklet af Richard Bellman, en matematiker og økonom.
På det tidspunkt ledte Bellman efter en måde at løse komplekse optimeringsproblemer på. Optimeringsproblemer kræver, at du vælger den bedste løsning fra en række muligheder.
Et eksempel på et optimeringsproblem er Traveling salesman problem. Målet er at finde den korteste rute, så sælgeren kan besøge hver by præcis én gang og vende tilbage til startbyen.
Bellmans tilgang til disse problemer var at opdele dem i mindre delproblemer og løse delproblemerne fra de mindste til de største. Derefter gemte han resultaterne af delproblemerne og genbrugte dem til at løse større delproblemer. Dette er hovedideen bag dynamisk programmering.
Hvad er dynamisk programmering?
Dynamisk programmering løser optimeringsproblemer ved at opdele dem i mindre delproblemer, løse hvert delproblem én gang og gemme deres løsninger, så de kan genbruges og kombineres til at løse det større problem. Problemerne løses fra de mindste til de største, så løsningerne kan genbruges.
Hvordan fungerer dynamisk programmering?
Løsning af et problem ved hjælp af dynamisk programmering involverer følgende trin:
For at se dette i aktion, beregner vi det 6. Fibonacci-tal, F(6), ved hjælp af denne proces.
Først skal du definere de delproblemer, der skal 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 andet trin involverer løsning af hvert delproblem ved hjælp af en rekursiv funktion eller en iterativ proces. Vi løser delproblemerne fra de mindste til de største, og genbruger resultater fra mindre delproblemer. Dette giver os 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
Efterhånden som vi løser hvert af underproblemerne, gemmer vi løsningerne i et array eller en tabel, så de kan genbruges til at løse større underproblemer som sådan:
Når alle underproblemerne er løst, bruger vi løsningerne til at konstruere løsningen til det oprindelige problem.
I dette tilfælde er løsningen på det oprindelige problem det 6. Fibonacci-tal, som findes ved at summere resultaterne af F(5) og F(4), underproblemer identificeret fra det største problem. Resultatet giver os 8.
Hvor og hvorfor bruges dynamisk programmering?
Dynamisk programmering bruges på områder, hvor vi har problemer, der kan opdeles i mindre delproblemer, og deres løsninger bruges til at løse større problemer.
Disse områder omfatter datalogi, økonomi, matematik og teknik. I datalogi bruges det til at løse problemer, der involverer sekvenser, grafer og heltalsværdier og i konkurrencedygtig programmering.
I økonomi bruges det til at løse optimeringsproblemer inden for økonomi, produktion og ressourceallokering. I matematik bruges dynamisk programmering i spilteori, statistik og sandsynlighed, hvor det bruges til at løse optimeringsproblemer.
I teknik bruges det til at løse problemer i ressourceallokering, planlægning, fremstilling, kommunikation og kontrolsystemer.
Der er flere fordele ved at bruge dynamisk programmering til at løse optimeringsproblemer:
Når det kommer til at løse optimeringsproblemer, er dynamisk programmering et meget nyttigt værktøj til at sikre effektivitet i løsninger.
Metoder, der bruges i dynamisk programmering
I dynamisk programmering bruges to tilgange til at løse optimeringsproblemer. Disse er top-down-tilgangen og bottom-up-tilgangen.
Top-down tilgang
Denne tilgang er også kendt som memoization. Memoisering er en optimeringsteknik, der primært bruges til at gøre computerprogrammer hurtigere ved at gemme resultaterne af funktionskald i cachen og returnere de cachelagrede resultater, næste gang de er nødvendige i stedet for at beregne dem igen.
Top-down tilgangen involverer rekursion og caching. Rekursion involverer en funktion, der kalder sig selv med enklere versioner af problemet som argument. Rekursion bruges til at nedbryde problemet i mindre delproblemer og løse delproblemerne.
Når et underproblem er løst, cachelagres dets resultat og genbruges, når et lignende problem opstår. Top-down er let at forstå og implementere og løser kun et delproblem én gang. En ulempe ved det er dog, at det fylder meget hukommelse på grund af rekursion. Dette kan føre til en stak overløbsfejl.
Bottom-up tilgang
Bottom-up tilgangen, også kendt som tabulering, fjerner rekursion og erstatter den med iteration, og undgår dermed stakoverløbsfejl.
I denne tilgang opdeles et stort problem i mindre delproblemer, og løsningerne til delproblemerne bruges til at løse det større problem.
Mindre underproblemer løses først fra det største til det mindste, og deres resultater gemmes i en matrix, matrix eller tabel, deraf navnettabulationen.
De lagrede resultater løser større problemer, der afhænger af delproblemerne. Resultatet af det oprindelige problem findes så ved at løse det største delproblem ved hjælp af tidligere beregnede værdier.
Denne tilgang har den fordel, at den er hukommelses- og tidseffektiv ved at gøre op med rekursion.
Eksempler på problemer, der kan løses ved dynamisk programmering
Følgende er nogle programmeringsproblemer, der kan løses ved hjælp af dynamisk programmering:
#1. Rullesæk problem
Kilde: Wikipedia
En rygsæk er en taske lavet af lærred, nylon eller læder, der typisk er spændt på ryggen og bruges af soldater og vandrere til at bære forsyninger.
I rygproblemet bliver du præsenteret for en rygsæk, og i betragtning af dens bæreevne er du forpligtet til at vælge genstande med hver deres værdi. Dit valg skal være sådan, at du får den maksimale samlede værdi af de udvalgte varer, og vægten af varerne er mindre end eller lig med rygsækkens kapacitet.
Et eksempel på rygsækproblemet er givet nedenfor:
Forestil dig, at du skal på vandretur og har en rygsæk med en kapacitet på 15 kilo. Du har en liste over varer, som du kan medbringe, sammen med deres værdier og vægt, som vist i tabellen nedenfor:
VareVærdiVægtTelt2003Sovepose1502Komfur501Mad1002Vandflaske100.5Førstehjælpskasse251
Vælg en delmængde af emnerne, der skal medbringes, således at den samlede værdi af emnerne maksimeres, mens den samlede vægt er mindre end eller lig med rygsækkens kapacitet, som er 15 kg.
Anvendelser i den virkelige verden af rygsækproblemet involverer at vælge værdipapirer, der skal tilføjes til en portefølje for at minimere risikoen og maksimere fortjenesten og finde de mindst spildfulde måder at skære i råmaterialer på.
#2. Planlægningsproblem
Et planlægningsproblem er et optimeringsproblem, hvor målet er optimalt at tildele opgaver til et sæt ressourcer. Ressourcerne kan være maskiner, personale eller andre ressourcer, der bruges til at udføre opgaverne.
Et eksempel på et planlægningsproblem er givet nedenfor:
Forestil dig, at du er en projektleder med ansvar for at planlægge et sæt opgaver, der skal udføres af et team af medarbejdere. Hver opgave har et starttidspunkt, et sluttidspunkt og en liste over medarbejdere, der er kvalificerede til at udføre den.
Her er en tabel, der beskriver opgaverne og deres karakteristika:
OpgaveStarttid Sluttid Kvalificerede medarbejdereT1911A, B, CT21012A, CT31113B, CT41214A, B
Tildel hver opgave til en medarbejder for at minimere den samlede færdiggørelsestid.
Planlægningsproblemet kan støde på i fremstillingsindustrien, når man forsøger at optimere allokeringen af ressourcer såsom maskiner, materialer, værktøj og arbejdskraft.
Det kan også ses i sundhedsvæsenet, når man optimerer brugen af senge, personale og medicinske forsyninger. Andre industrier, hvor dette problem kan opstå, er projektledelse, supply chain management og uddannelse.
#3. Rejsende sælger problem
Kilde: Wikipedia
Dette er et af de mest undersøgte optimeringsproblemer, der kan løses ved hjælp af dynamisk programmering.
Problemet med den rejsende sælger giver en liste over byer og afstandene mellem hvert par byer. Du er forpligtet til at finde den kortest mulige rute, der besøger hver by nøjagtigt én gang og vender tilbage til oprindelsesbyen.
Et eksempel på et rejsende sælgerproblem er givet nedenfor:
Forestil dig, at du er en sælger, der har brug for at besøge en række byer på kortest mulig tid. Du har en liste over de byer, du skal besøge, og afstandene mellem hvert bypar, som vist i tabellen nedenfor:
CityABCDEA010152030B100352515C153503020D202530010E301520100
Det rejsende sælgerproblem kan blandt andet støde på i fritidsbranchen, når man forsøger at planlægge ruter for turister, logistik ved planlægning af fragt af varer, transport ved planlægning af busruter og i salgsbranchen.
Det er klart, at dynamisk programmering har mange applikationer i den virkelige verden, som hjælper med at lære mere om det.
Overvej følgende ressourcer for at forklare din viden om dynamisk programmering.
Ressourcer
Dynamisk programmering af Richard Bellman
Dynamisk programmering er en bog af Richard Bellman, som fandt på dynamisk programmering og udviklede den i de tidlige stadier.
Bogen er skrevet på en letforståelig måde, der kun kræver grundlæggende viden om matematik og regning for at forstå teksten. I bogen introducerer Bellman den matematiske teori om en flertrinsbeslutningsproces, som er nøglen i dynamisk programmering.
Bogen undersøger derefter flaskehalsproblemer i flertrinsproduktionsprocesser, eksistens- og unikkesætninger og den optimale lagerligning.
Det bedste ved bogen er, at Bellman giver eksempler på mange komplekse problemer inden for områder som logistik, skemalægningsteori, kommunikationsteori, matematisk økonomi og kontrolprocesser og viser, hvordan dynamisk programmering kan løse problemerne.
Bogen er tilgængelig i Kindle-, hardcover- og paperback-versioner.
Masterkursus i dynamiske programmeringsalgoritmer
Dette Dynamic Programming Algorithms Master Course af Udemy tilbydes af Apaar Kamal, en softwareingeniør hos Google, og Prateek Narang, som også arbejdede med Google.
Kurset er optimeret til at hjælpe elever med at udmærke sig i programmeringskonkurrence, som byder på en masse problemer, der kræver dynamisk programmering.
Bortset fra programmeringskonkurrenter er kurset ideelt for programmører, der ønsker at forbedre deres forståelse af algoritmer og folk, der forbereder sig til programmeringsinterviews og online kodningsrunder.
Kurset, som er over 40 timer langt, dækker dynamisk programmering i dybden. Kurset byder først på en genopfriskning af begreber som rekursion og backtracking.
Det dækker derefter dynamisk programmering i spilteori, strenge, træer og grafer, matrixeksponentiering, bitmasker, kombinatorik og delsekvenser, partitionsproblemer og multidimensionel dynamisk programmering, blandt mange andre koncepter.
Konkurrencedygtig programmering Essentials, Master Algorithms
Udemy tilbyder et Competitive Programming Essentials-kursus af Prateek Narang og Amal Kamaar, der dækker dynamisk programmering, matematik, talteori og avancerede datastrukturer og algoritmer på en måde, der er nyttig og relevant for konkurrerende programmører.
Kurset tilbyder en genopfriskning af datastrukturer og algoritmer, før du dykker ned i mere komplekse algoritmer og teknikker, der er nyttige i konkurrencedygtig programmering.
Kurset dækker dynamisk programmering, matematik, spilteori, mønstertilpasning, Bitmasking og et utal af avancerede algoritmer brugt og testet i programmeringskonkurrencer.
Udemy-kurset er opdelt i 10 moduler og 42 sektioner og giver masser af øvelsesspørgsmål efter hvert afsnit. Dette bestseller-kursus er et must-have for alle, der er interesseret i konkurrencedygtig programmering.
Afsluttende ord
Dynamisk programmering er en gavnlig færdighed for enhver programmør at lære at forbedre deres problemløsning af problemer i den virkelige verden. Derfor bør programmører overveje at gennemgå de foreslåede ressourcer for at tilføje dette afgørende værktøj til deres værktøjskasse.
Dernæst kan du tjekke programmeringssprog til brug i datavidenskab.
