Een inleiding tot algoritmen: dynamisch programmeren

Stel dat u een berekening uitvoert met een geschikte reeks invoer. Er wordt bij elke instantie enige berekening uitgevoerd om een ​​resultaat af te leiden. U weet niet dat u dezelfde uitvoer was tegengekomen toen u dezelfde invoer had opgegeven . Het is dus alsof u een resultaat opnieuw berekent dat eerder werd bereikt door specifieke invoer voor de respectievelijke uitvoer.

Maar wat is hier het probleem? Het punt is dat uw kostbare tijd wordt verspild. U kunt het probleem hier eenvoudig oplossen door records bij te houden die eerder berekende resultaten in kaart brengen. Zoals het gebruik van de juiste datastructuur. U kunt bijvoorbeeld invoer opslaan als sleutel en uitvoer als waarde (onderdeel van mapping).

Degenen die zich het verleden niet kunnen herinneren, zijn veroordeeld het te herhalen. ~ Dynamisch programmeren

Door nu het probleem te analyseren, slaat u de invoer op als deze nieuw is (of niet in de datastructuur) met zijn respectieve uitvoer. Controleer anders die invoersleutel en haal de resulterende uitvoer uit zijn waarde. Op die manier kunt u direct het resultaat krijgen als u wat berekeningen uitvoert en controleert of die invoer in die gegevensstructuur bestond. We kunnen deze benadering dus relateren aan dynamische programmeertechnieken.

Duiken in dynamisch programmeren

In een notendop kunnen we zeggen dat dynamisch programmeren in de eerste plaats wordt gebruikt om problemen te optimaliseren, waarbij we de "beste" manier willen vinden om iets te doen.

Een bepaald scenario is alsof er terugkerende subproblemen zijn die op hun beurt hun eigen kleinere subproblemen hebben. In plaats van te proberen deze opnieuw opduikende subproblemen steeds weer op te lossen, stelt dynamisch programmeren voor om elk van de kleinere subproblemen slechts één keer op te lossen. Vervolgens legt u de resultaten vast in een tabel waaruit een oplossing voor het oorspronkelijke probleem kan worden verkregen.

De Fibonacci-getallen 0,1,1,2,3,5,8,13,…hebben bijvoorbeeld een eenvoudige beschrijving waarbij elke term is gerelateerd aan de twee termen ervoor. Als F(n)dit de ne term is van deze serie, dan hebben we F(n) = F(n-1) + F(n-2). Dit wordt een recursieve formule of een herhalingsrelatie genoemd. Er moeten eerdere termen zijn berekend om een ​​latere term te kunnen berekenen.

De meeste problemen met dynamisch programmeren kunnen in twee soorten worden onderverdeeld:

  1. Optimalisatieproblemen.
  2. Combinatorische problemen.

De optimalisatieproblemen verwachten dat u een haalbare oplossing kiest, zodat de waarde van de vereiste functie wordt geminimaliseerd of gemaximaliseerd. Combinatorische problemen verwachten dat je het aantal manieren bedenkt om iets te doen of de waarschijnlijkheid dat er iets gebeurt.

Een aanpak om op te lossen: top-down versus bottom-up

Er zijn de volgende twee verschillende manieren om het probleem op te lossen:

Top-down: je begint van bovenaf en lost het probleem op door het op te splitsen. Als u ziet dat het probleem al is opgelost, retourneert u gewoon het opgeslagen antwoord. Dit wordt Memoization genoemd.

Bottom-up: u begint direct met het oplossen van de kleinere subproblemen en gaat naar de top om de definitieve oplossing van dat ene grote probleem af te leiden. In dit proces wordt gegarandeerd dat de subproblemen zijn opgelost voordat het probleem wordt opgelost. Dit kan Tabulatie worden genoemd ( algoritme voor het vullen van tabellen ).

Met betrekking tot iteratie versus recursie, gebruikt bottom-up iteratie en gebruikt top-down recursie.

Hier is er een vergelijking tussen een naïeve benadering versus een DP-benadering. U kunt het verschil zien aan de tijdcomplexiteit van beide.

Memoization: niet vergeten

Jeff Erickson beschrijft in zijn aantekeningen voor Fibonacci-getallen:

