Vad är dynamisk programmering?

Dynamisk programmering, när man hänvisar till datavetenskapens område, beskriver en grupp liknande datoralgoritmer som är 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 fungerar dynamisk programmering med problem som antingen är överlappande 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 uppdelas i mindre uppsättningar av 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 är berättad om att beräkna alla möjliga resultat med hjälp av en uppsättning siffror beräkna samma resultat flera gånger under beräkningen av andra resultat endast en gång.Dynamisk programmering skulle berätta för detta problem att efter att ha beräknat resultatet första gången skulle det spara det resultatet och ansluta svaret till 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 delar upp ett komplext problem i mindre problem använder datorn sedan ett matematiskt system för att avgöra vad det bästa svaret för varje problem är.Det beräknar svaret på det ursprungliga problemet från de mindre svaren.Brister finns med denna process.Även om den ger den lösning som fungerar bäst matematiskt, kan den eller inte vara den bästa lösningen i verkligheten, beroende på typ av problem och hur den hänför sig till den verkliga världen.

Under någon av dessa operationer, den dynamiska programmeringenAlgoritm försöker hitta den kortaste vägen till lösningen.Det kan ta en av två tillvägagångssätt för att göra detta.Top-down-metoden delar upp ekvationen i mindre ekvationer och återanvänder svaren för dessa ekvationer vid behov.Bottom-up-metoden försöker lösa det minsta matematiska värdet efter att ha brutit ner ekvationen och sedan arbetar sig upp mot det största därifrån.Båda tillvägagångssätten sparar tid, men dynamisk programmering fungerar bara när det ursprungliga problemet kan bryta ner i mindre ekvationer som vid någon tidpunkt återanvänds för att lösa ekvationen.