Dynamické programování příklady optimálního řízení. Dynamické programování pro začátečníky. Dynamické programování. Základní pojmy

Řekněme, že existuje problém, který jsme již vyřešili dynamické programování, například věčná Fibonacciho čísla.
Pojďme si to trochu přeformulovat. Mějme vektor, ze kterého chceme vektor získat. Pojďme si vzorce trochu rozšířit: . Můžete vidět, že z vektoru můžete získat vektor násobením nějakou maticí, protože ve výsledném vektoru se objeví pouze přidané proměnné z prvního vektoru. Tuto matici lze snadno odvodit, zde je: . Říkejme tomu přechodová matice.

To znamená, že pokud vezmeme vektor a vynásobíme to přechodovou maticí n - 1 krát, dostaneme vektor obsahující fib[n] - odpověď na problém.

Proč je to všechno nutné? Maticové násobení má vlastnost asociativnosti, tedy (ale zároveň nemá komutativitu, což je podle mě překvapivé). Tato vlastnost nám dává právo: .

To je dobré, protože nyní můžete použít metodu rychlého umocňování, která funguje v . Celkem jsme byli schopni vypočítat N-té Fibonacciho číslo jako logaritmus aritmetických operací.

A teď vážnější příklad:

Příklad č. 3: Sekvence ramp

Označme pilovitou posloupnost délky N jako posloupnost, ve které je pro každý neextrémní prvek splněna následující podmínka: je buď menší než oba jeho sousedé, nebo větší. Musíte spočítat počet pilových sekvencí číslic délky N . Vypadá to nějak takto:

Řešení

Nejprve řešení bez přechodové matice:

1) Stav dynamiky: dp[n] - počet pilových sekvencí délky n končící posledním číslem. Navíc, je-li méně == 0, pak je poslední číslice menší než předposlední, a je-li méně == 1, pak je více.
2) Počáteční hodnoty:
pro poslední v rozsahu(10): dp = 9 - poslední dp = poslední 3) Přepočet dynamiky:
for prev in range(10): if prev > last: dp[n] += dp if prev< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Odpověď je součet dp[N] .

Nyní musíme přijít s počátečním vektorem a přechodovou maticí k němu. Zdá se, že vektor přichází rychle: všechny stavy označující délku sekvence N . Přechodová matice je odvozena pohledem na převodní vzorce.

Přechodový vektor a matice

Dynamika podle subsegmentů

Toto je třída dynamiky, ve které je stav hranicemi dílčího segmentu nějakého pole. Jde o to vypočítat odpovědi na dílčí problémy na základě všech možných dílčích segmentů našeho pole. Obvykle jsou seřazeny podle rostoucí délky a přepočet je tedy založen na kratších segmentech.

Příklad č. 4: Balení řetězce

Zde je rozšířená podmínka. Stručně to shrnu:

Pojďme definovat komprimovaný řetězec:
1) Řetězec sestávající pouze z písmen je komprimovaný řetězec. Uvolňuje se do sebe.
2) Řetězec, který je zřetězením dvou komprimovaných řetězců A a B. Je dekomprimován do zřetězení dekomprimovaných řetězců A a B.
3) Řetězec D(X) , kde D je celé číslo větší než 1 a X je komprimovaný řetězec. Je dekomprimován do zřetězení D řetězců dekomprimovaných z X .
Příklad: „3(2(A)2(B))C“ se rozšíří na „AABBAABBAABBC“ .

Z řetězce s je nutné zjistit délku nejkratšího komprimovaného řetězce, který se do něj dekomprimuje.

Řešení

Tento problém je vyřešen, jak jste již pravděpodobně uhodli, dynamikou v subsegmentech.

1) Stav dynamiky: d[l][r] - komprimovaný řetězec minimální délky, dekomprimovaný na řetězec s
2) Počáteční stavy: všechny podřetězce délky jedna mohou být komprimovány pouze do sebe.
3) Přepočet dynamiky:
Nejlepší odpověď má nějaké poslední operace komprese: buď je to jen řetězec z velká písmena, nebo je to zřetězení dvou řetězců, nebo samotná komprese. Pojďme si tedy projít všechny možnosti a vybrat tu nejlepší.

Dp_len = r - l dp[l][r] = dp_len # První možnost komprese je pouze řetězec. pro i v rozsahu (l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Zkuste dělit dva komprimované podřetězce pro cnt v rozsahu(2, dp_len): if (dp_len % cnt == 0): # Pokud to není dělitelné, pak nemá smysl zkoušet dělit dobro = True pro j v rozsahu(1, ( dp_len / cnt) + 1 ): # Zkontrolujte, zda jsou všechny podřetězce cnt stejně dobré &= s == s pokud je dobré: # Zkuste rozdělit na cnt identické podřetězce a komprimovat dp[l][r] = min(dp[l ][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Pořadí přepočtu: přímá vzestupná délka podřetězce nebo líná dynamika.
5) Odpověď spočívá v d.

Příklad č. 5: Duby

Dynamika podle podstromů

Stavovým parametrem dynamiky podél podstromů je obvykle vrchol, který označuje podstrom, ve kterém je tento vrchol kořenem. K získání hodnoty aktuálního stavu většinou potřebujete znát výsledky všech svých dětí. Nejčastěji to implementují líně – jednoduše napíšou hloubkové hledání z kořene stromu.

Příklad č. 6: Logický strom

Daný visící strom, jehož listy obsahují jednobitová čísla - 0 nebo 1. Všechny vnitřní vrcholy také obsahují čísla, ale podle následujícího pravidla: pro každý vrchol jedno z logické operace: „A“ nebo „NEBO“. Pokud je to "AND", pak hodnota vrcholu je logickým "AND" z hodnot všech jeho potomků. Pokud je „OR“, pak hodnota vrcholu je logickým „NEBO“ z hodnot všech jeho potomků.

Je nutné najít minimální počet změn v logických operacích ve vnitřních vrcholech tak, aby se změnila hodnota v kořenu, nebo ohlásit, že to není možné.

Řešení