De voor de hand liggende reden voor het gebrek aan snelheid van het recursieve algoritme is dat het steeds opnieuw dezelfde Fibonacci-getallen berekent.

We kunnen ons recursieve algoritme aanzienlijk versnellen door de resultaten van onze recursieve oproepen op te schrijven. Dan kunnen we ze opnieuw opzoeken als we ze later nodig hebben.

Memoization verwijst naar de techniek van het cachen en hergebruiken van eerder berekende resultaten.

Als je memoisatie gebruikt om het probleem op te lossen, doe je dat door een kaart bij te houden van reeds opgeloste deelproblemen (zoals we eerder hebben besproken over het in kaart brengen van sleutel en waarde). Je doet het " top-down " in de zin dat je eerst het "top" -probleem oplost (dat meestal terugkomt om de subproblemen op te lossen).

Pseudocode voor memoisatie :

Dus met recursie doen we dit met extra overheadgeheugen (dwz hier opzoeken) om resultaten op te slaan. Als er een waarde is opgeslagen in de zoekactie, retourneren we deze direct of voegen we deze toe aan de zoekactie voor die specifieke index.

Onthoud dat er een afweging is van extra overhead met betrekking tot de tabulatiemethode.

Als je echter meer visualisaties wilt voor memoisatie, raad ik je aan deze video te bekijken.

Tabellering: opvullen in tabelvorm

Maar als we eenmaal zien hoe de array (oplossing met memo) is gevuld, kunnen we de recursie vervangen door een eenvoudige lus die de array opzettelijk op volgorde vult, in plaats van te vertrouwen op de gecompliceerde recursie om het 'per ongeluk' voor ons te doen.

Tabellering doet het "van onderop" . Het is eenvoudiger, het berekent alle waarden. Het vereist minder overhead omdat het geen mapping hoeft te onderhouden en gegevens voor elke waarde in tabelvorm opslaat. Het kan ook onnodige waarden berekenen. Dit kan worden gebruikt als u alleen alle waarden voor uw probleem wilt berekenen.

Pseudocode voor tabellering:

Zoals je pseudocode (rechterkant) in een afbeelding kunt zien, doet het iteratie (dwz loopt door tot het einde van een array). Het begint simpelweg met fib (0), fib (1), fib (2),… Dus met de tabulatiebenadering kunnen we de noodzaak van recursie elimineren en simpelweg het resultaat retourneren door over elementen heen te lopen.

Terugkijken in de geschiedenis

Richard Bellman was de man achter dit concept. Hij bedacht dit toen hij halverwege de jaren vijftig voor RAND Corporation werkte. De reden dat hij deze naam 'dynamisch programmeren' koos, was om het wiskundige werk dat hij voor dit onderzoek deed te verbergen. Hij was bang dat zijn bazen zich tegen elke vorm van wiskundig onderzoek zouden verzetten of er een hekel aan zouden hebben.

Oké, dus het woord 'programmeren' is slechts een verwijzing om te verduidelijken dat dit een ouderwetse manier van plannen of plannen was, meestal door een tabel in te vullen (op een dynamische manier in plaats van op een lineaire manier) in de loop van de tijd in plaats van alles in een keer.

Afsluiten

Dat is het. Dit is deel 2 van de algoritme-serie die ik vorig jaar ben begonnen. In mijn vorige bericht hebben we besproken wat zoek- en sorteeralgoritmen zijn. Excuses dat ik dit niet in een kortere tijd kon leveren. Maar ik ben bereid om de komende maanden dingen sneller te maken.

Ik hoop dat je het leuk vond en ik zal binnenkort een derde in de serie toevoegen. Veel plezier met coderen!

Middelen:

Inleiding tot dynamisch programmeren 1 Tutorials & notities | Algoritmen | HackerEarth

De afbeelding hierboven zegt veel over Dynamic Programming. Dus herhaalt u de dingen waarvoor u al de… www.hackerearth.com Community - Competitief programmeren - Tutorials voor competitief programmeren - Dynamisch programmeren: van…

Gemeenschap - Competitief programmeren - Tutorials voor competitief programmeren - Dynamisch programmeren: van beginner tot gevorderd www.topcoder.com

//www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Speciale rekwisieten voor Jeff Erickson en zijn notities voor algoritme - //jeffe.cs.illinois.edu/