動態(tài)規(guī)劃--簡單的理解

???? ?這個算法簡單的來講就是采用自底向上的方式遞推求值，將待求解的問題分解成若干個子問題，先求解子問題，并把子問題的解存儲起來以便以后用來計算所需要求的解。簡言之，動態(tài)規(guī)劃的基本思想就是把全局的問題化為局部的問題，為了全局最優(yōu)必須局部最優(yōu)。

???? 多階段決策問題是根據(jù)問題本身的特點，將其求解的過程劃分為若干個相互獨立又相互聯(lián)系的階段，在每一個階段都需要做出決策，并且在一個階段的決策確定以后再轉(zhuǎn)移到下一個階段，在每一階段選取其最優(yōu)決策，從而實現(xiàn)整個過程總體決策最優(yōu)的目的。

一、基本概念

?? ?動態(tài)規(guī)劃過程是：每次決策依賴于當前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。

二、基本思想與策略

?? ?基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

?? ?由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個特點，為減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。

?? ?與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎(chǔ)上，進行進一步的求解）。

?

---

?

三、適用的情況

能采用動態(tài)規(guī)劃求解的問題的一般要具有3個性質(zhì)：

??? (1) 最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。

??? (2) 無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關(guān)。

?? （3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢）

?

---

?

四、求解的基本步驟

?? ? 動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟。

??? 初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)

?? ? ? ? ? ? ? ? ? ? ?圖1 動態(tài)規(guī)劃決策過程示意圖

??? (1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。

??? (2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。

??? (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上常常是反過來做，根據(jù)相鄰兩個階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。

??? (4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

?? ?一般，只要解決問題的階段、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了，就可以寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。

??? 但是，實際應(yīng)用當中經(jīng)常不顯式地按照下面標準動態(tài)規(guī)劃的基本框架步驟設(shè)計動態(tài)規(guī)劃，而是按以下幾個步驟進行：??
??????????1.?分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。??
????????? 2.?遞歸地定義最優(yōu)值。?
????????? 3.?以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。?
????????? 4.?根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。??
????步驟(1)--(3)是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟(4)可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟(4)。此時，在步驟(3)中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟(4)中，根據(jù)所記錄的信息，快速地構(gòu)造出一個最優(yōu)解。?

---

?

五、算法實現(xiàn)的說明

??? 動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，也就是上面4個步驟的確定，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。

?? ? 使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：

?? ?（1）問題的階段 （2）每個階段的狀態(tài)

?? ?（3）從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系。

?? ? 遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個角度來說，動態(tài)規(guī)劃往往可以用遞歸程序來實現(xiàn)，不過因為遞推可以充分利用前面保存的子問題的解來減少重復(fù)計算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也是動態(tài)規(guī)劃算法的核心之處。

?? ?確定了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得問題的最優(yōu)解。

?? ? ? ? ?f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

?

---

六、動態(tài)規(guī)劃算法基本框架

1 for(j=1; j<=m; j=j+1)// 第一個階段
2 ????? xn[j]= 初始值;
4 ?for(i=n-1; i>=1; i=i-1)// 其他n-1個階段
5 ????? for(j=1; j>=f(i); j=j+1)//f(i)與i有關(guān)的表達式
6?????????????? xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
9? t = g(x1[j1:j2]); // 由子問題的最優(yōu)解求解整個問題的最優(yōu)解的方案
11 print(x1[j1]);
13 for(i=2; i<=n-1; i=i+1）
15 {
17??????t = t-xi-1[ji];
19???? for(j=1; j>=f(i); j=j+1)
21??????????? if(t=xi[ji])
23?????????????? break;
25 }

標準動態(tài)規(guī)劃的基本框架：
1.?對fn+1(xn+1)初始化;?{邊界條件}
2.?for?k:=n?downto?1?do?
3.?for?每一個xk∈Xk?do
4.?for?每一個uk∈Uk(xk)?do??begin
5.?fk(xk):=一個極值;? {∞或－∞}
6.?xk+1:=Tk(xk,uk);? {狀態(tài)轉(zhuǎn)移方程}
7.?t:=φ(fk+1(xk+1),vk(xk,uk));?{基本方程(9)式}
8.?if?t比fk(xk)更優(yōu)?then?fk(xk):=t;?{計算fk(xk)的最優(yōu)值}
?end;?
9.?t:=一個極值;?{∞或－∞}
10.?for?每一個x1∈X1?do
11.?if?f1(x1)比t更優(yōu)?then?t:=f1(x1);?{按照10式求出最優(yōu)指標}
12.?輸出t;? ?

一道典型的動態(tài)規(guī)劃題以及解法：

一.題目

題目描述:
Flute市的Phlharmoniker樂團2000年準備到Harp市做一次大型演出,本著普及古典音樂的目的,樂團指揮L.Y.M準備 在到達Harp市之前先在周圍一些小城市作一段時間的巡回演出,此后的幾天里,音樂家們將每天搭乘一個航班從一個城市飛到另一個城市,最后才 到達目的地Harp市(樂團可多次在同一城市演出).
由于航線的費用和班次每天都在變,城市和城市之間都有一份循環(huán)的航班表,每一時間,每一方向,航班表循環(huán)的周期都可能不同.現(xiàn)要求尋找一張花 費費用最小的演出表.

輸入:
輸入文件包括若干個場景.每個場景的描述由一對整數(shù)n(2<=n<=10)和k(1<=k<=1000)開始,音樂 家們要在這n個城市作巡回演出,城市用1..n標號,其中1是起點Flute市,n是終點Harp市,接下來有n*(n-1)份航班表,一份 航班表一行,描述每對城市之間的航線和價格,第一組n-1份航班表對應(yīng)從城市1到其他城市(2,3,...n)的航班,接下的n-1行是從城 市2到其他城市(1,3,4...n)的航班,如此下去.
每份航班又一個整數(shù)d(1<=d<=30)開始,表示航班表循環(huán)的周期,接下來的d個非負整數(shù)表示1,2...d天對應(yīng)的兩個城 市的航班的價格,價格為零表示那天兩個城市之間沒有航班.例如"375 0 80"表示第一天機票價格是75KOI,第二天沒有航班,第三 天的機票是80KOI,然后循環(huán):第四天又是75KOI,第五天沒有航班,如此循環(huán).輸入文件由n=k=0的場景結(jié)束.

輸出:
對每個場景如果樂團可能從城市1出發(fā),每天都要飛往另一個城市,最后(經(jīng)過k天)抵達城市n,則輸出這k個航班價格之和的最小值.如果不可能 存在這樣的巡回演出路線,輸出0.

樣例輸入:
3 6
2 130 150
3 75 0 80
7 120 110 0 100 110 120 0
4 60 70 60 50
3 0 135 140
2 70 80
2 3
2 0 70
1 80
0 0

樣例輸出:
460
0

二. ? ? 題目分析

這道題題目求解最優(yōu)值,很容易想到動態(tài)規(guī)劃,因為第i天在第j個地方的最優(yōu)值只與第i-1天有關(guān),符合動態(tài)規(guī)劃的無后效性原則,即只與上一個狀態(tài)相關(guān)聯(lián),而某一天x航班價格不難求出Value=t[(x-1) mod num +1]. 我們用天數(shù)和地點來規(guī)劃,用一個數(shù)組A[1001][11]來存儲,A[i][j]表示第i天到達第j個城市的最優(yōu)值,C[i][j].t[1]表示i城市與j城市間第1天航班價格,則A[i][j]=Min{A[i-1][s]+C[s][j].t[i] (s=1~n且C[s][j].t[i]!=0)}。

三. 解法1

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的五大算法之二--动态规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。