1) Dynamický stav: d[v][x] - počet operací potřebných k získání hodnoty x ve vrcholu v. Pokud to není možné, pak hodnota stavu je +inf .
2) Počáteční hodnoty: u listů je zřejmé, že vaši hodnotu lze získat v nulových změnách, ale změnit hodnotu nelze, tedy je to možné, ale pouze v operacích +inf.
3) Konverzní vzorec:
Pokud tento vrchol již má hodnotu x , pak nula. Pokud ne, pak jsou dvě možnosti: změnit operaci v aktuálním vrcholu nebo ne. Pro obojí musíte najít nejlepší možnost a vybrat ten nejlepší.

Pokud je operace „AND“ a potřebujete získat „0“, pak je odpovědí minimum z hodnot d[i] , kde i je synem v .
Pokud je operace „AND“ a chcete získat „1“, pak je odpovědí součet všech hodnot d[i] , kde i je synem v .
Pokud je operace „OR“ a chcete získat „0“, pak je odpovědí součet všech hodnot d[i] , kde i je synem v .
Pokud je operace „OR“ a potřebujete získat „1“, pak je odpovědí minimum hodnot d[i] , kde i je synem v .

4) Pořadí přepočtu: nejjednodušší způsob, jak jej implementovat, je líně - formou hloubkového vyhledávání od kořene.
5) Odpověď je d xor 1].

Dynamika podle podmnožin

V dynamice podmnožin stav obvykle zahrnuje masku dané množiny. Nejčastěji jsou řazeny podle rostoucího počtu jednotek v této masce a podle toho se přepočítávají ze stavů, které jsou v zahrnutí menší. Lazy dynamics se obvykle používá proto, aby se specificky neuvažovalo o pořadí průchodu, což někdy není úplně triviální.

Příklad č. 7: Hamiltonovský cyklus minimální hmotnosti nebo problém obchodního cestujícího

Je dán vážený (váhy hran jsou nezáporné) graf G o velikosti N . Najděte hamiltonovský cyklus (cyklus procházející všemi vrcholy bez vlastních průniků) o minimální hmotnosti.

Řešení

Protože hledáme cyklus procházející všemi vrcholy, můžeme jako „počáteční“ zvolit libovolný vrchol. Nechť toto je číslo vrcholu 0.

1) Stav dynamiky: dp[v] - cesta minimální váhy z vrcholu 0 do vrcholu v, procházející všemi vrcholy ležícími v masce a pouze jimi.
2) Počáteční hodnoty: dp = 0, všechny ostatní stavy jsou zpočátku +inf.
3) Konverzní vzorec: Pokud je i-tý bit v masce 1 a existuje hrana od i do v, pak:
dp[v] = min(dp[v], dp[i] + w[i][v]) Kde w[i][v] je váha hrany od i do v .
4) Postup přepočtu: nejjednodušší a pohodlný způsob- to je psát línou dynamiku, ale můžete být kreativní a napsat výčet masek v pořadí, v němž zvýšíte počet jednotkových bitů.
5) Odpověď spočívá v d[(1<< N) - 1] .

Dynamika podle profilu

Klasické problémy řešené profilovou dynamikou jsou problémy obkládání pole nějakými figurami. Navíc se lze ptát na různé věci, například na počet způsobů obkládání nebo obkládání s minimálním počtem figurek.

Tyto problémy lze vyřešit vyčerpávajícím hledáním v , kde a je počet možností dlaždic pro jednu buňku. Dynamika podle profilu optimalizuje čas podél jedné z dimenzí na lineární, přičemž v exponenciále ponechává pouze koeficient. Dostanete něco takového: .

Profil je k (často jeden) sloupů, které jsou hranicí mezi částí, která již byla vydlážděna, a částí, která ještě nebyla vydlážděna. Tato hranice je vyplněna pouze částečně. Velmi často je součástí dynamického stavu.

Téměř vždy je stavem profil a kde se tento profil nachází. A přechod zvyšuje toto umístění o jeden. Zda je možné přecházet z jednoho profilu do druhého, zjistíte v čase lineárně k velikosti profilu. To lze zkontrolovat pokaždé při přepočtu, ale lze to také předem spočítat. Předběžně spočítáme dvourozměrné pole plechovky - je možné přecházet z jedné masky do druhé umístěním několika obrazců, čímž se poloha profilu zvýší o jednu. Pokud provedete předběžný výpočet, bude to trvat méně času a více paměti.

Příklad č. 8: Obklad Domino

Najděte počet způsobů, jak uspořádat stůl N x M pomocí kostek domina 1 x 2 a 2 x 1.

Řešení

Zde je profil jeden sloupec. Je vhodné jej ukládat ve formě binární masky: 0 - nezarovnaná buňka sloupce, 1 - dlaždicová buňka. Tedy celkové profily.

0) Předběžná kalkulace (volitelná): projděte všechny dvojice profilů a zkontrolujte, zda je možné přejít z jednoho do druhého. V tomto problému se to kontroluje takto:

Pokud je v prvním profilu na dalším místě 1, pak ve druhém musí být 0, protože tuto buňku nebudeme moci pokrýt žádnou číslicí.

Pokud je v prvním profilu na dalším místě 0, pak jsou dvě možnosti - buď ve druhém je 0 nebo 1.
Pokud je 0, znamená to, že musíme umístit vertikální domino, což znamená, že další buňku lze považovat za 1. Pokud 1, pak položíme vertikální domino a přesuneme se do další buňky.

Příklady přechodů (z horního profilu můžete přejít na spodní a pouze tam):

Poté uložte vše do pole plechovek - 1, pokud můžete, 0, pokud nemůžete.
1) Stav dynamiky: dp - počet kompletních obkladů první pozice - 1 sloupec s profilem masky.
2) Výchozí stav: dp = 1 - levá hranice pole - rovná stěna.
3) Konverzní vzorec:
dp += dp * může
4) Pořadí průchodu je v pořadí rostoucí poz.
5) Odpověď spočívá v dp.

Výsledná asymptotika je .

Dynamika podél rozbitého profilu

Jedná se o velmi silnou optimalizaci dynamiky profilu. Zde profil není jen maskou, ale také bodem zlomu. Vypadá to takto:

Nyní, po přidání přestávky do profilu, můžete přejít k dalšímu stavu a přidat pouze jednu figuru pokrývající levou buňku přestávky. To znamená, že zvýšením počtu stavů Nkrát (musíme si pamatovat, kde je bod zlomu), jsme snížili počet přechodů z jednoho stavu do druhého z na . Asymptotika se zlepšila z na .

