DYNAMISCH PROGRAMMEREN: KENMERKEN, VOORBEELD, VOORDELEN, NADELEN - TECHNOLOGIE - 2026

De dynamische programmering is een modelalgoritme dat een complex probleem oplost door het op te splitsen in deelproblemen, waarbij de resultaten ervan worden opgeslagen om te voorkomen dat de resultaten opnieuw moeten worden berekend.

Dit schema wordt gebruikt wanneer u problemen heeft die kunnen worden onderverdeeld in vergelijkbare deelproblemen, zodat hun resultaten kunnen worden hergebruikt. Dit schema wordt grotendeels gebruikt voor optimalisatie.

Dynamisch programmeren. Subproblemen gesuperponeerd in de Fibonacci-reeks. Bron: Wikimedia commons, en: Gebruiker: Dcoatzee, opgespoord door Gebruiker: Stannered / Public domain

Voordat het beschikbare subprobleem wordt opgelost, zal het dynamische algoritme proberen de resultaten van de eerder opgeloste subproblemen te onderzoeken. De oplossingen voor de deelproblemen worden gecombineerd om tot de beste oplossing te komen.

In plaats van steeds hetzelfde subprobleem te berekenen, kunt u uw oplossing in een bepaald geheugen opslaan, wanneer u dit subprobleem voor het eerst tegenkomt. Als het weer verschijnt tijdens het oplossen van een ander subprobleem, wordt de oplossing die al in het geheugen is opgeslagen, gebruikt.

Dit is een geweldig idee om de geheugentijd te herstellen, waarbij het gebruik van extra ruimte de tijd kan verbeteren die nodig is om een ​​oplossing te vinden.

Kenmerken van dynamische programmering

De volgende essentiële kenmerken zijn waarmee u een probleem moet hebben voordat dynamisch programmeren kan worden toegepast:

Optimale onderbouw

Dit kenmerk drukt uit dat een optimalisatieprobleem kan worden opgelost door de optimale oplossingen van de secundaire problemen die het omvat, te combineren. Deze optimale onderstructuren worden beschreven door middel van recursie.

In een grafiek wordt bijvoorbeeld een optimale substructuur gepresenteerd in het kortste pad r dat van een hoekpunt s naar een hoekpunt t gaat:

Dat wil zeggen, in dit kortste pad r kan elk tussenliggend hoekpunt i worden genomen. Als r echt de kortste route is, dan kan deze worden opgedeeld in de subroutes r1 (van s naar i) en r2 (van i naar t), zodanig dat dit op hun beurt de kortste routes zijn tussen de corresponderende hoekpunten.

Om de kortste paden te vinden, kan de oplossing daarom gemakkelijk recursief worden geformuleerd, wat het Floyd-Warshall-algoritme doet.

Overlappende subproblemen

De subprobleemruimte moet klein zijn. Dat wil zeggen, elk recursief algoritme dat een probleem oplost, zal dezelfde subproblemen steeds opnieuw moeten oplossen, in plaats van nieuwe subproblemen te genereren.

Om bijvoorbeeld de Fibonacci-reeks te genereren, kunnen we deze recursieve formulering beschouwen: Fn = F (n - 1) + F (n - 2), met als basisscenario dat F1 = F2 = 1. Dan hebben we: F33 = F32 + F31 en F32 = F31 + F30.

Zoals je kunt zien, wordt F31 opgelost in de recursieve substructuren van zowel F33 als F32. Hoewel het totale aantal subproblemen erg klein is, zul je, als je een recursieve oplossing als deze toepast, dezelfde problemen steeds opnieuw oplossen.

Hiermee wordt rekening gehouden door dynamische programmering, dus het lost elk subprobleem slechts één keer op. Dit kan op twee manieren worden bereikt:

Top-down benadering

Als de oplossing voor een probleem recursief kan worden geformuleerd met behulp van de oplossing van zijn subproblemen, en als deze subproblemen elkaar overlappen, kunnen de oplossingen voor de subproblemen gemakkelijk worden onthouden of in een tabel worden opgeslagen.

