Dinamikus programozás alapelvei

Kiválasztja az optimális megoldás, ha teljesítenek a programozási feladatok néha szükséges rendezni a nagy mennyiségű adat kombinációk, amely betölti a memória a személyi számítógép. Az ilyen módszerek közé tartozik, például, a programozási módszer a „oszd meg és szabályt”. Ebben az esetben az algoritmus szétválasztás probléma különálló kisebb részfeladatok. Ez a módszer csak akkor alkalmazható azokban az esetekben, amikor a kis részfeladatok egymástól függetlenek. Annak elkerülése érdekében végző felesleges munka, ha függő részfeladat, használja a dinamikus programozási módszert javasolt amerikai R.Bellmanom a 50-es években.

az eljárás

Dinamikus programozás célja, hogy meghatározza az optimális megoldás az n-dimenziós probléma, megosztva vele n külön szakaszban. Mindegyikük egy részfeladat tekintetében az egyik változó.

A fő előnye ennek a megközelítésnek lehet tekinteni, hogy a fejlesztők részt vesznek a egydimenziós optimalizálási probléma részfeladatok helyett egy n-dimenziós probléma, és elsődleges célunk fog „bottom-up”.

Célszerű alkalmazni dinamikus programozási azokban az esetekben, amikor a részfeladatok összefüggenek, azaz közösek modulokat. Az algoritmus a döntést az egyes részfeladatok egyszer, és megtakarítás válaszok végezzük egy speciális asztalon. Ez lehetővé teszi, hogy nem számít a választ, amikor találkoztak újra ugyanazokkal a részfeladat.

Dinamikus programozási feladat megoldja a problémát az optimalizálás. A szerző ezt a módszert fogalmazott R. Bellman optimum elve: bármi is az eredeti állapot az egyes lépéseket, és az oldatot az ebben a lépésben az összes alábbi választani az optimális kapcsolatban az állam, amely megkapja a rendszer végén lépést.

A módszer javítja a teljesítményt a feladatok megoldása az variánsok, vagy a rekurziót.

Az épület feladat algoritmusa

Dinamikus programozási algoritmust magában foglalja az építés ilyen feladatokat a feladat úgy van osztva két vagy több részfeladatot hogy a megoldás áll az optimális megoldást minden részfeladatot, ez magában foglalja. Továbbá szükség van levelet rekurzív sorozat, és kiszámítjuk az optimális paraméterek értékeit a feladat egészét.

Néha, a 3. lépésben, hogy memorizálni néhány további háttér-információkat a haladás minden egyes feladat. Ezt nevezik a visszatérő löket.

Alkalmazási módszer

Dinamikus programozás alkalmazzák, ha van két jellegzetessége:

• optimális részfeladatok;
• jelenlétét a problémát átfedő részfeladatok.

Megoldása optimalizálási probléma dinamikus programozás, akkor először meg kell leírni a szerkezet a megoldás. A feladat kell, hogy legyen az optimális, ha az oldat összetétele a legjobb határozatait részfeladatok. Ebben az esetben célszerű használni, dinamikus programozás.

A második tulajdonság a probléma, nélkülözhetetlen ez a módszer - kis számú részfeladat. Rekurzív megoldás a problémára ugyanazt átfedő al-problémák, amelyek száma függ a méret a kezdeti információk. A válasz tároljuk külön táblázatban, a program időt takarít meg az adatokat.

Különösen hatékony a dinamikus programozás, ha a feladat lényegében döntésekhez szükséges a szakaszban. Vegyük például egy egyszerű példát a probléma cseréje és javítása. Tegyük fel, hogy az öntvény gép gyárban a termelés gumiabroncsok ugyanakkor, hogy az abroncs két különböző formában. Abban az esetben, ha valamelyik formában nem sikerül, meg kell szétszedni a készüléket. Érthető, hogy néha jobban megéri cserélni, és egy második formát annak érdekében, hogy szedje szét a készüléket abban az esetben, és ebben a formában lesz kivitelezhetetlen a következő szakaszba. Különösen azért, mert ez könnyebb cserélni mindkét dolgozó alakja, mielőtt elkezdenek nem. Dinamikus programozás módszerrel a legjobb stratégia az ügyben a csere ezen formák, figyelembe véve az összes tényezőt: a kezelés folytatásának kizsákmányolás, elvesztése gép leállás, a költségek eldobott gumiabroncsokat és így tovább.