Hvad er dynamisk programmering?

Dynamisk programmering, når man henviser til området datalogi, beskriver en gruppe af lignende computeralgoritmer, der er beregnet til at løse komplekse problemer ved at nedbryde problemet i sæt af mindre problemer.Først oprettet af Richard Bellman i 1950'erne fungerer dynamisk programmering med problemer, der enten overlapper underproblemer eller optimale understrukturer.For at forstå, hvordan dynamisk programmering fungerer, beskriver det bedst at forstå konceptet bag disse to udtryk.

Overlappende underproblemer beskriver komplicerede ligninger, der, når de er opdelt i mindre sæt ligninger, genbruger dele af de mindre ligninger mere end én gang for at nå et svar.For eksempel kan en matematisk ligning, der fortælles om at beregne alle mulige resultater ved hjælp af et sæt tal, beregne det samme resultat adskillige gange, mens de beregner andre resultater kun én gang.Dynamisk programmering ville fortælle dette problem, at efter beregning af resultatet første gang det skulle gemme dette resultat og tilslutte svaret i ligningen senere i stedet for at beregne det igen.Når man beskæftiger sig med lange komplekse processer og ligninger, sparer dette tid og skaber en hurtigere løsning ved hjælp af langt færre trin.

Optimale understrukturer skaber en løsning ved at finde det bedste svar på alle underproblemer og derefter skabe det bedste samlede svar.Efter at have nedbragt et komplekst problem i mindre problemer, bruger computeren derefter et matematisk system til at bestemme, hvad det bedste svar for hvert problem er.Det beregner svaret på det originale problem fra de mindre svar.Der findes mangler med denne proces.Selvom den giver den løsning, der fungerer den bedste matematisk, er det måske eller ikke den bedste løsning i det virkelige liv, afhængigt af typen af problemet og hvordan den relaterer til den virkelige verden.

Under nogen af disse operationerAlgoritme forsøger at finde den korteste sti til løsningen.Det kan tage en af to tilgange til at gøre dette.Top-down-tilgangen bryder ligningen ned i mindre ligninger og genbruger svarene på disse ligninger, når det er nødvendigt.Bottom-up-tilgangen forsøger at løse den mindste matematiske værdi efter nedbrydning af ligningen og derefter arbejder sig op mod den største derfra.Begge fremgangsmåder sparer tid, men dynamisk programmering fungerer kun, når det originale problem kan nedbrydes i mindre ligninger, som på et tidspunkt genbruges for at løse ligningen.