Přechody v dynamice podél členitého profilu na příkladu problému s obklady domino (příklad č. 8):

Obnovení odpovědi

Někdy se stává, že prostě znát nějakou charakteristiku nejlepší odpovědi nestačí. Například v úloze „String Packing“ (příklad č. 4) dostaneme pouze délku nejkratšího komprimovaného řetězce, ale s největší pravděpodobností nepotřebujeme jeho délku, ale samotný řetězec. V tomto případě musíte obnovit odpověď.

Každý problém má svůj vlastní způsob, jak získat odpověď, ale nejběžnější jsou:

• Uložte úplnou odpověď na dílčí úkol vedle hodnoty stavu dynamiky. Pokud je odpovědí něco velkého, může to vyžadovat příliš mnoho paměti, takže pokud lze použít jinou metodu, obvykle se to dělá.
• Zrekonstruujte odpověď se znalostí předka (předků) daného státu. Často je možné rekonstruovat odpověď tak, že víme pouze to, jak byla přijata. Ve stejném „Sbalení řetězců“ pro obnovení odpovědi můžete uložit pouze typ poslední akce a stavy, ze kterých byla přijata.
• Existuje způsob, který vůbec nepoužívá přídavnou paměť – po přepočtu dynamiky jděte od konce po nejlepší cestě a po cestě skládejte odpověď.

Malé optimalizace

Paměť

Často se v dynamice můžeme setkat s problémem, kdy stav vyžaduje napočítání nepříliš velkého počtu dalších stavů. Například při výpočtu Fibonacciho čísel používáme pouze poslední dvě a nikdy se neobracíme na předchozí. To znamená, že na ně můžete zapomenout, tedy neukládat je do paměti. Někdy to zlepšuje asymptotický odhad z paměti. Tuto techniku ​​lze použít v příkladech č. 1, č. 2, č. 3 (v roztoku bez přechodové matrice), č. 7 a č. 8. Pravda, nelze to nijak využít, pokud je pořadím procházení líná dynamika.

Čas

Někdy se stane, že asymptotický čas můžete zlepšit použitím nějaké datové struktury. Například v Dijkstrově algoritmu můžete použít prioritní frontu ke změně asymptotického času.

Náhrada státu

V řešeních dynamikou se nutně objevuje stav - parametry, které jednoznačně definují dílčí úlohu, ale tento stav nemusí být nutně jediný. Někdy můžete přijít s jinými parametry a získat z toho benefit v podobě zkrácení asymptotického času nebo paměti.

Příklad č. 9: Rozšíření čísel

Musíte najít počet rozkladů čísla N na různé členy. Pokud například N = 7, pak existuje 5 takových rozšíření:

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Řekněme, že existuje problém, který jsme již vyřešili dynamickým programováním, například věčná Fibonacciho čísla.
Pojďme si to trochu přeformulovat. Mějme vektor, ze kterého chceme vektor získat. Pojďme si vzorce trochu rozšířit: . Můžete vidět, že z vektoru můžete získat vektor násobením nějakou maticí, protože ve výsledném vektoru se objeví pouze přidané proměnné z prvního vektoru. Tuto matici lze snadno odvodit, zde je: . Říkejme tomu přechodová matice.

To znamená, že pokud vezmeme vektor a vynásobíme to přechodovou maticí n - 1 krát, dostaneme vektor obsahující fib[n] - odpověď na problém.

Proč je to všechno nutné? Maticové násobení má vlastnost asociativnosti, tedy (ale zároveň nemá komutativitu, což je podle mě překvapivé). Tato vlastnost nám dává právo: .

To je dobré, protože nyní můžete použít metodu rychlého umocňování, která funguje v . Celkem jsme byli schopni vypočítat N-té Fibonacciho číslo jako logaritmus aritmetických operací.

A teď vážnější příklad:

Příklad č. 3: Sekvence ramp

Označme pilovitou posloupnost délky N jako posloupnost, ve které je pro každý neextrémní prvek splněna následující podmínka: je buď menší než oba jeho sousedé, nebo větší. Musíte spočítat počet pilových sekvencí číslic délky N . Vypadá to nějak takto:

Řešení

Nejprve řešení bez přechodové matice:

1) Stav dynamiky: dp[n] - počet pilových sekvencí délky n končící posledním číslem. Navíc, je-li méně == 0, pak je poslední číslice menší než předposlední, a je-li méně == 1, pak je více.
2) Počáteční hodnoty:
pro poslední v rozsahu(10): dp = 9 - poslední dp = poslední 3) Přepočet dynamiky:
for prev in range(10): if prev > last: dp[n] += dp if prev< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Odpověď je součet dp[N] .

Nyní musíme přijít s počátečním vektorem a přechodovou maticí k němu. Zdá se, že vektor přichází rychle: všechny stavy označující délku sekvence N . Přechodová matice je odvozena pohledem na převodní vzorce.

Přechodový vektor a matice

Dynamika podle subsegmentů

Toto je třída dynamiky, ve které je stav hranicemi dílčího segmentu nějakého pole. Jde o to vypočítat odpovědi na dílčí problémy na základě všech možných dílčích segmentů našeho pole. Obvykle jsou seřazeny podle rostoucí délky a přepočet je tedy založen na kratších segmentech.

Příklad č. 4: Balení řetězce

Zde je rozšířená podmínka. Stručně to shrnu:

Pojďme definovat komprimovaný řetězec:
1) Řetězec sestávající pouze z písmen je komprimovaný řetězec. Uvolňuje se do sebe.
2) Řetězec, který je zřetězením dvou komprimovaných řetězců A a B. Je dekomprimován do zřetězení dekomprimovaných řetězců A a B.
3) Řetězec D(X) , kde D je celé číslo větší než 1 a X je komprimovaný řetězec. Je dekomprimován do zřetězení D řetězců dekomprimovaných z X .
Příklad: „3(2(A)2(B))C“ se rozšíří na „AABBAABBAABBC“ .

Z řetězce s je nutné zjistit délku nejkratšího komprimovaného řetězce, který se do něj dekomprimuje.

Řešení

Tento problém je vyřešen, jak jste již pravděpodobně uhodli, dynamikou v subsegmentech.

