動態(tài)規(guī)劃

什么是動態(tài)規(guī)劃？

動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方法。所謂“動態(tài)”，指的是在問題的多階段決策中，按某一順序，根據(jù)每一步所選決策的不同，將隨即引起狀態(tài)的轉(zhuǎn)移，最終在變化的狀態(tài)中產(chǎn)生一個決策序列。動態(tài)規(guī)劃就是為了使產(chǎn)生的決策序列在符合某種條件下達(dá)到最優(yōu)。

一、動態(tài)規(guī)劃中的主要概念，名詞術(shù)語

1 階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。
2 狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。通常一個階段包含若干狀態(tài)。如圖1中，階段3就有三個狀態(tài)結(jié)點(diǎn)4、5、6。
3 決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(tài)的選擇。
4策略：由開始到終點(diǎn)的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。
5 狀態(tài)轉(zhuǎn)移方程：前一階段的終點(diǎn)就是后一階段的起點(diǎn)，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。
6 目標(biāo)函數(shù)與最優(yōu)化概念：目標(biāo)函數(shù)是衡量多階段決策過程優(yōu)劣的準(zhǔn)則。最優(yōu)化概念是在一定條件下找到一個途徑，經(jīng)過按題目具體性質(zhì)所確定的運(yùn)算以后，使全過程的總效益達(dá)到最優(yōu)。

二、動態(tài)規(guī)劃問題的數(shù)學(xué)描述

首先，例舉一個典型的且很直觀的多階段決策問題:
[例] 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費(fèi)用，單向通行由
A->E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出 A->E 的最省費(fèi)用。

如圖從 A 到 E 共分為 4 個階段，即第一階段從 A 到 B，第二階段從 B 到 C，
第三階段從 C 到 D，第四階段從 D 到 E。除起點(diǎn) A 和終點(diǎn) E 外，其它各點(diǎn)既是上
一階段的終點(diǎn)又是下一階段的起點(diǎn)。例如從 A 到 B 的第一階段中，A 為起點(diǎn)，終
點(diǎn)有 B1，B2，B3 三個，因而這時走的路線有三個選擇，一是走到 B1，一是走到
B2，一是走到 B3。若選擇 B2 的決策，B2 就是第一階段在我們決策之下的結(jié)果，
它既是第一階段路線的終點(diǎn)，又是第二階段路線的始點(diǎn)。在第二階段，再從 B2
點(diǎn)出發(fā)，對于 B2 點(diǎn)就有一個可供選擇的終點(diǎn)集合(C1，C2，C3)；若選擇由 B2
走至 C2 為第二階段的決策，則 C2 就是第二階段的終點(diǎn)，同時又是第三階段的始
點(diǎn)。同理遞推下去，可看到各個階段的決策不同，線路就不同。很明顯，當(dāng)某階
段的起點(diǎn)給定時，它直接影響著后面各階段的行進(jìn)路線和整個路線的長短，而后 面各階段的路線的發(fā)展不受這點(diǎn)以前各階段的影響。故此問題的要求是：在各個
階段選取一個恰當(dāng)?shù)臎Q策，使由這些決策組成的一個決策序列所決定的一條路
線，其總路程最短。

三、 運(yùn)用動態(tài)規(guī)劃需符合的條件

任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同理，動態(tài)規(guī)劃也并不是萬能的。那么使用動態(tài)規(guī)劃必須符合什么條件呢？必須滿足最優(yōu)化原理和無后效性。

1 最優(yōu)化原理

最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀
態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。

2 無后效性

“過去的步驟只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是歷史的總結(jié)”。這條特征說明動態(tài)規(guī)劃只適用于解決當(dāng)前決策與過去狀態(tài)無關(guān)的問題。狀態(tài)，出現(xiàn)在策略任何一個位置，它的地位相同，都可實施同樣策略，這就是無后效性的內(nèi)涵。
由上可知，最優(yōu)化原理，無后效性，是動態(tài)規(guī)劃必須符合的兩個條件。

四 、動態(tài)規(guī)劃的計算方法

對于一道題，怎樣具體運(yùn)用動態(tài)規(guī)劃方法呢？

（1）首先，分析題意，考察此題是否滿足最優(yōu)化原理與無后效性兩個條件。
（2）接著，確定題中的階段，狀態(tài)，及約束條件。
（3）推導(dǎo)出各階段狀態(tài)間的函數(shù)基本方程，進(jìn)行計算。

應(yīng)用舉例：數(shù)字三角形（洛谷-P1216）

題目描述
觀察下面的數(shù)字金字塔。

