動(dòng)態(tài)規(guī)劃算法

1、動(dòng)態(tài)規(guī)劃（一）、動(dòng)態(tài)規(guī)劃的基本思想：動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重

2、復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。二、設(shè)計(jì)動(dòng)態(tài)規(guī)劃法的步驟：1、找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值（寫(xiě)出動(dòng)態(tài)規(guī)劃方程）；3、以自底向上的

3、方式計(jì)算出最優(yōu)值；4、根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟13是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。三、動(dòng)態(tài)規(guī)劃問(wèn)題的特征：動(dòng)態(tài)規(guī)劃算法的有效性依賴于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)。1、最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最

4、優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問(wèn)題的解。（二）、動(dòng)態(tài)規(guī)劃算法的基本步驟優(yōu)指標(biāo)12.輸出t但是，實(shí)際應(yīng)用當(dāng)中經(jīng)常不顯式地按照上面步驟設(shè)計(jì)動(dòng)態(tài)規(guī)劃，而是按以下幾個(gè)步驟進(jìn)行：2.分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。3.遞歸地定義最優(yōu)值。

5、4.以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計(jì)算出最優(yōu)值。5.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟(1)(3)是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟(4)可以省略，若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟(4)。此時(shí)，在步驟(3)中計(jì)算最優(yōu)值時(shí)，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。（三）、動(dòng)態(tài)規(guī)劃概述1.基本思想：將問(wèn)題分解為若干小問(wèn)題，解子問(wèn)題，

6、然后從子問(wèn)題得到原問(wèn)題的解。2.特點(diǎn)：將問(wèn)題分解為子問(wèn)題，這些子問(wèn)題往往不相互獨(dú)立。（如果可以用分治法求解，分解的子問(wèn)題太多，因此，用分治法時(shí)間代價(jià)太高，消耗指數(shù)時(shí)間）3.且某些子問(wèn)題可能被重復(fù)多次計(jì)算，因此將計(jì)算過(guò)的子問(wèn)題的結(jié)果保存。一般，放入表中。4.應(yīng)用：往往求解具有某種最優(yōu)性質(zhì)的問(wèn)題，此類問(wèn)題往往具有多個(gè)解，我們要找到具有最優(yōu)值的那個(gè)解。5.步驟：找出最優(yōu)解的性質(zhì)，刻畫(huà)其特征；遞歸地定義最優(yōu)值；以自底向上的方式計(jì)算出最優(yōu)值；根據(jù)