1) Stav dynamiky: d[l][r] - komprimovaný řetězec minimální délky, dekomprimovaný na řetězec s
2) Počáteční stavy: všechny podřetězce délky jedna mohou být komprimovány pouze do sebe.
3) Přepočet dynamiky:
Nejlepší odpovědí je nějaká závěrečná kompresní operace: buď je to jen řetězec velkých písmen, nebo je to zřetězení dvou řetězců, nebo samotná komprese. Pojďme si tedy projít všechny možnosti a vybrat tu nejlepší.

Dp_len = r - l dp[l][r] = dp_len # První možnost komprese je pouze řetězec. pro i v rozsahu (l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Zkuste dělit dva komprimované podřetězce pro cnt v rozsahu(2, dp_len): if (dp_len % cnt == 0): # Pokud to není dělitelné, pak nemá smysl zkoušet dělit dobro = True pro j v rozsahu(1, ( dp_len / cnt) + 1 ): # Zkontrolujte, zda jsou všechny podřetězce cnt stejně dobré &= s == s pokud je dobré: # Zkuste rozdělit na cnt identické podřetězce a komprimovat dp[l][r] = min(dp[l ][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Pořadí přepočtu: přímá vzestupná délka podřetězce nebo líná dynamika.
5) Odpověď spočívá v d.

Příklad č. 5:

Dynamika podle podstromů

Stavovým parametrem dynamiky podél podstromů je obvykle vrchol, který označuje podstrom, ve kterém je tento vrchol kořenem. K získání hodnoty aktuálního stavu většinou potřebujete znát výsledky všech svých dětí. Nejčastěji to implementují líně – jednoduše napíšou hloubkové hledání z kořene stromu.

Příklad č. 6: Logický strom

Daný visící strom, jehož listy obsahují jednobitová čísla - 0 nebo 1. Všechny vnitřní vrcholy také obsahují čísla, ale podle následujícího pravidla: pro každý vrchol je vybrána jedna z logických operací: „AND“ nebo „NEBO“. Pokud je to "AND", pak hodnota vrcholu je logickým "AND" z hodnot všech jeho potomků. Pokud je „OR“, pak hodnota vrcholu je logickým „NEBO“ z hodnot všech jeho potomků.

Je nutné najít minimální počet změn v logických operacích ve vnitřních vrcholech tak, aby se změnila hodnota v kořenu, nebo ohlásit, že to není možné.

Řešení

1) Dynamický stav: d[v][x] - počet operací potřebných k získání hodnoty x ve vrcholu v. Pokud to není možné, pak hodnota stavu je +inf .
2) Počáteční hodnoty: u listů je zřejmé, že vaši hodnotu lze získat v nulových změnách, ale změnit hodnotu nelze, tedy je to možné, ale pouze v operacích +inf.
3) Konverzní vzorec:
Pokud tento vrchol již má hodnotu x , pak nula. Pokud ne, pak jsou dvě možnosti: změnit operaci v aktuálním vrcholu nebo ne. Pro oba musíte najít tu nejlepší možnost a vybrat tu nejlepší.

Pokud je operace „AND“ a potřebujete získat „0“, pak je odpovědí minimum z hodnot d[i] , kde i je synem v .
Pokud je operace „AND“ a chcete získat „1“, pak je odpovědí součet všech hodnot d[i] , kde i je synem v .
Pokud je operace „OR“ a chcete získat „0“, pak je odpovědí součet všech hodnot d[i] , kde i je synem v .
Pokud je operace „OR“ a potřebujete získat „1“, pak je odpovědí minimum hodnot d[i] , kde i je synem v .

4) Pořadí přepočtu: nejjednodušší způsob, jak jej implementovat, je líně - formou hloubkového vyhledávání od kořene.
5) Odpověď je d xor 1].

Dynamika podle podmnožin

V dynamice podmnožin stav obvykle zahrnuje masku dané množiny. Nejčastěji jsou řazeny podle rostoucího počtu jednotek v této masce a podle toho se přepočítávají ze stavů, které jsou v zahrnutí menší. Lazy dynamics se obvykle používá proto, aby se specificky neuvažovalo o pořadí průchodu, což někdy není úplně triviální.

Příklad č. 7: Hamiltonovský cyklus minimální hmotnosti nebo problém obchodního cestujícího

Je dán vážený (váhy hran jsou nezáporné) graf G o velikosti N . Najděte hamiltonovský cyklus (cyklus procházející všemi vrcholy bez vlastních průniků) o minimální hmotnosti.

Řešení

Protože hledáme cyklus procházející všemi vrcholy, můžeme jako „počáteční“ zvolit libovolný vrchol. Nechť toto je číslo vrcholu 0.

1) Stav dynamiky: dp[v] - cesta minimální váhy z vrcholu 0 do vrcholu v, procházející všemi vrcholy ležícími v masce a pouze jimi.
2) Počáteční hodnoty: dp = 0, všechny ostatní stavy jsou zpočátku +inf.
3) Konverzní vzorec: Pokud je i-tý bit v masce 1 a existuje hrana od i do v, pak:
dp[v] = min(dp[v], dp[i] + w[i][v]) Kde w[i][v] je váha hrany od i do v .
4) Pořadí přepočtu: nejjednodušší a nejpohodlnější způsob je napsat línou dynamiku, ale můžete být kreativní a napsat vyhledávání masek v pořadí, v němž se zvýší počet jednotkových bitů.
5) Odpověď spočívá v d[(1<< N) - 1] .

Dynamika podle profilu

Klasické problémy řešené profilovou dynamikou jsou problémy obkládání pole nějakými figurami. Navíc se lze ptát na různé věci, například na počet způsobů obkládání nebo obkládání s minimálním počtem figurek.

Tyto problémy lze vyřešit vyčerpávajícím hledáním v , kde a je počet možností dlaždic pro jednu buňku. Dynamika podle profilu optimalizuje čas podél jedné z dimenzí na lineární, přičemž v exponenciále ponechává pouze koeficient. Dostanete něco takového: .

Profil je k (často jeden) sloupů, které jsou hranicí mezi částí, která již byla vydlážděna, a částí, která ještě nebyla vydlážděna. Tato hranice je vyplněna pouze částečně. Velmi často je součástí dynamického stavu.

