Hva er dynamisk programmering?

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

Overlappende delproblemer beskriver kompliserte ligninger som, når de blir brutt ned i mindre sett med ligninger, gjenbruker deler av de mindre ligningene mer enn en gang for å nå et svar.For eksempel kan en matematisk ligning som er bedt om å beregne alle mulige resultater ved bruk av et sett med tall, beregne det samme resultatet flere ganger mens du beregner andre resultater bare en gang.Dynamisk programmering vil fortelle dette problemet at etter beregning av resultatet første gang det skal lagre resultatet og koble svaret til ligningen senere i stedet for å beregne det igjen.Etter å ha delt ut et komplekst problem i mindre problemer, bruker datamaskinen deretter et matematisk system for å bestemme hva det beste svaret for hvert problem er.Det beregner svaret på det opprinnelige problemet fra de mindre svarene.Det eksisterer mangler med denne prosessen.Selv om det gir løsningen som fungerer best matematisk, kan det hende at det ikke er den beste løsningen i det virkelige liv, avhengig av type problem og hvordan det forholder seg til den virkelige verden.

I løpet av noen av disse operasjonene, den dynamiske programmeringenAlgoritme prøver å 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 jobber seg deretter opp mot den største derfra.Begge tilnærminger sparer tid, men dynamisk programmering fungerer bare når det opprinnelige problemet kan bryte ned i mindre ligninger som på et tidspunkt blir gjenbrukt for å løse ligningen.