Dynamisk programmering, en metodik framtagen av Richard Bellman, en framstående matematiker och ekonom, revolutionerade sättet att tackla komplicerade optimeringsutmaningar.
Bellmans strävan var att finna en effektiv lösning på komplexa optimeringsproblem, som i grunden handlar om att välja det bästa alternativet från en mängd möjliga lösningar.
Ett klassiskt exempel på ett sådant problem är ”handelsresandeproblemet”, där målet är att identifiera den kortaste resvägen för en säljare som ska besöka varje stad en gång och sedan återvända till startpunkten.
Bellman föreslog en metod där man delar upp dessa problem i mindre, mer hanterbara delproblem. Dessa delproblem löses sedan från de enklaste till de mer komplexa. Lösningarna på dessa delproblem lagras och återanvänds för att lösa ännu större delar av det ursprungliga problemet. Denna grundprincip utgör kärnan i dynamisk programmering.
Vad innebär dynamisk programmering?
Dynamisk programmering är en teknik som löser optimeringsproblem genom att bryta ner dem i mindre delproblem. Varje delproblem hanteras separat och dess lösning sparas, vilket möjliggör återanvändning och kombination av lösningar för att angripa det övergripande problemet. Processen fortlöper från de enklaste till de mer komplexa delproblemen, vilket effektiviserar återanvändning av tidigare erhållna resultat.
Hur fungerar dynamisk programmering i praktiken?
Dynamisk programmering innefattar följande steg för att lösa ett problem:
- Identifiera delproblemen: Det stora problemet delas upp i mindre, mer hanterbara enheter.
- Lös delproblemen: Varje delproblem hanteras, antingen genom rekursiva metoder eller iterativa processer.
- Spara resultaten: Lösningar på delproblemen lagras för framtida återanvändning.
- Konstruera den övergripande lösningen: Lösningen på det ursprungliga problemet skapas genom att kombinera resultaten från de lösta delproblemen.
Låt oss illustrera detta med ett exempel: beräkning av det sjätte Fibonacci-talet, F(6).
Först identifierar vi delproblemen:
F(n) = F(n-1) + F(n-2) , där n > 1
Detta innebär att:
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
I nästa steg löser vi varje delproblem, antingen med rekursion eller iterativt, från de enklaste till de mer komplexa, och återanvänder tidigare lösningar. Detta ger:
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
Lösningarna på delproblemen lagras i en array eller tabell för att möjliggöra återanvändning när vi går vidare till mer komplexa problem:
När alla delproblem är lösta kombineras dessa lösningar för att skapa den slutgiltiga lösningen på det ursprungliga problemet.
I detta specifika fall erhålls lösningen på det ursprungliga problemet, det vill säga det sjätte Fibonacci-talet, genom att addera resultaten av F(5) och F(4), vilket ger oss 8.
Var och varför tillämpas dynamisk programmering?
Dynamisk programmering är särskilt lämplig för problem som kan brytas ner i mindre delar, där lösningarna på dessa delar används för att lösa det större problemet.
Denna teknik används inom många områden som datavetenskap, ekonomi, matematik och ingenjörsvetenskap. Inom datavetenskap tillämpas den för problem som rör sekvenser, grafer, heltal samt i tävlingsprogrammering.
Inom ekonomi används dynamisk programmering för optimeringsproblem inom områden som finans, produktion och resursfördelning. Inom matematik används tekniken inom spelteori, statistik och sannolikhetsberäkning för att lösa optimeringsproblem.
Inom ingenjörsvetenskap används dynamisk programmering för resursfördelning, schemaläggning, tillverkning, kommunikation och kontrollsystem.
Det finns flera fördelar med att använda dynamisk programmering:
- Effektivitet: Genom att undvika upprepad beräkning av samma delproblem, kan dynamisk programmering vara mer effektiv än andra optimeringsmetoder.
- Hantering av stora problem: Den är särskilt lämplig för stora optimeringsproblem, som skulle vara omöjliga att lösa med andra metoder. Detta tack vare att den reducerar problemens komplexitet genom att dela upp dem.
- Optimala lösningar: Dynamisk programmering kan hitta de bästa lösningarna, förutsatt att delproblemen och målen är tydligt definierade.
- Enkelhet: Metoden är ofta enkel att implementera och förstå, särskilt om problemet kan definieras i en specifik ordning.
- Skalbarhet: Dynamisk programmering är lätt att anpassa till mer komplexa problem genom att lägga till nya delproblem och anpassa problemets mål.
Dynamisk programmering är därmed ett kraftfullt verktyg för att säkerställa effektiva lösningar på optimeringsproblem.
Metoder inom dynamisk programmering
Dynamisk programmering använder huvudsakligen två olika metoder för att lösa optimeringsproblem: top-down-metoden och bottom-up-metoden.
Top-down-metoden
Denna metod är även känd som memoization. Memoization är en optimeringsteknik som förbättrar hastigheten i datorprogram genom att lagra resultaten av funktionsanrop i en cache, vilket gör det möjligt att snabbt återanvända tidigare resultat istället för att beräkna dem på nytt.
Top-down-metoden använder rekursion och cachning. Rekursion innebär att en funktion anropar sig själv med enklare varianter av problemet som argument. Rekursion hjälper till att bryta ner det stora problemet i mindre delproblem.
När ett delproblem har lösts, sparas dess resultat i cachen, så att det kan användas nästa gång ett liknande delproblem dyker upp. Top-down-metoden är enkel att förstå och implementera, och ett delproblem behöver bara lösas en gång. En nackdel är dock att rekursion kan ta upp mycket minne och leda till stack overflow-fel.
Bottom-up-metoden
Bottom-up-metoden, också känd som tabulering, undviker rekursion genom att använda iteration, vilket gör att stack overflow-fel undviks.
Denna metod innebär att man delar upp ett stort problem i mindre delproblem, och lösningarna på dessa delproblem används sedan för att bygga upp lösningen på det större problemet.
Delproblemen löses från det minsta till det största, och deras resultat lagras i en matris eller tabell, därav namnet tabulering.
De lagrade resultaten används för att lösa större problem som är beroende av delproblemen. Den slutgiltiga lösningen på det ursprungliga problemet fås genom att lösa det största delproblemet med hjälp av de tidigare beräknade värdena.
Denna metod är effektiv både i termer av minnesanvändning och tid, eftersom rekursion elimineras.
Exempel på problem som kan lösas med dynamisk programmering
Här följer några exempel på programmeringsproblem som kan lösas med dynamisk programmering:
#1. Ryggsäcksproblemet
Ryggsäcksproblemet går ut på att välja föremål med olika värden som ska packas i en ryggsäck med begränsad kapacitet. Målet är att maximera det totala värdet av de föremål som väljs, utan att överstiga ryggsäckens kapacitet.
Ett exempel på detta ges nedan:
Tänk dig att du ska vandra och har en ryggsäck som rymmer 15 kilo. Du har en lista över föremål, tillsammans med deras värden och vikter, som du kan ta med:
| Föremål | Värde | Vikt (kg) |
| Tält | 200 | 3 |
| Sovsäck | 150 | 2 |
| Spis | 50 | 1 |
| Mat | 100 | 2 |
| Vattenflaska | 100 | 0.5 |
| Första hjälpen-kit | 25 | 1 |
Uppgiften är att välja en delmängd av föremålen så att det totala värdet maximeras, samtidigt som den totala vikten är högst 15 kg.
Ryggsäcksproblemet har praktiska tillämpningar inom t.ex. finans där man väljer värdepapper för att maximera vinsten och minimera risker, samt i produktionsprocesser där man vill minimera materialspill.
#2. Schemaläggningsproblem
Ett schemaläggningsproblem är ett optimeringsproblem där man ska fördela uppgifter optimalt till en given uppsättning resurser. Resurserna kan vara maskiner, personal eller andra verktyg som behövs för att slutföra uppgifterna.
Ett exempel på detta ges nedan:
Tänk dig att du är projektledare och ska schemalägga ett antal uppgifter som ska utföras av ett team. Varje uppgift har en starttid, en sluttid och en lista över anställda som är kvalificerade att utföra den.
| Uppgift | Starttid | Sluttid | Kvalificerade medarbetare |
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
Uppgiften är att tilldela varje uppgift till en anställd på ett sätt som minimerar den totala tiden för projektet.
Schemaläggningsproblem är vanligt inom tillverkningsindustrin, där man optimerar resursfördelningen av maskiner, material och personal. Det kan också handla om att optimera användningen av personal och resurser inom hälsovården. Andra områden där schemaläggningsproblem förekommer är projektledning, logistik och utbildning.
#3. Handelsresandeproblemet
Detta är ett av de mest välstuderade optimeringsproblemen som kan lösas med dynamisk programmering.
Handelsresandeproblemet ger en lista över städer och avståndet mellan varje par av städer. Målet är att hitta den kortaste vägen som besöker varje stad exakt en gång och sedan återvänder till utgångsstaden.
Ett exempel på handelsresandeproblemet:
Tänk dig att du är en säljare som måste besöka en uppsättning städer så snabbt som möjligt. Du har en lista över städerna och avståndet mellan varje par av städer:
| Stad | A | B | C | D | E |
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
Handelsresandeproblemet är relevant inom t.ex. turism där man planerar resvägar, logistik för att optimera godstransporter, och försäljning där man vill planera effektiva resrutter.
Dynamisk programmering har uppenbarligen många praktiska användningsområden, vilket gör det viktigt att lära sig mer om det.
Här följer några resurser för att förbättra dina kunskaper om dynamisk programmering.
Resurser
”Dynamic Programming” av Richard Bellman
”Dynamic Programming” är en bok skriven av Richard Bellman, som introducerade och utvecklade dynamisk programmering.
Boken är skriven på ett lättfattligt sätt som kräver grundläggande kunskaper i matematik och kalkyl. Bellman introducerar den matematiska teorin om beslutsprocesser i flera steg, som är grundläggande för dynamisk programmering.
Boken utforskar sedan utmaningarna i produktionsprocesser i flera steg, existens- och unikhetsteorem samt den optimala lagerhanteringsformeln.
Bellman använder exempel från områden som logistik, schemaläggningsteori, kommunikationsteori, matematisk ekonomi och styrprocesser för att visa hur dynamisk programmering kan användas för att lösa dessa komplexa problem.
Boken finns tillgänglig som Kindle-version, inbunden och pocketbok.
Masterkurs i dynamiska programmeringsalgoritmer
Denna masterkurs i dynamiska programmeringsalgoritmer på Udemy erbjuds av Apaar Kamal, mjukvaruingenjör på Google, och Prateek Narang, som också har arbetat på Google.
Kursen är optimerad för att hjälpa studenter att lyckas i programmeringstävlingar, där dynamisk programmering ofta krävs.
Utöver tävlingsprogrammering är kursen också lämplig för programmerare som vill fördjupa sina kunskaper om algoritmer och för de som förbereder sig för programmeringsintervjuer och online-kodningstester.
Kursen är över 40 timmar lång och behandlar dynamisk programmering på djupet. Den börjar med en repetition av grundläggande koncept som rekursion och backtracking.
Kursen tar sedan upp dynamisk programmering inom spelteori, stränghantering, träd och grafer, matrisexponentiering, bitmasker, kombinatorik och delsekvenser, partitioneringsproblem och flerdimensionell dynamisk programmering, bland mycket annat.
”Competitive Programming Essentials, Master Algorithms”
Udemy erbjuder även kursen ”Competitive Programming Essentials” av Prateek Narang och Amal Kamaar. Denna kurs täcker dynamisk programmering, matematik, talteori och avancerade datastrukturer på ett sätt som är användbart och relevant för tävlingsprogrammerare.
Kursen ger en repetition av datastrukturer och algoritmer innan den går in på mer komplexa algoritmer och tekniker som är användbara i tävlingsprogrammering.
Kursen täcker dynamisk programmering, matematik, spelteori, mönstermatchning, bitmaskning och en rad avancerade algoritmer som används i programmeringstävlingar.
Udemy-kursen är uppdelad i 10 moduler och 42 sektioner och ger många övningsuppgifter efter varje sektion. Denna populära kurs är ett måste för alla som är intresserade av tävlingsprogrammering.
Slutord
Dynamisk programmering är en viktig färdighet för alla programmerare, då den förbättrar problemlösningsförmågan i praktiska situationer. Programmerare bör därför överväga att ta del av de föreslagna resurserna för att lägga till detta användbara verktyg till sina färdigheter.
För vidare läsning rekommenderar vi att undersöka vilka programmeringsspråk som används inom datavetenskap.