De dynamisk programmering är en algoritmmodell som löser ett komplext problem genom att dela upp det i delproblem, lagra deras resultat för att undvika att behöva räkna om dessa resultat.
Det här schemat används när du har problem som kan delas in i liknande delproblem så att deras resultat kan återanvändas. För det mesta används denna programmering för optimering.
Innan det tillgängliga delproblemet löses försöker den dynamiska algoritmen att undersöka resultaten av de tidigare lösta delproblemen. Delproblemlösningar 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 lite minne när du först stöter på detta delproblem. När det visas igen under lösningen av ett annat delproblem tas den lösning som redan är lagrad i minnet.
Detta är en underbar idé att fixa minnestiden, där du genom att använda extra utrymme kan förbättra den tid som krävs för att hitta en lösning..
Artikelindex
Följande väsentliga egenskaper är vad du måste ha problem med innan dynamisk programmering kan tillämpas:
Denna egenskap uttrycker att ett optimeringsproblem kan lösas genom att kombinera de optimala lösningarna för de sekundära problem som innefattar det. Dessa optimala underkonstruktioner beskrivs genom rekursion.
Till exempel, i en graf presenteras en optimal understruktur i den kortaste vägen r som går från ett toppunkt s till ett toppunkt t:
Det vill säga, i denna kortaste väg r kan alla mellanliggande toppar 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), på ett sådant sätt att dessa i sin tur är de kortaste vägarna mellan motsvarande hörn.
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..
Delproblemutrymmet måste vara litet. Det vill säga 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å har vi: F33 = F32 + F31 och F32 = F31 + F30.
Som du kan se, löses F31 in i de rekursiva subtreesen för både F33 och F32. Även om det totala antalet delproblem är riktigt 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:
Om lösningen på något problem kan formuleras rekursivt med hjälp av lösningen på dess delproblem, och om dessa delproblem överlappar varandra, kan lösningarna på delproblemen lätt 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. I annat fall löses delproblemet och lagrar lösningen i tabellen.
Efter att lösningen på ett problem har formulerats rekursivt med avseende på dess delproblem kommer det att vara möjligt att försöka omformulera problemet på stigande sätt: först försöker vi 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 vanligtvis också i tabellform och genererar iterativt lösningar på större och större delproblem genom att använda lösningar på mindre delproblem. Till exempel, om värdena på F31 och F30 redan är kända, kan värdet på F32 beräknas direkt.
Ett viktigt inslag i ett problem som kan lösas dynamiskt är att det borde ha överproblem som överlappar varandra. Det är detta som skiljer dynamisk programmering från delnings- och erövringstekniken, 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 bara beror på tidigare beräknade värden.
För alla positiva heltal "e" kan något av följande tre steg utföras.
- Subtrahera 1 från numret. (e = e-1).
- Om det är delbart med 2, dividera med 2 (om e% 2 == 0, då e = e / 2).
- Om det är delbart med 3, dividera med 3 (om e% 3 == 0, då e = e / 3).
Baserat på stegen ovan måste det minsta antalet av dessa steg hittas 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).
Man kan tänka sig 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 dock: 10-1 = 9/3 = 3/3 = 1 (3 steg). Därför bör alla möjliga steg som kan göras för varje värde av n hittas försökas och välja 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 basfall: F (1) = 0. Med återkommande ekvation kan vi börja koda rekursionen.
Det kan dock ses att det har överlappande delproblem. Dessutom beror den optimala lösningen för en given ingång på den optimala lösningen på dess delproblem.
Som i memorering, där lösningarna på delproblemen som löses lagras för senare användning. Eller som i dynamisk programmering börjar du längst ner och jobbar dig upp till den angivna e. Sedan båda koderna:
En av de största fördelarna med att använda dynamisk programmering är att det påskyndar behandlingen eftersom referenser som tidigare beräknats används. Eftersom det är en rekursiv programmeringsteknik minskar det programmets kodrader.
Giriga algoritmer liknar dynamisk programmering genom att de båda är verktyg för optimering. Den giriga algoritmen letar dock efter en optimal lösning vid varje lokalt steg. Det vill säga det 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 den 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 välgrundat val genom att kombinera resultaten av dessa delproblem för att faktiskt hitta den mest optimala lösningen..
- Mycket minne behövs för att lagra det beräknade resultatet för varje delproblem, vilket inte kan garantera att det lagrade värdet kommer att användas eller inte.
- Många gånger lagras utgångsvärdet utan att någonsin användas i följande delproblem under körning. Detta leder till onödig minnesanvändning.
- I dynamisk programmering kallas funktioner rekursivt. Detta gör att stackminnet ständigt ökar.
Om du har begränsat minne för att köra din kod och bearbetningshastighet inte är ett problem kan du använda rekursion. Till exempel, om du utvecklar en mobilapplikation är minnet mycket begränsat för att köra applikationen.
Om du vill att programmet ska köras snabbare och du inte har minnesbegränsningar är det att föredra att använda dynamisk programmering.
Dynamisk programmering är en effektiv metod för att lösa problem som annars kan verka extremt svåra att lösa på rimlig tid..
Algoritmer baserade på det dynamiska programmeringsparadigmet används inom många vetenskapliga områden, inklusive många exempel inom artificiell intelligens, från planeringsproblemlösning till taligenkänning..
Dynamisk programmering är ganska effektiv och fungerar mycket bra för ett stort antal problem. Många algoritmer kan ses som giriga algoritmapplikationer, till exempel:
- Fibonacci-nummerserie.
- Hanoi Towers.
- Alla kortaste ruttpar av Floyd-Warshall.
- Ryggsäck problem.
- Projektplanering.
- Den kortaste vägen genom Dijkstra.
- Flygkontroll och robotikkontroll.
- Matematiska optimeringsproblem.
- Tidsdelning - Schemalägg jobbet för att maximera CPU-användningen.
Fibonacci-nummer ä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-tal med återfallsformeln: F (n) = F (n -1) + F (n -2), där F (0) = 0 och F (1) = 1.
I det här exemplet initialiseras en sökmatris 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 returneras det värdet. I annat fall kommer resultatet att beräknas lagras i sökarrayen så att det kan återanvändas senare.
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 kommer lösningarna på delproblemen att konstrueras från botten uppåt.
Ingen har kommenterat den här artikeln än.