Elke keer dat een nieuwe subprobleemoplossing wordt doorzocht, wordt de tabel gecontroleerd om te zien of deze eerder is opgelost. Als een oplossing is opgeslagen, wordt deze gebruikt in plaats van deze opnieuw te berekenen. Anders wordt het subprobleem opgelost en wordt de oplossing in de tabel opgeslagen.

Bottom-up benadering

Nadat de oplossing van een probleem recursief is geformuleerd in termen van zijn subproblemen, is het mogelijk om te proberen het probleem opwaarts te herformuleren: eerst zullen we proberen de subproblemen op te lossen en hun oplossingen gebruiken om tot oplossingen te komen voor de grotere subproblemen.

Dit gebeurt meestal ook in tabelvorm, waarbij iteratief oplossingen worden gegenereerd voor grotere en grotere deelproblemen door oplossingen te gebruiken voor de kleinere deelproblemen. Als de waarden van F31 en F30 bijvoorbeeld al bekend zijn, kan de waarde van F32 direct worden berekend.

Vergelijking met andere technieken

Een belangrijk kenmerk van een probleem dat kan worden opgelost door dynamisch programmeren, is dat het subproblemen moet overlappen. Dit is wat dynamisch programmeren onderscheidt van de verdeel en heers-techniek, waarbij het niet nodig is om de eenvoudigste waarden op te slaan.

Het is vergelijkbaar met recursie, omdat bij het berekenen van de basisgevallen de uiteindelijke waarde inductief kan worden bepaald. Deze bottom-up benadering werkt goed wanneer een nieuwe waarde alleen afhangt van eerder berekende waarden.

Voorbeeld

Minimale stappen om 1 te bereiken

Voor elk positief geheel getal "e" kan elk van de volgende drie stappen worden uitgevoerd.

- Trek 1 af van het getal. (e = e-1).

- Als het deelbaar is door 2, wordt het gedeeld door 2 (als e% 2 == 0, dan e = e / 2).

- Als het deelbaar is door 3, wordt het gedeeld door 3 (als e% 3 == 0, dan e = e / 3).

Op basis van de bovenstaande stappen moet het minimumaantal van deze stappen worden gevonden om e op 1 te brengen. Bijvoorbeeld:

- Als e = 1, resultaat: 0.

- Als e = 4, resultaat: 2 (4/2 = 2/2 = 1).

- Als e = 7, resultaat: 3 (7-1 = 6/3 = 2/2 = 1).

Focus

Men zou kunnen denken om altijd de stap te kiezen die n zo laag mogelijk maakt en zo door te gaan tot 1. Het is echter duidelijk dat deze strategie hier niet werkt.

Als e = 10, zijn de stappen bijvoorbeeld: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 stappen). De optimale vorm is echter: 10-1 = 9/3 = 3/3 = 1 (3 stappen). Daarom moeten alle mogelijke stappen die kunnen worden uitgevoerd voor elke gevonden waarde van n worden geprobeerd, waarbij het minimum aantal van deze mogelijkheden wordt gekozen.

Het begint allemaal met recursie: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} als e> 1, met als basisscenario: F (1) = 0. Met de herhalingsvergelijking kunt u beginnen met het coderen van de recursie.

Het is echter te zien dat het overlappende subproblemen heeft. Bovendien hangt de optimale oplossing voor een bepaalde input af van de optimale oplossing van zijn deelproblemen.

Zoals bij het onthouden, waar de oplossingen van de subproblemen die zijn opgelost, worden opgeslagen voor later gebruik. Of zoals bij dynamisch programmeren, begin je onderaan en werk je omhoog naar de gegeven e. Dan beide codes:

Memorisatie

Dynamische bottom-up programmering

Voordeel

Een van de belangrijkste voordelen van het gebruik van dynamisch programmeren is dat het de verwerking versnelt, aangezien eerder berekende referenties worden gebruikt. Omdat het een recursieve programmeertechniek is, reduceert het het aantal regels code in het programma.

Vraatzuchtige algoritmen versus dynamische programmering

Hebzuchtige algoritmen lijken op dynamisch programmeren in die zin dat ze beide tools zijn voor optimalisatie. Het hebzuchtige algoritme zoekt echter bij elke lokale stap naar een optimale oplossing. Dat wil zeggen, het zoekt een hebzuchtige keuze in de hoop een wereldwijd optimum te vinden.