Téměř vždy je stavem profil a kde se tento profil nachází. A přechod zvyšuje toto umístění o jeden. Zda je možné přecházet z jednoho profilu do druhého, zjistíte v čase lineárně k velikosti profilu. To lze zkontrolovat pokaždé při přepočtu, ale lze to také předem spočítat. Předběžně spočítáme dvourozměrné pole plechovky - je možné přecházet z jedné masky do druhé umístěním několika obrazců, čímž se poloha profilu zvýší o jednu. Pokud provedete předběžný výpočet, bude to trvat méně času a více paměti.

Příklad č. 8: Obklad Domino

Najděte počet způsobů, jak uspořádat stůl N x M pomocí kostek domina 1 x 2 a 2 x 1.

Řešení

Zde je profil jeden sloupec. Je vhodné jej ukládat ve formě binární masky: 0 - nezarovnaná buňka sloupce, 1 - dlaždicová buňka. Tedy celkové profily.

0) Předběžná kalkulace (volitelná): projděte všechny dvojice profilů a zkontrolujte, zda je možné přejít z jednoho do druhého. V tomto problému se to kontroluje takto:

Pokud je v prvním profilu na dalším místě 1, pak ve druhém musí být 0, protože tuto buňku nebudeme moci pokrýt žádnou číslicí.

Pokud je v prvním profilu na dalším místě 0, pak jsou dvě možnosti - buď ve druhém je 0 nebo 1.
Pokud je 0, znamená to, že musíme umístit vertikální domino, což znamená, že další buňku lze považovat za 1. Pokud 1, pak položíme vertikální domino a přesuneme se do další buňky.

Příklady přechodů (z horního profilu můžete přejít na spodní a pouze tam):

Poté uložte vše do pole plechovek - 1, pokud můžete, 0, pokud nemůžete.
1) Stav dynamiky: dp - počet kompletních obkladů první pozice - 1 sloupec s profilem masky.
2) Výchozí stav: dp = 1 - levá hranice pole - rovná stěna.
3) Konverzní vzorec:
dp += dp * může
4) Pořadí průchodu je v pořadí rostoucí poz.
5) Odpověď spočívá v dp.

Výsledná asymptotika je .

Dynamika podél rozbitého profilu

Jedná se o velmi silnou optimalizaci dynamiky profilu. Zde profil není jen maskou, ale také bodem zlomu. Vypadá to takto:

Nyní, po přidání přestávky do profilu, můžete přejít k dalšímu stavu a přidat pouze jednu figuru pokrývající levou buňku přestávky. To znamená, že zvýšením počtu stavů Nkrát (musíme si pamatovat, kde je bod zlomu), jsme snížili počet přechodů z jednoho stavu do druhého z na . Asymptotika se zlepšila z na .

Přechody v dynamice podél členitého profilu na příkladu problému s obklady domino (příklad č. 8):

Obnovení odpovědi

Někdy se stává, že prostě znát nějakou charakteristiku nejlepší odpovědi nestačí. Například v úloze „String Packing“ (příklad č. 4) dostaneme pouze délku nejkratšího komprimovaného řetězce, ale s největší pravděpodobností nepotřebujeme jeho délku, ale samotný řetězec. V tomto případě musíte obnovit odpověď.

Každý problém má svůj vlastní způsob, jak získat odpověď, ale nejběžnější jsou:

• Uložte úplnou odpověď na dílčí úkol vedle hodnoty stavu dynamiky. Pokud je odpovědí něco velkého, může to vyžadovat příliš mnoho paměti, takže pokud lze použít jinou metodu, obvykle se to dělá.
• Zrekonstruujte odpověď se znalostí předka (předků) daného státu. Často je možné rekonstruovat odpověď tak, že víme pouze to, jak byla přijata. Ve stejném „Sbalení řetězců“ pro obnovení odpovědi můžete uložit pouze typ poslední akce a stavy, ze kterých byla přijata.
• Existuje způsob, který vůbec nepoužívá přídavnou paměť – po přepočtu dynamiky jděte od konce po nejlepší cestě a po cestě skládejte odpověď.

Malé optimalizace

Paměť

Často se v dynamice můžeme setkat s problémem, kdy stav vyžaduje napočítání nepříliš velkého počtu dalších stavů. Například při výpočtu Fibonacciho čísel používáme pouze poslední dvě a nikdy se neobracíme na předchozí. To znamená, že na ně můžete zapomenout, tedy neukládat je do paměti. Někdy to zlepšuje asymptotický odhad z paměti. Tuto techniku ​​lze použít v příkladech č. 1, č. 2, č. 3 (v roztoku bez přechodové matrice), č. 7 a č. 8. Pravda, nelze to nijak využít, pokud je pořadím procházení líná dynamika.

Čas

Někdy se stane, že asymptotický čas můžete zlepšit použitím nějaké datové struktury. Například v Dijkstrově algoritmu můžete použít prioritní frontu ke změně asymptotického času.

Náhrada státu

V řešeních dynamikou se nutně objevuje stav - parametry, které jednoznačně definují dílčí úlohu, ale tento stav nemusí být nutně jediný. Někdy můžete přijít s jinými parametry a získat z toho benefit v podobě zkrácení asymptotického času nebo paměti.

Příklad č. 9: Rozšíření čísel

Musíte najít počet rozkladů čísla N na různé členy. Pokud například N = 7, pak existuje 5 takových rozšíření:

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Pro výběr optimálního řešení při provádění programovacích úloh je někdy nutné třídit velké množství kombinací dat, což zatěžuje paměť osobního počítače. Mezi takové metody patří například programovací metoda „rozděl a panuj“. V tomto případě algoritmus umožňuje rozdělení úkolu na samostatné malé dílčí úkoly. Tato metoda se používá pouze v případech, kdy jsou malé dílčí úkoly na sobě nezávislé. Aby se předešlo zbytečné práci, pokud jsou dílčí úkoly na sobě závislé, používá se metoda dynamického programování navržená Američanem R. Bellmanem v 50. letech.

Podstata metody

Dynamické programování zahrnuje určení optimálního řešení n-rozměrného problému jeho rozdělením do n samostatných kroků. Každý z nich je dílčím úkolem s ohledem na jednu proměnnou.

Hlavní výhodou tohoto přístupu je, že se vývojáři zabývají jednorozměrnými optimalizačními problémy dílčích úloh namísto n-rozměrného problému a řešení hlavního problému je sestaveno „zdola nahoru“.

