DYNAMISK PROGRAMMERING: EGENSKAPER, EXEMPEL, FÖRDELAR, NACKDELAR - TEKNOLOGI - 2025

Den dynamiska programmeringen är en modellalgoritm som löser ett komplicerat problem genom att dela upp det i delproblem, lagra resultaten därav för att undvika att omberäkna resultaten.

Detta schema används när du har problem som kan delas upp i liknande delproblem, så att deras resultat kan återanvändas. För det mesta används detta schema för optimering.

Dynamisk programmering. Delproblem överlagrade i Fibonacci-sekvensen. Källa: Wikimedia commons, en: Användare: Dcoatzee, spåras av User: Stannered / Public domain

Innan lösningen av det tillgängliga delproblemet kommer den dynamiska algoritmen att försöka undersöka resultaten från de tidigare löst delproblemen. Lösningarna på delproblemen kombineras för att uppnå den bästa lösningen.

Istället för att beräkna samma delproblem om och om igen, kan du lagra din lösning i ett minne när du stöter på detta delproblem. När den visas igen under lösningen av ett annat delproblem tas lösningen som redan är lagrad i minnet.

Detta är en underbar idé för att fixa minnetid, där användning av extra utrymme kan förbättra den tid som krävs för att hitta en lösning.

Funktioner i dynamisk programmering

Följande väsentliga egenskaper är vad du måste ha problem med innan dynamisk programmering kan tillämpas:

Optimal understruktur

Denna egenskap uttrycker att ett optimeringsproblem kan lösas genom att kombinera de optimala lösningarna av de sekundära problemen som det innefattar. Dessa optimala understrukturer beskrivs genom rekursion.

I en graf presenteras till exempel en optimal understruktur i den kortaste vägen r som går från en toppunkt till en toppunkt t:

Det vill säga på denna kortaste väg r kan varje mellanliggande toppunkt i tas. Om r verkligen är den kortaste vägen, kan den delas in i delvägarna r1 (från s till i) och r2 (från i till t), så att dessa i sin tur är de kortaste vägarna mellan motsvarande toppar.

För att hitta de kortaste vägarna kan lösningen därför enkelt formuleras rekursivt, vilket är vad Floyd-Warshall-algoritmen gör.

Överlappande delproblem

Underproblemets utrymme måste vara litet. Det vill säga att varje rekursiv algoritm som löser ett problem måste lösa samma delproblem om och om igen, istället för att generera nya delproblem.

Till exempel, för att generera Fibonacci-serien, kan denna rekursiva formulering övervägas: Fn = F (n - 1) + F (n - 2), som basfall att F1 = F2 = 1. Då kommer vi att ha: F33 = F32 + F31 och F32 = F31 + F30.

Som ni ser är F31 att lösa in de rekursiva underträden för både F33 och F32. Även om det totala antalet delproblem verkligen är litet, kommer du att lösa samma problem om och om igen om du använder en rekursiv lösning som denna.

Detta beaktas av dynamisk programmering, så det löser varje delproblem bara en gång. Detta kan åstadkommas på två sätt:

Uppifrån och ner tillvägagångssätt

Om lösningen på något problem kan formuleras rekursivt med hjälp av lösningen av dess delproblem, och om dessa delproblem överlappar varandra, kan lösningarna på delproblemen enkelt memoreras eller lagras i en tabell.

Varje gång man söker efter en ny delproblemlösning kommer tabellen att kontrolleras för att se om den tidigare har lösts. Om en lösning lagras kommer den att användas istället för att beräkna den igen. Annars kommer delproblemet att lösas och lagra lösningen i tabellen.

Uppifrån och upp

När lösningen av ett problem har formulerats rekursivt med avseende på dess delproblem, är det möjligt att försöka omformulera problemet uppåt: Först kommer vi att försöka lösa delproblemen och använda deras lösningar för att komma fram till lösningar på de större delproblemen.

Detta görs också i allmänhet i tabellform, vilket iterativt genererar lösningar på större och större delproblem genom att använda lösningar för mindre delproblem. Om värdena på F31 och F30 till exempel redan är kända kan värdet på F32 beräknas direkt.

Jämförelse med andra tekniker

Ett viktigt inslag i ett problem som kan lösas genom dynamisk programmering är att det bör ha delproblem som överlappar varandra. Det är detta som skiljer dynamisk programmering från splittring och erövringsteknik, där det inte är nödvändigt att lagra de enklaste värdena.

Det liknar rekursion eftersom det slutliga värdet kan beräknas induktivt vid beräkning av basfall. Denna bottom-up-metod fungerar bra när ett nytt värde endast beror på tidigare beräknade värden.

Exempel

Minsta steg för att nå 1

För varje positivt heltal "e" kan något av följande tre steg utföras.

- Dra 1 från numret. (e = e-1).

- Om det är delbart med 2, delas det med 2 (om e% 2 == 0, då e = e / 2).

- Om det är delbart med 3, delas det med 3 (om e% 3 == 0, då e = e / 3).

Baserat på stegen ovan bör minimiantalet av dessa steg visas för att få e till 1. Till exempel:

- Om e = 1, resultat: 0.

- Om e = 4, resultat: 2 (4/2 = 2/2 = 1).

- När e = 7, resultat: 3 (7-1 = 6/3 = 2/2 = 1).

