Dynamisk programmering är ett koncept utvecklat av Richard Bellman, matematiker och ekonom.
Vid den tiden letade Bellman efter ett sätt att lösa komplexa optimeringsproblem. Optimeringsproblem kräver att du väljer den bästa lösningen från en uppsättning alternativ.
Ett exempel på ett optimeringsproblem är problemet med resande säljare. Målet är att hitta den kortaste vägen så att säljaren kan besöka varje stad exakt en gång och återvända till startstaden.
Bellmans inställning till dessa problem var att dela upp dem i mindre delproblem och lösa delproblemen från det minsta till det största. Han lagrade sedan resultaten av delproblemen och återanvände dem för att lösa större delproblem. Detta är huvudtanken bakom dynamisk programmering.
Innehållsförteckning
Vad är dynamisk programmering?
Dynamisk programmering löser optimeringsproblem genom att dela upp dem i mindre delproblem, lösa varje delproblem en gång och lagra deras lösningar så att de kan återanvändas och kombineras för att lösa det större problemet. Problemen löses från de minsta till de största, vilket gör att lösningarna kan återanvändas.
Hur fungerar dynamisk programmering?
Att lösa ett problem med dynamisk programmering innebär följande steg:
För att se detta i aktion, beräknar vi det 6:e Fibonacci-talet, F(6), med hjälp av denna process.
Definiera först de delproblem som måste lösas.
F(n) = F(n-1) + F(n-2) för n > 1
Därför: 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 andra steget innebär att lösa varje delproblem med hjälp av en rekursiv funktion eller en iterativ process. Vi löser delproblemen från de minsta till de största och återanvänder resultat från mindre delproblem. Detta ger oss följande:
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 vart och ett av delproblemen lagrar vi lösningarna i en array eller tabell så att de kan återanvändas för att lösa större delproblem som så:
När alla delproblem har lösts använder vi lösningarna för att konstruera lösningen till det ursprungliga problemet.
I det här fallet är lösningen på det ursprungliga problemet det 6:e Fibonacci-talet, som hittas genom att summera resultaten av F(5) och F(4), delproblem identifierade från det största problemet. Resultatet ger oss 8.
Var och varför används dynamisk programmering?
Dynamisk programmering används inom områden där vi har problem som kan delas upp i mindre delproblem, och deras lösningar används för att lösa större problem.
Dessa områden inkluderar datavetenskap, ekonomi, matematik och teknik. Inom datavetenskap används det för att lösa problem som involverar sekvenser, grafer och heltalsvärden och i konkurrenskraftig programmering.
Inom ekonomi används det för att lösa optimeringsproblem inom ekonomi, produktion och resursallokering. Inom matematiken används dynamisk programmering inom spelteori, statistik och sannolikhet, där det används för att lösa optimeringsproblem.
Inom tekniken används det för att lösa problem i resursallokering, schemaläggning, tillverkning, kommunikation och kontrollsystem.
Det finns flera fördelar med att använda dynamisk programmering för att lösa optimeringsproblem:
När det gäller att lösa optimeringsproblem är dynamisk programmering ett mycket användbart verktyg för att säkerställa effektivitet i lösningar.
Tillvägagångssätt som används i dynamisk programmering
Inom dynamisk programmering används två tillvägagångssätt för att lösa optimeringsproblem. Dessa är top-down-metoden och bottom-up-metoden.
Uppifrån och ner tillvägagångssätt
Detta tillvägagångssätt är också känt som memoization. Memoisering är en optimeringsteknik som främst används för att göra datorprogram snabbare genom att lagra resultaten av funktionsanrop i cachen och returnera de cachade resultaten nästa gång de behövs istället för att beräkna dem igen.
Top-down-metoden involverar rekursion och cachning. Rekursion innebär att en funktion anropar sig själv med enklare versioner av problemet som argument. Rekursion används för att bryta ner problemet i mindre delproblem och lösa delproblemen.
När ett delproblem är löst, cachelagras resultatet och återanvänds när ett liknande problem uppstår. Top-down är lätt att förstå och implementera och löser bara ett delproblem en gång. En nackdel med det är dock att det tar upp mycket minne på grund av rekursion. Detta kan leda till ett stackspillfel.
Bottom-up-metoden
Bottom-up-metoden, även känd som tabulering, tar bort rekursion och ersätter den med iteration och undviker på så sätt stackoverflow-fel.
I detta tillvägagångssätt bryts ett stort problem upp i mindre delproblem, och lösningarna för delproblemen används för att lösa det större problemet.
Mindre delproblem löses först från det största till det minsta, och deras resultat lagras i en matris, array eller tabell, därav namntabellen.
De lagrade resultaten löser större problem som beror på delproblemen. Resultatet av det ursprungliga problemet hittas sedan genom att lösa det största delproblemet med hjälp av tidigare beräknade värden.
Detta tillvägagångssätt har fördelen av att vara minnes- och tidseffektivt genom att avskaffa rekursion.
Exempel på problem som kan lösas genom dynamisk programmering
Följande är några programmeringsproblem som kan lösas med dynamisk programmering:
#1. Knapsäcksproblem
Källa: Wikipedia
En ryggsäck är en väska gjord av duk, nylon eller läder som vanligtvis är fastspänd på ryggen och används av soldater och vandrare för att bära förnödenheter.
I ryggsäcksproblemet får du en ryggsäck och med tanke på dess bärförmåga måste du välja föremål, var och en med sitt värde. Ditt urval bör vara sådant att du får det maximala totala värdet av de plockade föremålen och vikten på föremålen är mindre än eller lika med ryggsäckens kapacitet.
Ett exempel på ryggsäcksproblemet ges nedan:
Föreställ dig att du ska på vandring och har en ryggsäck med en kapacitet på 15 kilo. Du har en lista över föremål som du kan ta med dig, tillsammans med deras värden och vikter, som visas i tabellen nedan:
ArtikelVärdeViktTält2003Sovsäck1502Spis501Mat1002Vattenflaska100.5Första hjälpen-kit251
Välj en delmängd av föremålen att ta med så att det totala värdet av föremålen maximeras medan den totala vikten är mindre än eller lika med ryggsäckens kapacitet, som är 15 kg.
Verkliga tillämpningar av ryggsäcksproblemet involverar att välja värdepapper att lägga till en portfölj för att minimera risker och maximera vinsten och hitta de minst slösaktiga sätten att skära ner på råvaror.
#2. Schemaläggningsproblem
Ett schemaläggningsproblem är ett optimeringsproblem där målet är att optimalt tilldela uppgifter till en uppsättning resurser. Resurserna kan vara maskiner, personal eller andra resurser som används för att slutföra uppgifterna.
Ett exempel på ett schemaläggningsproblem ges nedan:
Föreställ dig att du är en projektledare med ansvar för att schemalägga en uppsättning uppgifter som måste utföras av ett team av anställda. Varje uppgift har en starttid, en sluttid och en lista över anställda som är kvalificerade att slutföra den.
Här är en tabell som beskriver uppgifterna och deras egenskaper:
Uppgift Starttid Sluttid Kvalificerade medarbetareT1911A, B, CT21012A, CT31113B, CT41214A, B
Tilldela varje uppgift till en anställd för att minimera den totala slutförandetiden.
Schemaläggningsproblemet kan uppstå i tillverkningsindustrin när man försöker optimera allokeringen av resurser som maskiner, material, verktyg och arbetskraft.
Det kan också förekomma inom sjukvården när man optimerar användningen av sängar, personal och medicinska förnödenheter. Andra branscher där detta problem kan uppstå är projektledning, supply chain management och utbildning.
#3. Resande säljare problem
Källa: Wikipedia
Detta är ett av de mest studerade optimeringsproblemen som kan lösas med hjälp av dynamisk programmering.
Problemet med resande försäljare ger en lista över städer och avstånden mellan varje par av städer. Du måste hitta den kortaste möjliga vägen som besöker varje stad exakt en gång och återvänder till ursprungsstaden.
Ett exempel på ett resandeförsäljarproblem ges nedan:
Föreställ dig att du är en säljare som behöver besöka en uppsättning städer på kortast möjliga tid. Du har en lista över de städer som du behöver besöka och avstånden mellan varje par av städer, som visas i tabellen nedan:
CityABCDEA010152030B100352515C153503020D202530010E301520100
Det resande säljarproblemet kan man stöta på inom fritidsbranschen när man försöker planera rutter för turister, logistik vid planering av frakt av varor, transporter vid planering av busslinjer och i försäljningsbranschen med flera.
Uppenbarligen har dynamisk programmering många verkliga tillämpningar, vilket hjälper dig att lära dig mer om det.
Överväg följande resurser för att förklara dina kunskaper om dynamisk programmering.
Resurser
Dynamisk programmering av Richard Bellman
Dynamisk programmering är en bok av Richard Bellman, som kom på dynamisk programmering och utvecklade den i dess tidiga skeden.
Boken är skriven på ett lättförståeligt sätt som bara kräver grundläggande kunskaper i matematik och kalkyl för att förstå texten. I boken introducerar Bellman den matematiska teorin om en beslutsprocess i flera steg som är nyckeln i dynamisk programmering.
Boken undersöker sedan flaskhalsproblem i flerstegsproduktionsprocesser, existens- och unikhetsteorem och den optimala lagerekvationen.
Det bästa med boken är att Bellman ger exempel på många komplexa problem inom områden som logistik, schemaläggningsteori, kommunikationsteori, matematisk ekonomi och styrprocesser och visar hur dynamisk programmering kan lösa problemen.
Boken finns i Kindle, inbunden och pocketversioner.
Masterkurs i dynamiska programmeringsalgoritmer
Denna masterkurs i dynamiska programmeringsalgoritmer av Udemy erbjuds av Apaar Kamal, en mjukvaruingenjör på Google, och Prateek Narang, som också arbetade med Google.
Kursen är optimerad för att hjälpa elever att utmärka sig i programmeringstävling som innehåller många problem som kräver dynamisk programmering.
Förutom programmeringskonkurrenter är kursen idealisk för programmerare som vill förbättra sin förståelse för algoritmer och personer som förbereder sig för programmeringsintervjuer och onlinekodningsrundor.
Kursen, som är över 40 timmar lång, täcker dynamisk programmering på djupet. Kursen ger först en repetition om begrepp som rekursion och backtracking.
Den täcker sedan dynamisk programmering i spelteori, strängar, träd och grafer, matrisexponentiering, bitmasker, kombinatorik och delsekvenser, partitionsproblem och multidimensionell dynamisk programmering, bland många andra koncept.
Konkurrenskraftig programmering Essentials, Master Algorithms
Udemy erbjuder en Competitive Programming Essentials-kurs av Prateek Narang och Amal Kamaar som täcker dynamisk programmering, matematik, talteori och avancerade datastrukturer och algoritmer på ett sätt som är användbart och relevant för konkurrerande programmerare.
Kursen ger en repetition om datastrukturer och algoritmer innan du dyker in i mer komplexa algoritmer och tekniker som kommer väl till pass i konkurrenskraftig programmering.
Kursen omfattar dynamisk programmering, matematik, spelteori, mönstermatchning, Bitmasking och en myriad av avancerade algoritmer som används och testas i programmeringstävlingar.
Udemy-kursen är uppdelad i 10 moduler och 42 avsnitt och ger massor av övningsfrågor efter varje avsnitt. Den här bästsäljarkursen är ett måste för alla som är intresserade av konkurrenskraftig programmering.
Slutord
Dynamisk programmering är en fördelaktig färdighet för alla programmerare att lära sig att förbättra sin problemlösning av verkliga problem. Därför bör programmerare överväga att gå igenom de föreslagna resurserna för att lägga till detta avgörande verktyg i sin verktygslåda.
Därefter kan du kolla in programmeringsspråk att använda inom datavetenskap.