Nyckelprinciper för dynamisk programmering (DP)
Dynamisk programmering är en algoritmisk teknik som används för att lösa optimeringsproblem genom att dela upp dem i mindre, överlappande delproblem, lösa varje delproblem bara en gång och lagra resultaten för att undvika redundanta beräkningar. Det är särskilt väl lämpat för problem som visar optimal understruktur och överlappande delproblem .
Här är en uppdelning av dess viktigaste principer:
1. Optimal understruktur:
- Ett problem uppvisar optimal understruktur om en optimal lösning på problemet kan konstrueras av optimala lösningar på dess delproblem. Detta innebär att om du känner till den optimala lösningen på varje mindre bit kan du dela dem ihop för att bilda den totala optimala lösningen.
- Exempel: Den kortaste vägen mellan två städer i en graf har optimal understruktur. Varje underväg av den kortaste vägen måste också vara den kortaste vägen mellan dess slutpunkter.
2. Överlappande delproblem:
- Problemet kan delas upp i delproblem som återanvänds flera gånger i beräkningen. Detta innebär att samma delproblem löses upprepade gånger om en naiv rekursiv metod används.
- Exempel: Att beräkna det nionde Fibonacci -antalet som rekursivt innebär upprepade gånger beräkning av mindre Fibonacci -nummer (t.ex. FIB (3) beräknas flera gånger vid beräkning av FIB (5)).
3. memoisering (top-down) eller tabulering (bottom-up):
- memoisering (top-down): Detta tillvägagångssätt börjar med det ursprungliga problemet och delar upp det rekursivt i delproblem. Resultaten av varje löst delproblem lagras (vanligtvis i en ordbok eller hashkarta) för att undvika ersättning. När ett delproblem stöter på för andra gången, är dess lagrade resultat helt enkelt tittat upp och returneras.
- Tabulation (bottom-up): Detta tillvägagångssätt beräknar systematiskt lösningarna på alla möjliga delproblem på ett bottom-up-sätt, börjar med de minsta delproblemen och bygger upp till det ursprungliga problemet. Resultaten lagras vanligtvis i en tabell (t.ex. en matris eller matris).
4. Stat:
- Ett tillstånd representerar en specifik konfiguration av problemet som måste lösas. Att definiera staten är avgörande för att utforma en DP -lösning. Staten bör fånga all information som krävs för att lösa ett delproblem oberoende av andra delproblem. Antalet tillstånd bestämmer vanligtvis rymdkomplexiteten för DP -lösningen.
- Exempel: I ryggsäcksproblemet kan ett tillstånd definieras som `(index, kapacitet)` där `index 'representerar de objekt som hittills beaktats och" kapacitet "representerar ryggsäckens återstående kapacitet.
5. Övergångar:
- Övergångar är reglerna som beskriver hur man beräknar lösningen till ett givet tillstånd baserat på lösningarna på dess delproblem. Dessa regler definierar förhållandet mellan de olika tillstånden och gör att du kan bygga upp lösningen från mindre delproblem. Övergångarna uttrycks vanligtvis som rekursiva ekvationer.
- Exempel: I Fibonacci-sekvensen är övergången `fib (n) =fib (n-1) + fib (n-2)`.
Applications of Dynamic Programmering
Dynamisk programmering används i stor utsträckning inom olika domäner. Här är några anmärkningsvärda applikationer:
1. Optimeringsproblem:
* Kortaste sökvägsalgoritmer:
* Floyd-Warshall-algoritm: Hitta de kortaste vägarna mellan alla par av toppar i en vägd graf.
* bellman-Ford algoritm: Hitta den kortaste vägen från en källa toppunkt till alla andra vertikaler i en vägd graf, även med negativa kantvikter (upptäcker negativa cykler).
* ryggsäcksproblem: Bestämmer de mest värdefulla artiklarna som ska inkluderas i en ryggsäck utan att överskrida dess viktkapacitet. Variationer inkluderar 0/1 ryggsäck, obegränsad ryggsäck och fraktionerad ryggsäck.
* Längsta gemensamma efterföljande (LCS): Hittar den längsta sekvensen av tecken som är gemensamma för två eller flera strängar. Används i bioinformatik (sekvensinriktning), filjämförelse och textredigering.
* Matriskedjemultiplikation: Bestämmer den optimala ordningen för att multiplicera en sekvens av matriser för att minimera antalet skalära multiplikationer.
* Redigera avstånd (levenshtein avstånd): Beräknar det minsta antalet redigeringar (infogningar, borttagningar, substitutioner) som behövs för att omvandla en sträng till en annan. Används i stavningskontroller, DNA -sekvensering och naturlig språkbehandling.
* myntändringsproblem: Hittar det minsta antalet mynt som behövs för att göra ett visst belopp, eller antalet sätt att göra en given mängd med en uppsättning mynt.
* Travel Salesperson Problem (TSP) (Hold-Karp Algoritm): Hitta den kortaste möjliga rutten som besöker varje stad exakt en gång och återvänder till Origin City. Medan DP tillhandahåller en * exakt * lösning för små fall, är det inte praktiskt för stora fall (NP-Hard).
2. Sekvensanalys:
* sekvensjustering (bioinformatik): Justering av DNA- eller proteinsekvenser för att identifiera likheter och skillnader, ofta med algoritmer som Needleman-Wunsch (Global Alignment) och Smith-Waterman (lokal anpassning).
* dolda Markov -modeller (HMMS): Används i taligenkänning, naturlig språkbehandling och bioinformatik för modellering av sekventiella data. Viterbi -algoritmen, en DP -algoritm, används för att hitta den mest troliga sekvensen av dolda tillstånd med tanke på en sekvens av observationer.
3. Grafalgoritmer:
* All-Pairs kortaste vägar (Floyd-Warshall): Som nämnts ovan.
* Nätverksflödesproblem: Hitta det maximala flödet för ett nätverk från en källa till en diskbänk.
4. Spelteori:
* Hitta optimala strategier: I spel som schack eller tic-tac-toe kan dynamisk programmering användas för att bestämma de optimala rörelserna för en spelare.
* MiniMax-algoritm (med alfa-beta-beskärning): En variant av dynamisk programmering som ofta används i spel för att utforska möjliga spelstater och hitta det bästa draget för en spelare.
5. Datorvision:
* Bildsegmentering: Dela en bild i meningsfulla regioner eller föremål. Dynamisk programmering kan användas för att optimera segmenteringsprocessen.
6. Textbehandling:
* Text Motivering: Att bestämma det optimala sättet att dela upp ett stycke i linjerna för att minimera trasigheten i den högra marginalen.
* Word Breaking: Att bryta en sekvens av karaktärer i ord.
7. Kontrollsystem:
* optimal kontroll: Bestämma kontrollingångarna som kommer att driva ett system från ett tillstånd till ett annat på ett optimalt sätt (t.ex. minimera energiförbrukningen).
Att välja mellan memoisering och tabulering:
* memoisering:
* Mer intuitivt och lättare att förstå för vissa problem.
* Beräknar bara de delproblem som faktiskt behövs.
* Kan drabbas av stacköverflöde för mycket djup rekursion.
* Tabulation:
* Vanligtvis effektivare när det gäller konstant faktorer (ingen rekursionskostnad).
* Kan beräkna vissa delproblem som inte behövs.
* I allmänhet kräver noggrann beställning av beräkningar för att säkerställa att delproblem löses innan de behövs.
Steg för att lösa ett dynamiskt programmeringsproblem:
1. Definiera tillståndet: Bestäm parametrarna som unikt identifierar ett delproblem.
2. Definiera övergångarna: Uttryck lösningen på ett delproblem när det gäller lösningarna på mindre delproblem.
3. Identifiera basfallen: Definiera lösningarna på de minsta delproblemen (utgångspunkten).
4. Implementera algoritmen: Använd antingen memoisering (top-down) eller tabulering (bottom-up) för att beräkna och lagra lösningarna.
5. Bestäm beräkningsordningen: Om du använder tabulering, bestäm rätt ordning för att beräkna delproblemen.
6. Extrahera den optimala lösningen: När alla delproblem har lösts ut, extrahera den optimala lösningen på det ursprungliga problemet från de lagrade resultaten.
Dynamisk programmering är en kraftfull teknik, men det kräver noggrann analys och problemspecifik design. Att förstå principerna och öva med olika exempel är nyckeln till att behärska denna algoritmiska strategi.
