Dynamické programovanie, základné princípy

Ak chcete zvoliť optimálne riešenie pri plnení úlohy programovaní sú niekedy potrebné triediť veľké objemy dát kombinácie, ktoré načíta pamäti osobného počítača. Takéto spôsoby zahŕňajú, napríklad, programovací metóda "rozdeľuj a panuj". V tomto prípade algoritmus poskytuje problém separácie na jednotlivé menšie čiastkové úlohy. Táto metóda je použiteľná iba v tých prípadoch, kedy malé čiastkové úlohy sú navzájom nezávislé. Aby sa zabránilo zbytočnému vykonávania fungovať, ak na sebe závislých čiastkových úloh, používa dynamické programovanie metódu navrhnutú American R.Bellmanom v 50. rokoch.

metóda

Dynamické programovanie je určiť optimálne riešenie problému n-dimenzionálnej, zdieľanie jej n samostatné etapy. Každý z nich je sub-úloha s ohľadom na jednej premennej.

Hlavnou výhodou tohto prístupu možno považovať, že vývojári zapojené do optimalizačného problému jednorozmerného čiastkových úloh namiesto problému n-rozmerné, a naším hlavným cieľom bude "bottom-up".

Je vhodné aplikovať dynamické programovanie v tých prípadoch, keď sú vzájomne prepojené čiastkové úlohy, tj zdieľať spoločné moduly. Algoritmus poskytuje rozhodnutie každého z čiastkových úloh naraz, a odpovede na úsporu prebieha v špeciálnej tabuľke. To umožňuje, aby výpočet odpoveď, keď sa znovu stretli s rovnakou čiastkové úloha.

Dynamické programovanie úloha rieši problém optimalizácie. Autor tohto spôsobu formuloval princíp optimality R. Bellman: čo je počiatočný stav každého z krokov a riešení definovaného v tomto kroku, všetky nasledujúce zvoliť optimálny vzhľadom na stav, ktorý prijíma systém na konci kroku.

Spôsob zlepšuje výkon úloh riešených pomocou variantov, alebo rekurzia.

Algoritmus úloha Building

Dynamické programovanie algoritmus zahŕňa výstavbu takých úloh, že úloha, takže je rozdelené do dvoch alebo viacerých čiastkových úloh na jeho riešenie sa skladá zo optimálne riešenie pre všetky čiastkové úlohy, to zahŕňa. Ďalej je nutné, aby napísať vzťah opakovanie, a výpočet optimálnej hodnoty parametrov pre túto úlohu ako celok.

Niekedy sa v 3. kroku je zapamätať si niektoré ďalšie základné informácie o priebehu každej úlohy. Tento jav sa nazýva spätný zdvih.

spôsob nanášania

Dynamické programovanie je použitá v prípade, že sú dva charakteristické rysy:

• optimálne pre čiastkové úlohy;
• Prítomnosť v probléme prekrývajúcich subproblems.

Vyriešenie problému optimalizácie pomocou dynamického programovania, je potrebné najprv opísať štruktúru riešenie. Úloha musí byť optimálna, ak je roztok zložený z najlepších rozhodnutí jeho čiastkových úloh. V tomto prípade je vhodné použiť dynamické programovanie.

Druhá vlastnosť tohto problému, ktorý je nevyhnutný pri tejto metóde, - malý počet čiastkových úloh. Rekurzívne riešenie problému s použitím rovnakých prekrývajúce čiastkové problémy, ktorých počet závisí na veľkosti počiatočnej informácie. Odpoveď je uložený v špeciálnej tabuľke, program šetrí čas pomocou týchto dát.

Zvlášť efektívne je použitie, kedy je nevyhnutná úloha rozhodovať v niekoľkých fázach dynamického programovania. Zoberme si napríklad jednoduchý príklad problému výmeny a opravy zariadení. Povedzme, že v továrni liace stroje na výrobu pneumatík v rovnakom čase, aby sa pneumatiky v dvoch rôznych formách. V prípade, že jedna z foriem zlyhania, je nutné demontovať zariadenie. Je pochopiteľné, že niekedy výhodnejšie vymeniť a druhá forma, aby sa demontáže zariadenia v prípade, že aj táto forma bude nevykonateľný v ďalšom stupni. Najmä preto, že je to jednoduchšie vymeniť obaja pracovali tvar, než začnú zlyhávať. Dynamický spôsob programovania určuje najlepšiu stratégiu vo veci náhrady týchto foriem, pričom do úvahy všetky faktory: prínosy ďalšieho foriem vykorisťovania, straty prestoje stroje, náklady na vyradených pneumatík a ďalšie.