Fokus

Man kan tänka på att alltid välja steget som gör n så lågt som möjligt och fortsätta så här tills det når 1. Det kan dock ses att denna strategi inte fungerar här.

Till exempel, om e = 10, skulle stegen vara: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 steg). Den optimala formen är emellertid: 10-1 = 9/3 = 3/3 = 1 (3 steg). Därför måste alla möjliga steg som kan göras för varje värde på n hittas testas, välj det minsta antalet av dessa möjligheter.

Allt börjar med rekursion: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} om e> 1, med utgångspunkt: F (1) = 0. Med återfallsekvationen kan du börja koda rekursionen.

Det kan dock ses att det har överlappande delproblem. Vidare beror den optimala lösningen för en given input på den optimala lösningen av dess delproblem.

Som i memorering, där lösningarna för delproblemen som är löst lagras för senare användning. Eller som i dynamisk programmering, börjar du längst ner, arbetar dig upp till den givna e. Sedan båda koderna:

memorering

Dynamisk programmering nedifrån och upp

Fördel

En av de främsta fördelarna med att använda dynamisk programmering är att det påskyndar bearbetningen, eftersom referenser som tidigare beräknats används. Eftersom det är en rekursiv programmeringsteknik minskar den kodens rader i programmet.

Voracious algoritmer vs dynamisk programmering

Giriga algoritmer liknar dynamisk programmering eftersom de båda är verktyg för optimering. Men den giriga algoritmen letar efter en optimal lösning vid varje lokalt steg. Det vill säga den söker ett girigt val i hopp om att hitta ett globalt optimalt.

Därför kan giriga algoritmer göra ett antagande som ser optimalt ut vid tiden, men blir dyrt i framtiden och inte garanterar ett globalt optimalt.

Å andra sidan hittar dynamisk programmering den optimala lösningen för delproblemen och gör sedan ett informerat val genom att kombinera resultaten från dessa delproblem för att faktiskt hitta den mest optimala lösningen.

nackdelar

- Det behövs mycket minne för att lagra det beräknade resultatet för varje delproblem utan att kunna garantera att det lagrade värdet kommer att användas eller inte.

- Många gånger lagras utgångsvärdet utan att det någonsin har använts i följande delproblem under körning. Detta leder till onödig minnesanvändning.

- Vid dynamisk programmering kallas funktioner rekursivt. Detta håller stackminnet ständigt ökar.

Rekursion kontra dynamisk programmering

Om du har begränsat minne för att köra din kod och bearbetningshastigheten inte är ett problem kan du använda rekursion. Om du till exempel utvecklar en mobilapplikation är minnet mycket begränsat för att köra applikationen.

Om du vill att programmet ska köras snabbare och inte har några minnesbegränsningar är det att föredra att använda dynamisk programmering.

tillämpningar

Dynamisk programmering är en effektiv metod för att lösa problem som annars kan tyckas extremt svårt att lösa på rimlig tid.

Algoritmer baserade på det dynamiska programmeringsparadigmet används inom många vetenskapsområden, inklusive många exempel inom konstgjord intelligens, från planering av problemlösning till taligenkänning.

Algoritmer baserade på dynamisk programmering

Dynamisk programmering är ganska effektiv och fungerar mycket bra för ett brett spektrum av problem. Många algoritmer kan ses som giriga algoritmapplikationer, till exempel:

- Fibonacci-nummerserie.

- Torn i Hanoi.

- Alla par kortare rutter genom Floyd-Warshall.

- Ryggsäckproblem.

- Projektplanering.

- Det kortaste vägen genom Dijkstra.

- Flygkontroll och robotkontroll.

- Matematiska optimeringsproblem.

- Timeshare: schemalägga jobbet för att maximera CPU-användningen.

Fibonacci-nummerserie

Fibonacci-tal är siffrorna som finns i följande sekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

I matematisk terminologi definieras sekvensen Fn för Fibonacci-nummer av återfallsformeln: F (n) = F (n -1) + F (n -2), där F (0) = 0 och F ( 1) = 1.

Uppifrån och ner tillvägagångssätt

I det här exemplet initialiseras en sökgrupp med alla initialvärden med -1. Närhelst lösningen på ett delproblem behövs kommer denna sökmatris att sökas först.

Om det beräknade värdet finns där, kommer det värdet att returneras. Annars beräknas resultatet för att lagras i sökfältet så att det kan återanvändas senare.

Uppifrån och upp

I detta fall beräknas f (0) för samma Fibonacci-serie först, sedan f (1), f (2), f (3) och så vidare. Således konstrueras delproblemens lösningar från botten och upp.

referenser

1. Vineet Choudhary (2020). Introduktion till dynamisk programmering. Developer Insider Hämtad från: Developerinsider.co.
2. Alex Allain (2020). Dynamisk programmering i C ++. C-programmering. Hämtad från: cprogramming.com.
3. After Academy (2020). Idé om dynamisk programmering. Hämtad från: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dynamisk programmering och rekursion - skillnad, fördelar med exempel. CSE-stack. Hämtad från: csestack.org.
5. Code Chef (2020). Handledning för dynamisk programmering. Hämtad från: codechef.com.
6. Programiz (2020). Dynamisk programmering. Hämtad från: programiz.com.