Daarom kunnen hebzuchtige algoritmen een aanname doen die er op dat moment optimaal uitziet, maar in de toekomst duur wordt en geen globaal optimaal garandeert.

Anderzijds vindt dynamisch programmeren de optimale oplossing voor de deelproblemen en maakt vervolgens een weloverwogen keuze door de resultaten van die deelproblemen te combineren om daadwerkelijk de meest optimale oplossing te vinden.

Nadelen

- Er is veel geheugen nodig om het berekende resultaat van elk subprobleem op te slaan, zonder te kunnen garanderen dat de opgeslagen waarde wel of niet wordt gebruikt.

- Vaak wordt de outputwaarde opgeslagen zonder ooit gebruikt te worden in de volgende subproblemen tijdens de uitvoering. Dit leidt tot onnodig geheugengebruik.

- Bij dynamisch programmeren worden functies recursief aangeroepen. Hierdoor blijft het stapelgeheugen constant toenemen.

Recursie versus dynamische programmering

Als u een beperkt geheugen heeft om uw code uit te voeren en de verwerkingssnelheid geen probleem is, kunt u recursie gebruiken. Als u bijvoorbeeld een mobiele applicatie ontwikkelt, is het geheugen zeer beperkt om de applicatie uit te voeren.

Als u wilt dat het programma sneller werkt en geen geheugenbeperkingen heeft, verdient het de voorkeur om dynamische programmering te gebruiken.

Toepassingen

Dynamisch programmeren is een effectieve methode om problemen op te lossen die anders buitengewoon moeilijk zouden lijken om binnen een redelijke tijd op te lossen.

Algoritmen op basis van het dynamische programmeerparadigma worden in veel wetenschapsgebieden gebruikt, waaronder veel voorbeelden in kunstmatige intelligentie, van het oplossen van problemen bij het plannen tot spraakherkenning.

Algoritmen gebaseerd op dynamische programmering

Dynamisch programmeren is behoorlijk effectief en werkt erg goed voor een breed scala aan problemen. Veel algoritmen kunnen worden gezien als hebzuchtige algoritme-applicaties, zoals:

- Fibonacci-nummerreeks.

- Torens van Hanoi.

- Alle paren van kortere routes door Floyd-Warshall.

- Probleem met rugzak.

- Projectplanning.

- De kortste weg door Dijkstra.

- Vluchtcontrole en robotica controle.

- Wiskundige optimalisatieproblemen.

- Timeshare: plan de taak om het CPU-gebruik te maximaliseren.

Fibonacci-nummerreeks

Fibonacci-nummers zijn de nummers die in de volgende volgorde worden gevonden: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, enz.

In wiskundige terminologie wordt de reeks Fn van Fibonacci-getallen gedefinieerd door de herhalingsformule: F (n) = F (n -1) + F (n -2), waarbij F (0) = 0 en F ( 1) = 1.

Top-down benadering

In dit voorbeeld wordt een zoekmatrix met alle beginwaarden geïnitialiseerd met -1. Wanneer de oplossing voor een deelprobleem nodig is, wordt eerst deze zoekmatrix doorzocht.

Als de berekende waarde aanwezig is, wordt die waarde geretourneerd. Anders wordt het resultaat berekend om te worden opgeslagen in de zoekmatrix, zodat het later opnieuw kan worden gebruikt.

Bottom-up benadering

In dit geval wordt voor dezelfde Fibonacci-reeks eerst f (0) berekend, daarna f (1), f (2), f (3), enzovoort. Zo worden de oplossingen van de deelproblemen van onderaf geconstrueerd.

Referenties

1. Vineet Choudhary (2020). Inleiding tot dynamisch programmeren. Developer Insider. Genomen van: developerinsider.co.
2. Alex Allain (2020). Dynamisch programmeren in C ++. C Programmeren. Genomen van: cprogramming.com.
3. Na Academie (2020). Idee van dynamische programmering. Genomen van: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamische programmering en recursie - Verschil, voordelen met voorbeeld. CSE-stapel. Genomen uit: csestack.org.
5. Code Chef (2020). Tutorial voor dynamisch programmeren. Genomen van: codechef.com.
6. Programiz (2020). Dynamisch programmeren. Genomen van: programiz.com.