Wat is dynamisch programmeren?
Dynamisch programmeren, wanneer het verwijst naar het gebied van informatica, beschrijft een groep vergelijkbare computeralgoritmen die bedoeld zijn om complexe problemen op te lossen door het probleem op te splitsen in sets van kleinere problemen. Voor het eerst gemaakt door Richard Bellman in de jaren 1950, werkt dynamisch programmeren met problemen die overlappende subproblemen zijn of optimale substructuren. Om te begrijpen hoe dynamisch programmeren werkt, is het het beste om het concept achter deze twee termen te begrijpen.
Overlappende subproblemen beschrijven gecompliceerde vergelijkingen die, wanneer ze worden opgesplitst in kleinere reeksen 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 reeks getallen, kan bijvoorbeeld hetzelfde resultaat meerdere keren berekenen, terwijl andere resultaten slechts één keer worden berekend. Dynamisch programmeren zou dit probleem vertellen dat na het berekenen van het resultaat de eerste keer dat het dat resultaat moet opslaan en het antwoord later in de vergelijking moet stoppen in plaats van het opnieuw te berekenen. Wanneer het gaat om lange complexe processen en vergelijkingen, bespaart dit tijd en ontstaat een snellere oplossing met veel minder stappen.
Optimale substructuren creëren een oplossing door het beste antwoord op alle subproblemen te vinden en vervolgens het beste algemene antwoord te creëren. Na een complex probleem op te splitsen 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 uit de kleinere antwoorden. Er bestaan fouten in dit proces. Hoewel het de oplossing geeft die wiskundig het beste werkt, is het misschien wel of niet de beste oplossing in het echte leven, afhankelijk van het type probleem en hoe het zich verhoudt tot de echte wereld.
Tijdens elk van deze bewerkingen probeert het dynamische programmeeralgoritme het kortste pad naar de oplossing te vinden. Hiervoor kan een van de twee benaderingen nodig zijn. De top-down benadering splitst de vergelijking op in kleinere vergelijkingen en hergebruikt de antwoorden voor deze vergelijkingen indien nodig. De bottom-up benadering probeert de kleinste wiskundige waarde op te lossen na het opsplitsen van de vergelijking en werkt zich vervolgens vanaf daar omhoog naar de grootste. Beide benaderingen besparen tijd, maar dynamisch programmeren werkt alleen wanneer het oorspronkelijke probleem kan worden opgesplitst in kleinere vergelijkingen die op een gegeven moment opnieuw worden gebruikt om de vergelijking op te lossen.