Dynamické programování je vhodné používat v případech, kdy dílčí úkoly spolu souvisí, tzn. mají společné moduly. Algoritmus umožňuje vyřešit každý z dílčích úkolů jednou a odpovědi jsou uloženy ve speciální tabulce. To umožňuje nepřepočítávat odpověď při setkání s podobným dílčím úkolem.

Problém optimalizace dynamického programování. Autor této metody R. Bellman formuloval princip optimality: bez ohledu na počáteční stav každého z kroků a řešení určené v tomto kroku, všechny následující jsou zvoleny optimální ve vztahu ke stavu, který systém nabývá na konec kroku.

Metoda zlepší provádění problémů řešených pomocí výčtu opcí nebo rekurzí.

Konstrukce problémového algoritmu

Dynamické programování zahrnuje konstrukci algoritmu problému, ve kterém je problém rozdělen do dvou nebo více dílčích úkolů tak, aby jeho řešení sestávalo z optimálního řešení všech dílčích úkolů v něm obsažených. Dále je potřeba napsat rekurenci recidivy a vypočítat optimální hodnotu parametru pro problém jako celek.

Někdy si ve 3. kroku musíte dodatečně zapamatovat nějaké pomocné informace o průběhu každého dílčího úkolu. Tomu se říká couvání.

Aplikace metody

Dynamické programování se používá, když jsou přítomny dva charakteristické rysy:

• optimalita pro dílčí úkoly;
• přítomnost překrývajících se dílčích úkolů v úkolu.

Při řešení pomocí dynamického programování je potřeba nejprve popsat strukturu řešení. Problém je optimální, pokud řešení problému sestává z optimálních řešení jeho dílčích problémů. V tomto případě je vhodné použít dynamické programování.

Druhou vlastností problému, která je pro tuto metodu zásadní, je malý počet dílčích úloh. Rekurzivní řešení problému využívá stejné překrývající se dílčí problémy, jejichž počet závisí na velikosti vstupní informace. Odpověď je uložena ve speciální tabulce, program šetří čas používáním těchto dat.

Využití dynamického programování je zvláště účinné, když je třeba rozhodovat o podstatě problému krok za krokem. Zvažte například jednoduchý příklad problému výměny a opravy zařízení. Řekněme, že licí stroj slévárny pneumatik vyrábí pneumatiky ve dvou různých tvarech současně. Pokud jedna z forem selže, je nutné stroj rozebrat. Je jasné, že někdy je výhodnější vyměnit druhou formu, aby nedošlo k rozebrání stroje v případě, že se i tato forma v další fázi ukáže jako nefunkční. Navíc může být snazší vyměnit obě pracovní formy dříve, než začnou selhávat. Metoda dynamického programování určuje nejlepší strategii pro výměnu takových forem, přičemž bere v úvahu všechny faktory: výhody pokračování v provozu forem, ztráty z prostojů stroje, náklady na vyřazené pneumatiky a další.

), vypadá jako soubor překrývajících se dílčích problémů, jejichž složitost je o něco menší než původní. V tomto případě může být doba výpočtu ve srovnání s „naivními“ metodami výrazně zkrácena.

Klíčová myšlenka dynamického programování je poměrně jednoduchá. Zpravidla je pro vyřešení daného problému nutné vyřešit jednotlivé části problému (dílčí úlohy), a následně řešení dílčích úloh spojit do jednoho obecného řešení. Mnoho z těchto dílčích úkolů je často stejných. Přístup dynamického programování spočívá v řešení každého dílčího problému pouze jednou, čímž se sníží počet výpočtů. To je užitečné zejména v případech, kdy je počet opakujících se dílčích úkolů exponenciálně velký.

Metoda dynamické programování shora- jde o jednoduché zapamatování výsledků řešení těch dílčích úkolů, se kterými se můžete v budoucnu znovu setkat. Dynamické programování zdola zahrnuje přeformulování složitého problému do rekurzivní sekvence jednodušších dílčích problémů.

Příběh

Fráze „dynamické programování“ byla poprvé použita v 90. letech 20. století R. Bellmanem k popisu procesu hledání řešení problému, kdy odpověď na jeden problém lze získat až po vyřešení problému, který mu „předcházel“. Ve městě tuto definici upřesnil na tu moderní. Tento obor byl původně založen jako systémová analýza a inženýrství, což bylo uznáno IEEE. Bellmanovy příspěvky k dynamickému programování byly zvěčněny ve jménu Bellmanovy rovnice, ústředního výsledku teorie dynamického programování, která přeformuluje optimalizační problém v rekurzivní formě.

Slovo „programování“ ve frázi „dynamické programování“ ve skutečnosti nemá téměř nic společného s „tradičním“ programováním (psaní kódu) a má stejný význam jako ve frázi „matematické programování“, které je synonymem slova „optimalizace“ . Proto slovo „program“ v tomto kontextu spíše znamená optimální sled akcí k dosažení řešení problému. Například konkrétní plán akcí na výstavě se někdy nazývá program. Program je v tomto případě chápán jako platný sled událostí.

Myšlenka dynamického programování

Nalezení nejkratší cesty v grafu z jednoho vrcholu do druhého pomocí optimální podstruktury; přímka označuje jednoduchou hranu; vlnovka označuje nejkratší cestu mezi vrcholy, které spojuje (mezilehlé vrcholy cesty nejsou zobrazeny); Tlustá čára označuje konečnou nejkratší cestu.

Optimální spodní konstrukce v dynamickém programování znamená, že k vyřešení původního problému lze použít optimální řešení menších dílčích problémů. Například nejkratší cestu v grafu z jednoho vrcholu (označeného s) do druhého (označeného t) lze nalézt takto: nejprve vypočítáme nejkratší cestu ze všech vrcholů sousedících s s do t a poté vezmeme s ohledem na váhy hran, které spojují s se sousedními vrcholy, vyberte nejlepší cestu k t (kterým vrcholem je nejlepší projít). Obecně můžeme problém, který má optimální podstrukturu, vyřešit tím, že projdeme následujícími třemi kroky.

1. Rozdělení úkolu na menší dílčí úkoly.
2. Nalezení optimálního řešení dílčích problémů rekurzivně provedením stejného tříkrokového algoritmu.
3. Použití získaného řešení dílčích problémů ke konstrukci řešení původního problému.

