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, is het het beste om het concept achter deze twee termen te begrijpen.

Overlappende subproblemen beschrijven gecompliceerde vergelijkingen die, wanneer ze worden onderverdeeld in kleinere sets vergelijkingen, delen van de kleinere vergelijkingen meer dan eenmaal 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 andere resultaten slechts één keer worden berekend. Dynamische programmering zou dit probleem vertellen dat na het berekenen van het resultaat de eerste keer dat het resultaat moet opslaan en het antwoord moet aansluiten op deVergelijking later in plaats van het opnieuw te berekenen. Bij het omgaan met lange complexe processen en vergelijkingen bespaart dit tijd en creëert dit 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 maken. 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 probeert het dynamische programmeeralgoritme het kortste pad naar de oplossing te vinden. Het kan er een vanTwee benaderingen 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.