Dynamisk programmering

Detta är en  metod att undvika att samma arbete utförs fler gånger.

Definition (informell)

Dynamisk programmering består av två olika moment:
  1. Ett vanligt problem med rekursiva algoritmer är att samma beräkningar görs i flera av de rekursiva anropen. Detta kan undvikas genom att den rekursiva funktionen sparar delresultaten i en tabell. Innan den utför en beräkning kollar den om resultatet redan finns i tabellen. Detta är den stora prestandavinsten som dynamisk programmering ger.
  2. Exekveringstiden kan minskas ytterligare om vi bestämmer i vilken ordning algoritmen behöver de olika delresultaten. I stället för rekursiva anrop kan algoritmen då implementeras som en loop som börjar med basfallet och sedan beräknar delresultaten i den ordning de behövs. På det viset slipper vi den tid det tar att initiera tabellen och att kolla om resultaten redan finns. Vi slipper också tiden för de rekursiva funktionsanropen.

Ett typiskt exempel

Ett enkelt och typiskt exempel på en algoritm som kan förbättras med hjälp av dynamisk programmering är Fibonaccis tal. Fibonaccis tal ges av ekvationen F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. En enkel och rättfram lösning kommer här, Fibonacci.c . Denna lösning liknar de algoritmer vi skrev med hjälp av söndra och härska. Det är dock ingen bra implementation av söndra och härska eftersom de två delproblemen inte är oberoende. Till exempel kommer både beräkningen av F(n-1) och av F(n-2) att leda till att F(n-3) beräknas, se figur 11.1 på sid 172 i kompendiet. Exekveringstiden för algoritmen är T(n) = T(n-1) + T(n-2) + 1. 1:an kommer av den instans av funktionen som gör de två rekursiva anropen. Algoritmen är inte användbar för särskilt stora n, till exempel leder beräkningen av F(35) till 29860703 anrop.

Här finns utrymme för stora förbättringar med hjälp av dynamisk programmering. Vi börjar med moment 1, spara beräknade resultat i en tabell, FibonacciDyn1.c . Nu krävs det bara 69 anrop för att beräkna F(35), ingen dålig förbättring. Detta illustreras av figur 11.2 på sid 172. Av figuren framgår att det nu krävs 2n - 1 anrop för att beräkna F(n), dvs O(T(n)) = n.

En ytterligare förbättring kan åstadkommas med moment 2. Vi måste först bestämma i vilken ordning algoritmen behöver de olika delresultaten, detta kallas resultatens topologiska ordning . I detta fall beror varje resultat av resultat för mindre n. Den topologisa ordningen är alltså F(0), F(1), F(2) ... F(n). Vi kan nu skriva om algoritmen som följer, FibonacciDyn2.c . O(T(n)) är visserligen fortfarande n men vi slapp initiera arrayen (raden memset(arr, 0, noOfElements); är borta), vi slapp kolla om f[n] = 0, vi slapp tiden för funktionsanropen vid rekursionen och de 69 funktionsanropen för att beräkna F(35) motsvaras av 34 varv i loopen. Mer generellt krävs nu n - 1 varv i loopen i stället för 2n - 1 exekveringar av den rekursiva funktionen i FibonacciDyn1.c. Det beror på att det nu inte krävs rekursiva anrop för att hitta de tidigare beräknade resultaten.

När ska dynamisk programmering användas?

Moment ett kan alltid användas när en rekursiv funktion utför samma arbete i flera olika rekursiva anrop. Det kan , som i exemplet ovan, ofta leda till avsevärda prestandaförbättringar. Detta är egentligen inget annat än rekursionens fjärde regel (som vi nämnde redan på första föreläsningen): Lös inte samma delproblem i flera olika rekursiva anrop.

