Wat is dynamisch programmeren?

Dynamische programmering beschrijft bij het verwijzen naar het gebied van informatica een groep vergelijkbare computeralgoritmen die bedoeld zijn om complexe problemen op te lossen door het probleem op te splitsen in sets van kleinere problemen.Dynamische programmering is voor het eerst gemaakt door Richard Bellman in de jaren 1950 en werkt met problemen die overlappende subproblemen of optimale substructuren zijn.Om te begrijpen hoe dynamische programmering werkt, het is het beste om het concept achter deze twee termen te begrijpen.

Overlappende subproblemen beschrijven gecompliceerde vergelijkingen die, wanneer ze worden opgesplitst in kleinere sets vergelijkingen, delen van de kleinere vergelijkingen meer dan eens hergebruiken om een antwoord te bereiken.Een wiskundige vergelijking die wordt verteld om alle mogelijke resultaten te berekenen met behulp van een set getallen kan bijvoorbeeld meerdere keren hetzelfde resultaat berekenen terwijl het slechts één keer andere resultaten berekent.Dynamische programmering zou dit probleem vertellen dat na het berekenen van het resultaat de eerste keer dat het resultaat moet opslaan en het antwoord later op de vergelijking zou moeten aansluiten in plaats van het opnieuw te berekenen.Bij het omgaan met lange complexe processen en vergelijkingen bespaart dit de tijd en creëert dit een snellere oplossing met veel minder stappen.

Optimale substructuren creëren een oplossing door het beste antwoord op alle subprobleem te vinden en vervolgens het beste algemene antwoord te creëren.Na het opsplitsen van een complex probleem in kleinere problemen, gebruikt de computer vervolgens een wiskundig systeem om te bepalen wat het beste antwoord voor elk probleem is.Het berekent het antwoord op het oorspronkelijke probleem van de kleinere antwoorden.Er bestaan gebreken met dit proces.Hoewel het de oplossing geeft die het beste wiskundig werkt, kan het al dan niet de beste oplossing zijn in het echte leven, afhankelijk van het type probleem en hoe het zich verhoudt tot de echte wereld.

Tijdens een van deze bewerkingen, het dynamische programmeringAlgoritme probeert het kortste pad naar de oplossing te vinden.Het kan een van de twee benaderingen nodig hebben om dit te doen.De top-downbenadering breekt de vergelijking op in kleinere vergelijkingen en hergebruikt de antwoorden voor deze vergelijkingen wanneer dat nodig is.De bottom-up benadering probeert de kleinste wiskundige waarde op te lossen na het afbreken van de vergelijking en werkt zich vervolgens omhoog naar de grootste vanaf daar.Beide benaderingen besparen tijd, maar dynamisch programmeren werkt alleen wanneer het oorspronkelijke probleem kan afbreken in kleinere vergelijkingen die op een gegeven moment worden hergebruikt om de vergelijking op te lossen.