algorithm
Toepassingen van dynamisch programmeren
Zoeken…
Invoering
Het basisidee achter dynamisch programmeren is het splitsen van een complex probleem in verschillende kleine en eenvoudige problemen die zich herhalen. Als u een eenvoudig subprobleem kunt identificeren dat herhaaldelijk wordt berekend, is de kans groot dat er een dynamische programmeerbenadering van het probleem bestaat.
Omdat dit onderwerp getiteld Toepassingen van dynamische programmering is , zal het zich meer richten op toepassingen in plaats van het proces van het creëren van dynamische programmeeralgoritmen.
Opmerkingen
Definities
Memoisatie - een optimalisatietechniek die voornamelijk wordt gebruikt om computerprogramma's te versnellen door de resultaten van dure functieaanroepen op te slaan en het resultaat in de cache te retourneren wanneer dezelfde invoer opnieuw optreedt.
Dynamische programmering - een methode om een complex probleem op te lossen door het op te splitsen in een verzameling eenvoudigere subproblemen, elk van die subproblemen slechts één keer op te lossen en hun oplossingen op te slaan.
Fibonacci-nummers
Fibonacci-getallen zijn een belangrijk onderwerp voor dynamisch programmeren, omdat de traditionele recursieve benadering veel herhaalde berekeningen maakt. In deze voorbeelden zal ik het basisscenario van f(0) = f(1) = 1 .
Hier is een voorbeeld van een recursieve boom voor fibonacci(4) , let op de herhaalde berekeningen: 
Niet-dynamische programmering O(2^n) Runtime Complexity, O(n) Stack complexity
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Dit is de meest intuïtieve manier om het probleem te schrijven. De stapelruimte is hoogstens O(n) terwijl u de eerste recursieve tak afdaalt en fibonacci(n-1) aanroept tot u het basisscenario n < 2 raakt.
Het O(2^n) runtime complexiteitsbewijs dat hier te zien is: Computationele complexiteit van Fibonacci Sequence . Het belangrijkste punt om op te merken is dat de looptijd exponentieel is, wat betekent dat de looptijd hiervoor verdubbelt voor elke volgende termijn, fibonacci(15) duurt twee keer zo lang als fibonacci(14) .
Memoized O(n) Runtime Complexity, O(n) Space complexity, O(n) Stack complexity
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
Met de memo-benadering introduceren we een array die kan worden beschouwd als alle voorgaande functie-aanroepen. De memo[n] is het resultaat van de functieaanroep fibonacci(n) . Dit stelt ons in staat om ruimtecomplexiteit van O(n) in te ruilen voor een O(n) runtime omdat we niet langer dubbele functie-aanroepen hoeven te berekenen.
Iteratieve dynamische programmering O(n) Runtime complexiteit, O(n) Ruimtecomplexiteit, Geen recursieve stapel
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
Als we het probleem opsplitsen in zijn kernelementen, zul je merken dat we fibonacci(n-1) en fibonacci(n-2) nodig hebben om fibonacci(n) te berekenen. We kunnen ook opmerken dat ons basisscenario aan het einde van die recursieve boom verschijnt, zoals hierboven te zien.
Met deze informatie is het nu logisch om de oplossing achterstevoren te berekenen, beginnend bij de basisgevallen en naar boven toe werkend. Om nu fibonacci(n) te berekenen, berekenen we eerst alle fibonacci-getallen tot en met n .
Dit belangrijkste voordeel is dat we nu de recursieve stapel hebben geëlimineerd terwijl we de O(n) -looptijd hebben behouden. Helaas hebben we nog steeds een O(n) ruimtecomplexiteit, maar dat kan ook worden gewijzigd.
Geavanceerde Iteratieve dynamische programmering O(n) Runtime complexiteit, O(1) Ruimtecomplexiteit, Geen recursieve stapel
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
Zoals hierboven opgemerkt, begint de iteratieve dynamische programmeerbenadering van de basisgevallen tot het eindresultaat. De belangrijkste observatie die we moeten maken om tot de ruimtecomplexiteit van O(1) (constant) te komen, is dezelfde observatie die we deden voor de recursieve stapel - we hebben alleen fibonacci(n-1) en fibonacci(n-2) nodig om te bouwen fibonacci(n) . Dit betekent dat we alleen de resultaten voor fibonacci(n-1) en fibonacci(n-2) op elk moment in onze iteratie hoeven op te slaan.
Om deze laatste 2 resultaten op te slaan, gebruik ik een array van maat 2 en draai ik gewoon naar welke index ik wijs door i % 2 die zo zal afwisselen: 0, 1, 0, 1, 0, 1, ..., i % 2 .
Ik voeg beide indexen van de array samen omdat we weten dat optellen commutatief is ( 5 + 6 = 11 en 6 + 5 == 11 ). Het resultaat wordt dan toegewezen aan de oudste van de twee vlekken (aangegeven met i % 2 ). Het eindresultaat wordt vervolgens opgeslagen op positie n%2
Notes
- Het is belangrijk op te merken dat het soms het beste is om een iteratieve memo-oplossing te bedenken voor functies die herhaaldelijk grote berekeningen uitvoeren, omdat u een cache opbouwt van het antwoord op de functieoproepen en de daaropvolgende oproepen
O(1)als het is al berekend.