Dílčí úkoly se řeší tak, že se rozdělují na dílčí úkoly o ještě menší velikosti atd., dokud se nedospěje k triviálnímu případu problému, který lze vyřešit v konstantním čase (odpověď lze říci ihned). Pokud například potřebujeme najít n!, pak by triviální úloha byla 1! = 1 (nebo 0! = 1).

Překrývající se dílčí úkoly v dynamickém programování znamenají dílčí úkoly, které se používají k řešení řady problémů (nejen jednoho) většího rozsahu (to znamená, že totéž děláme několikrát). Nápadným příkladem je výpočet Fibonacciho posloupnosti a i v takovém triviálním případě jsme již dvakrát počítali výpočet pouze dvou Fibonacciho čísel. Pokud budete pokračovat dále a počítat , pak se to započítá ještě dvakrát, protože výpočet bude vyžadovat a znovu. Stane se, že jednoduchý rekurzivní přístup ztratí čas výpočtem řešení problémů, které již vyřešil.

Abychom se takovému průběhu událostí vyhnuli, uložíme si řešení podproblémů, které jsme již vyřešili, a až budeme řešení podproblému potřebovat znovu, místo opětovného výpočtu jej jednoduše vyvoláme z paměti. Tento přístup se nazývá ukládání do mezipaměti. Můžeme také provádět další optimalizace – například pokud jsme si naprosto jisti, že řešení dílčího úkolu již nebudeme potřebovat, můžeme jej vyhodit z paměti a uvolnit tak pro jiné potřeby, nebo pokud je procesor nečinný a my vědět, že řešení některých dílčích úkolů, které ještě nebyly spočítány, budeme potřebovat v budoucnu, můžeme je vyřešit předem.

Shrneme-li výše uvedené, můžeme říci, že dynamické programování využívá následující vlastnosti problému:

• překrývající se dílčí úkoly;
• optimální spodní stavba;
• schopnost zapamatovat si řešení často se vyskytujících dílčích problémů.

Dynamické programování obecně sleduje dva přístupy k řešení problémů:

• Dynamické programování shora dolů: problém se rozdělí na menší dílčí problémy, ty se vyřeší a poté se spojí, aby se vyřešil původní problém. Memorování se používá k řešení často se vyskytujících dílčích problémů.
• Dynamické programování zdola nahoru: všechny dílčí úkoly, které budou následně potřeba k vyřešení původního problému, jsou předem spočítány a následně použity ke konstrukci řešení původního problému. Tato metoda je z hlediska velikosti potřebného zásobníku a počtu volání funkcí lepší než programování shora dolů, ale někdy není snadné předem vědět, které dílčí problémy budeme muset později vyřešit.

Programovací jazyky si mohou zapamatovat výsledek volání funkce se specifickou sadou argumentů (memoizace), aby se urychlilo „vyhodnocení podle názvu“. Některé jazyky mají tuto funkci vestavěnou (například Scheme, Common Lisp, Perl) a některé vyžadují další rozšíření (C++).

Existují sériové dynamické programování, které je obsaženo ve všech učebnicích operačního výzkumu, a nesériové dynamické programování (NSDP), které je v současnosti málo známé, přestože bylo objeveno v 60. letech 20. století.

Obyčejné dynamické programování je speciální případ nesériového dynamického programování, kdy graf vztahů proměnných je prostě cesta. NSDP, která je přirozenou a obecnou metodou pro zohlednění struktury optimalizačního problému, považuje množinu omezení a/nebo účelovou funkci za rekurzivně vypočítatelnou funkci. To vám umožní najít řešení ve fázích, v každé fázi pomocí informací získaných v předchozích fázích, a účinnost tohoto algoritmu přímo závisí na struktuře grafu vztahů mezi proměnnými. Pokud je tento graf dostatečně řídký, pak lze množství výpočtů v každé fázi udržet v rozumných mezích.

Jednou z hlavních vlastností problémů řešených pomocí dynamického programování je aditivnost. Neaditivní problémy se řeší jinými metodami. Například mnoho problémů optimalizace investic společnosti není aditivní a řeší se porovnáním hodnoty společnosti s investicemi a bez nich.

Klasické problémy dynamického programování

Literatura

• Bellman R. Dynamické programování. - M.: Nakladatelství zahraniční literatury, 1960.
• Cormen, T., Leiserson, C., Rivest, R., Stein, K. Kapitola 15. Dynamické programování // Algoritmy: konstrukce a analýza = Introduction to Algorithms / Ed. I. V. Krasíková. - 2. vyd. - M.: Williams, 2005. - 1296 s. - ISBN 5-8459-0857-4
• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algoritmy = Algoritmy. - 1. vyd. - McGraw-Hill Science/Engineering/Math, 2006. - S. 336. - ISBN 0073523402
• Akulich I.L. Kapitola 4. Problémy dynamického programování// Matematické programování v příkladech a úlohách. - M.: Vyšší škola, 1986. - 319 s. - ISBN 5-06-002663-9.
• Bertele U., Brioshi F. Nesériové dynamické programování. - N.Y.: Academic Press, 1972. - 235 stran.
• Shcherbina O. A. O nesériové modifikaci lokálního dekompozičního algoritmu pro diskrétní optimalizační problémy // Dynamic Systems, 2005, no. 19.
• Shcherbina O. A. Metodologické aspekty dynamického programování // Dynamické systémy, 2007, sv. 22. - str.21-36.
• Gabasov R., Kirillova F. M. Základy dynamického programování. - Mn.: Nakladatelství BSU, 1975. - 262 s.

Odkazy

Nadace Wikimedia. 2010.

Podívejte se, co je "Dynamické programování" v jiných slovnících:

dynamické programování- - [E.S. Alekseev, A.A. Anglicko-ruský vysvětlující slovník o inženýrství počítačových systémů. Moskva 1993] dynamické programování Obor matematického programování, soubor technik, který umožňuje nalézt optimální řešení na základě ... Technická příručka překladatele

Dynamické programování- část matematického programování, soubor technik, které vám umožní najít optimální řešení na základě výpočtu důsledků každého rozhodnutí a vytvoření optimální strategie pro následná rozhodnutí.… … Ekonomický a matematický slovník

