Vad är dynamisk programmering?

Dynamisk programmering, när man hänvisar till datavetenskapens fält, beskriver en grupp liknande datoralgoritmer avsedda att lösa komplexa problem genom att dela upp problemet i uppsättningar av mindre problem. Först skapad av Richard Bellman på 1950-talet, dynamisk programmering fungerar med problem som antingen överlappar delproblem eller optimala understrukturer. För att förstå hur dynamisk programmering fungerar är det bäst att förstå konceptet bakom dessa två termer.

Överlappande delproblem beskriver komplicerade ekvationer som, när de delas upp i mindre uppsättningar ekvationer, återanvänder delar av de mindre ekvationerna mer än en gång för att nå ett svar. Till exempel kan en matematisk ekvation som berättas för att beräkna alla möjliga resultat med hjälp av en uppsättning siffror beräkna samma resultat flera gånger medan man beräknar andra resultat bara en gång. Dynamisk programmering skulle säga till detta problem att efter beräkning av resultatet första gången skulle det spara resultatet och ansluta svaret i ekvationen senare istället för att beräkna det igen. När du hanterar långa komplexa processer och ekvationer sparar detta tid och skapar en snabbare lösning med mycket färre steg.

Optimala understrukturer skapar en lösning genom att hitta det bästa svaret på alla delproblem och sedan skapa det bästa övergripande svaret. Efter att ha uppdelat ett komplext problem i mindre problem använder datorn sedan ett matematiskt system för att bestämma vad som är det bästa svaret för varje problem. Det beräknar svaret på det ursprungliga problemet från de mindre svaren. Det finns brister i denna process. Även om det ger den lösning som fungerar bäst matematiskt, kan det vara eller inte vara den bästa lösningen i verkliga livet, beroende på typ av problem och hur det förhåller sig till den verkliga världen.

Under någon av dessa operationer försöker den dynamiska programmeringsalgoritmen att hitta den kortaste vägen till lösningen. Det kan ta en av två metoder för att göra detta. Uppifrån och ner-metoden bryter ekvationen i mindre ekvationer och återanvänder svaren för dessa ekvationer vid behov. Nedifrån-upp-metoden försöker lösa det minsta matematiska värdet efter att ha brytat ekvationen och arbetar sedan upp mot det största därifrån. Båda metoderna sparar tid, men dynamisk programmering fungerar bara när det ursprungliga problemet kan delas upp i mindre ekvationer som vid någon tidpunkt återanvänds för att lösa ekvationen.