Moment två kan användas även om moment ett inte är tillämpligt, dvs i rekursiva funktioner där samma arbete aldrig utförs i oberoende rekursiva  anrop. Ett exempel är sorteringsalgoritmen mergesort, se sid 163 och avsnittet om söndra och härska . Här utförs inget överlappande arbete i olika rekursiva anrop. Algoritmen kan ändå bli snabbare med hjälp av dynamisk programmering på följande sätt. Skapa först n/2 sekvenser med vardera två sorterade element (basfallet i mergesort). Loopa därefter log(n) varv och samsortera på varje varv sekvenserna parvis till dubbelt så stora sekvenser. Det blir n element som ska sorteras på varje varv. På detta sätt slipper vi looparna som delar upp sekvensen i två delsekvenser inför de rekursiva anropen. Vi slipper även den tid det tar att utföra de rekursiva anropen. O(T(n)) är dock fortfarande nlog(n) eftersom det krävs log(n) varv i en loop som behandlar n element på varje varv.      

Fler exempel

Här kommer ytterligare några problem som löses med hjälp av dynamisk programmering.  

Myntväxling

Detta problem såg vi första gången i avsnittet om glupska algoritmer, på sid 152 i kompendiet. Det handlar om att växla ett visst belopp i de valörer som finns tillgängliga i en valuta. Den glupska algoritmen tog alltid största möjliga valör tills det sökta beloppet var nått. Detta var en snabb algoritm eftersom den inte jämförde olika lösningar, tyvärr gav den inte alltid den bästa lösningen (dvs den som krävde minst antal mynt/sedlar).

En alternativ algoritm som är långsammare men alltid ger den bästa lösningen beskrivs överst på sid 173. Den är av typen söndra och härska. Att växla beloppet b i minst antal mynt delas upp i delproblemen att oberoende av varandra växla b-1 och 1, b-2 och 2, b-3 och 3 ... b-b/2 och b/2. Resultatet är det minsta antal mynt som krävs för något av dessa par av växlingar. Här kommer en implementation av denna algoritm, ChangeDoc.c . Denna algoritm är tyvärr oanvändbart långsam eftersom väldigt många beräkningar utförs flera gånger. Till exempel leder beräkningen av b-1 till att både b-2 och 1 beräknas ytterligare en gång. En analys av programmet ger att T(n) >= T(1) + T(2) + ... + T(n-1) vilket innebär att O(T(n)) = 2n-1. Redan beräkningen av beloppet 27 leder till 15227045 anrop.

Detta kan förbättras avsevärt med hjälp av första momentet av dynamisk programmering, se algoritmen nederst på sid 173. Här kommer ett sådant program, ChangeDyn1.c . Detta ger en avsevärd förbättring, det krävs nu bara 331 anrop för att växla beloppet 27. Loopen där b-1 och 1 ... b-b/2 och b/2 ska växlas leder nu endast till ett rekursiva anrop i en nivå eftersom antalet mynt som krävs för att växla alla belopp lägre än det sökta redan är beräknade. Detta innebär att O(T(n)) är O(T(n-1) + n).

Ytterligare en förbättring kan åstadkommas med det andra momentet av dynamisk programmering. Den topologiska ordningen för delresultaten är i stigande ordning, dvs växla 1, 2, 3 ... b. Detta leder till följande program, ChangeDyn2.c . Det blev en ytterligare förbättre, nu krävs det bara 216  varv i loopen för att växla beloppet 27. O(T(n)) är nu O(antal valörer * n) = n. Anledningen till förbättringen är att det nu inte krävs ett rekursivt anrop för att hitta ett tidigare beräknade resultatet.

Knapsack II

Detta problem går ut på att fylla en ryggsäck av volymen c med så värdefulla objekt som möjligt. Det finns n olika typer av objekt, bi, 1 <= i <= n. Objekten har volymen v i och värdet wi. Det finns ett obegränsat antal av varje typ av objekt och det går inte att dela objekten. En lösning med hjälp av dynamisk programmering blir mycket snarlik ChangeDyn2.c ovan. För alla möjliga storlekar på ryggsäcken får vi gå igenom alla möjliga objekt och undersöka om ryggsäckens värde ökar i fall ett visst objekt läggs i. Detta leder till en loop från 1 till n inuti en loop från 1 till c. O(T(n)) blir alltså, precis som för ChangeDyn2.c, O(cn) = n.