Obor matematiky věnovaný teorii a metodám řešení vícekrokových úloh optimálního řízení. V dynamickém řízení pro řízené procesy se mezi všemi možnými řízeními hledá to, které poskytuje extrémní (nejmenší nebo největší) hodnotu... ... Matematická encyklopedie

Obor matematiky věnovaný teorii a metodám řešení vícekrokových problémů optimálního řízení (viz Optimální řízení). V D. p. pro řízené procesy se mezi všemi možnými kontrolami hledá taková, která přináší... ... Velká sovětská encyklopedie

dynamické programování- dinaminis programavimas statusas T sritis automatika atitikmenys: engl. dynamické programování vok. dynamický programovací program, f rus. dynamické programování, n pranc. programmation dynamique, f … Automatikos terminų žodynas

Matematická sekce programování, studium vícekrokových procesů hledání optimálních. řešení složitých problémů. Používá se při vývoji programů pro řešení takových optimalizačních problémů, u kterých může být proces hledání řešení reprezentován formou určitého roje... ... Velký encyklopedický polytechnický slovník

Mezi problémy řešené pomocí matematického programování lze rozlišit samostatnou třídu problémů, které vyžadují optimalizaci vícekrokových (vícestupňových) procesů. Tyto problémy se vyznačují možností rozdělit řešení do několika vzájemně propojených etap. K řešení takových problémů se používá dynamické programování nebo, jak se také nazývá, vícestupňové programování. Jeho metody jsou optimalizovány pro nalezení optimálního řešení vícekrokových problémů, které lze rozdělit do několika fází, kroků atd.

Původ termínu

Použití slova „dynamický“ v názvu původně naznačovalo, že k rozdělení do dílčích úkolů dojde především v čase. Při použití dynamických metod k řešení výrobních, ekonomických a jiných problémů, ve kterých se vyskytuje faktor času, není jeho rozdělení na jednotlivé etapy obtížné. Techniky dynamického programování je ale možné využít i v úlohách, kde jednotlivé fáze časově nesouvisí. Ve vícekrokovém problému můžete vždy vybrat parametr nebo vlastnost, kterou lze použít k rozdělení do samostatných kroků.

Algoritmus (metoda) řešení vícestupňových problémů

Algoritmus nebo metoda dynamického programování je založena na principu sekvenční optimalizace problému, kdy se řešení obecného problému rozdělí na řadu řešení jednotlivých dílčích problémů a následně se spojí do jediného řešení. Velmi často se jednotlivé dílčí problémy ukáží jako stejné a jedno obecné řešení výrazně zkrátí dobu výpočtu.

Charakteristickým rysem metody je autonomie řešení problému v každé jednotlivé fázi, tj. bez ohledu na to, jak byl proces optimalizován a řešen v předchozí fázi, jsou v aktuálním výpočtu použity pouze parametry procesu, které jej v daném okamžiku charakterizují. Například řidič pohybující se po silnici rozhoduje o aktuálním odbočení bez ohledu na to, jak a jak dlouho předtím jel.

Metoda shora a metoda zdola

Navzdory skutečnosti, že při výpočtu v samostatné fázi řešení problému se používají parametry procesu v aktuálním okamžiku, výsledek optimalizace v předchozí fázi ovlivňuje výpočty následujících fází, aby bylo dosaženo nejlepšího výsledku jako celku. Dynamické programování nazývá tento princip řešení metodou optimality, která určuje, že po optimální strategii řešení problému bez ohledu na počáteční rozhodnutí a podmínky musí následovat následná rozhodnutí ve všech fázích, aby se vytvořila optimální strategie vzhledem k výchozímu stavu. Jak vidíme, proces řešení problému je průběžná optimalizace výsledku v každé jednotlivé fázi od první do poslední. Tato metoda se nazývá metoda programování shora dolů. Obrázek schematicky znázorňuje algoritmus řešení shora dolů. Existuje však třída vícestupňových problémů, ve kterých je maximální účinek na poslední fázi již znám, například jsme již dorazili z bodu A do bodu B a nyní chceme zjistit, zda jsme jeli správně při každém předchozím fázi nebo zda se dalo něco udělat optimálněji. Vzniká rekurzivní sekvence fází, to znamená, že jdeme „z opačného směru“. Tato metoda řešení se nazývá „metoda programování zdola nahoru“.

Praktické použití

Dynamické programování lze použít v jakékoli oblasti činnosti, kde existují procesy, které lze rozdělit na řadu shodných malých etap podle nějakého parametru (čas, množství, teplota atd.). Dynamické metody řešení se nejvíce používají v teorii řízení a při vývoji počítačových systémů.

Hledání optimální cesty

Pomocí dynamické optimalizace je možné řešit širokou třídu problémů hledání či optimalizace nejkratší cesty a další problémy, u kterých „klasický“ způsob výčtu možných variant řešení vede k prodloužení doby výpočtu a je někdy zcela nepřijatelný. Klasickým problémem dynamického programování je problém batohu: daný určitý počet objektů s určitou hmotností a cenou a je nutné vybrat sadu objektů s maximální cenou a hmotností, která nepřesahuje objem batohu. Klasické hledání všech možností při hledání optimálního řešení zabere značný čas, ale pomocí dynamických metod je problém vyřešen v přijatelném časovém horizontu. Problémy hledání nejkratší cesty pro dopravní logistiku jsou základní a pro jejich řešení jsou optimálně vhodné dynamické metody řešení. Nejjednodušším příkladem takového úkolu je sestavení nejkratší trasy pomocí automobilové GPS navigace.

Výroba

Dynamické programování je široce používáno při řešení různých výrobních problémů, jako je řízení zásob pro udržení požadovaného počtu komponent v daném čase, plánování výrobního procesu, rutina a generální opravy zařízení, jednotné pracovní vytížení personálu, nejefektivnější distribuce investičních fondů atd. Pro řešení produkčních problémů pomocí metod dynamického programování byly vyvinuty speciální softwarové balíčky, které jsou integrovány do populárních systémů řízení podniku, jako je SAP.

Vědecký obor

Metody dynamického programování jsou široce používány v různých vědeckých výzkumech. Například se úspěšně používají v algoritmech rozpoznávání řeči a obrazu při zpracování velkého množství dat v sociologii a