寫一個程序來查找從最高點(diǎn)到底部任意處結(jié)束的路徑，使路徑經(jīng)過數(shù)字的和最大。每一步可以走到左下方的點(diǎn)也可以到達(dá)右下方的點(diǎn)。

7 3 8 8 1 0

2 7 4 4
4 5 2 6 5
在上面的樣例中,從 7 \to 3 \to 8 \to 7 \to 57→3→8→7→5 的路徑產(chǎn)生了最大

輸入格式
第一個行一個正整數(shù) rr ,表示行的數(shù)目。

后面每行為這個數(shù)字金字塔特定行包含的整數(shù)。

輸出格式
單獨(dú)的一行,包含那個可能得到的最大的和。

輸入輸出樣例
輸入：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
輸出
30

思路：

@順推：

F[i+1][j] = MAX (F[i][j] + a[i+1][j]);

F[i+1][j+1] = MAX (F[i][j] + a[i+1][j+1]);

@ 逆推：

F[i][j] = MAX (F[i-1][j], F[i-1][j-1]) + a[i][j]; (注意！逆推時要注意邊界情況！ )

代碼如下：
1、順推：

//T2:數(shù)字金字塔-順推（有點(diǎn)類似于記憶化搜索的思路） //d數(shù)組儲存順序：記錄從頂端向底部走的路徑最優(yōu)值（自頂向下）#include<iostream> #include<string.h> using namespace std; int a[1005][1005];//儲存數(shù)塔 int d[1005][1005];//從該點(diǎn)到底端的最大數(shù)字和 int main() {int i,j,n,ans;while(cin>>n){memset(d,-1,sizeof(d));for(i=0;i<n;i++)for(j=0;j<=i;j++){cin>>a[i][j];}d[0][0]=a[0][0];for(int i=0;i<n-1;++i)for(int j=0;j<=i;++j)//d數(shù)組為最優(yōu)值路徑（黑色金字塔，a為源數(shù)據(jù)數(shù)組（紫色金字塔）{//分別用最優(yōu)值來更新左下方和右下方d[i+1][j]=max(d[i+1][j],d[i][j]+a[i+1][j]);//和當(dāng)前的f[i+1][j]比較d[i+1][j+1]=max(d[i+1][j+1],d[i][j]+a[i+1][j+1]);//和當(dāng)前的f[i+1][j+1]比較}//答案可能是最后一行的任意一個，所以把最后一行搜索一遍，最大的賦給ansans=0;for(int i=0;i<n;i++)ans=max(ans,d[n-1][i]);cout<<ans<<endl;for(int i=0;i<n;++i){for(int j=0;j<=i;++j){cout<<d[i][j]<<" ";}cout<<endl;}}return 0; }

2、逆推

//數(shù)字金字塔-逆推 //d數(shù)組儲存順序：記錄從頂端向底部走的路徑最優(yōu)值（自頂向下） #include<iostream> #include<string.h> using namespace std; int a[1005][1005];//儲存數(shù)塔 int d[1005][1005];//從該點(diǎn)到底端的最大數(shù)字和 int main() {int i,j,n,ans;while(cin>>n){memset(d,-1,sizeof(d));for(i=0;i<n;i++)for(j=0;j<=i;j++){cin>>a[i][j];}//逆推（自頂向下）d[0][0]=a[0][0];for(int i=1;i<n;i++){d[i][0]=d[i-1][0]+a[i][0];//最左的位置沒有左上方d[i][i]=d[i-1][i-1]+a[i][i];//最右的位置沒有右上方for(int j=0;j<=i;j++)//在左上方和右上方取較大的d[i][j]=max(d[i-1][j-1],d[i-1][j])+a[i][j];}//答案可能是最后一行的任意一個，所以把最后一行搜索一遍，最大的賦給ansans=0;for(int i=0;i<n;i++)ans=max(ans,d[n-1][i]);cout<<ans<<endl;;for(int i=0;i<n;++i){for(int j=0;j<=i;++j){cout<<d[i][j]<<" ";}cout<<endl;}}return 0; }

附注：

動態(tài)規(guī)劃相比較于深度搜索算法是一種高效算法。若能成功運(yùn)用，必會使程序效率，無論時間還是空間，都有著質(zhì)的飛躍。

掌握好動態(tài)規(guī)劃，關(guān)鍵還是在于理解動態(tài)規(guī)劃算法的基礎(chǔ)上，多找一些相關(guān)的題進(jìn)行練習(xí)。

總結(jié)

以上是生活随笔為你收集整理的NOIP竞赛学习整理--动态规划算法举例P1264的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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