Hva er dynamisk programmering?

Dynamisk programmering beskriver en gruppe lignende datamaskinalgoritmer beregnet på å løse komplekse problemer ved å dele problemet ned i sett med mindre problemer når det refereres til datavitenskapens felt. Først opprettet av Richard Bellman på 1950-tallet, fungerer dynamisk programmering med problemer som enten er overlappende delproblemer eller optimale understrukturer. For å forstå hvordan dynamisk programmering fungerer, er det best å forstå konseptet bak disse to begrepene.

Overlappende delproblemer beskriver kompliserte ligninger som, når de blir delt opp i mindre sett med ligninger, gjenbruker deler av de mindre likningene mer enn en gang for å komme til et svar. For eksempel kan en matematisk ligning som blir bedt om å beregne alle mulige resultater ved bruk av et sett med tall, beregne det samme resultatet flere ganger mens du bare beregner andre resultater en gang. Dynamisk programmering vil fortelle dette problemet at etter beregning av resultatet første gang skulle det lagre dette resultatet og koble svaret til ligningen senere i stedet for å beregne det igjen. Når du arbeider med lange komplekse prosesser og ligninger, sparer dette tid og skaper en raskere løsning ved å bruke langt færre trinn.

Optimale understrukturer skaper en løsning ved å finne det beste svaret på alle delproblemer og deretter lage det beste samlede svaret. Etter å ha delt opp et komplekst problem i mindre problemer, bruker datamaskinen deretter et matematisk system for å finne ut hva som er det beste svaret for hvert problem. Den beregner svaret på det opprinnelige problemet ut fra de mindre svarene. Det eksisterer mangler ved denne prosessen. Selv om det gir den løsningen som fungerer best matematisk, er det kanskje ikke den beste løsningen i det virkelige liv, avhengig av type problem og hvordan det forholder seg til den virkelige verden.

Under en av disse operasjonene prøver den dynamiske programmeringsalgoritmen å finne den korteste veien til løsningen. Det kan ta en av to tilnærminger for å gjøre dette. Top-down tilnærmingen bryter ligningen ned i mindre ligninger og gjenbruker svarene for disse ligningene når det er nødvendig. Bottom-up-tilnærmingen prøver å løse den minste matematiske verdien etter å ha brutt ligningen ned og deretter jobber seg opp mot den største derfra. Begge tilnærminger sparer tid, men dynamisk programmering fungerer bare når det opprinnelige problemet kan brytes ned i mindre ligninger som på et tidspunkt blir gjenbrukt for å løse ligningen.