動態規劃基本原理

動態程式設計

近年來，涉及動態規劃的各種競賽題越來越多，每一年的noi幾乎都至少有一道題目需要用動態規劃的方法來解決；而競賽對選手運用動態規劃知識的要求也越來越高，已經不再停留於簡單的遞推和建模上了。

要了解動態規劃的概念，首先要知道什麼是多階段決策問題。

一、多階段決策問題

如果一類活動過程可以分為若干個互相聯絡的階段，在每乙個階段都需作出決策(採取措施)，乙個階段的決策確定以後，常常影響到下乙個階段的決策，從而就完全確定了乙個過程的活動路線，則稱它為多階段決策問題。

各個階段的決策構成乙個決策序列，稱為乙個策略。每乙個階段都有若干個決策可供選擇，因而就有許多策略供我們選取，對應於乙個策略可以確定活動的效果，這個效果可以用數量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取乙個最優策略，使在預定的標準下達到最好的效果.

讓我們先來看下面的例子：如圖所示的是乙個帶權有向的多段圖，要求從a到d的最短路徑的長度(下面簡稱最短距離)。

我們可以搜尋，列舉圖中的每條路徑，但當圖的規模大起來時，搜尋的效率顯然不可能盡人意。讓我們來試用動態規劃的思路分析這道題：從圖中可以看到，a點要到達d點必然要經過b1和b2中的乙個，所以a到d的最短距離必然等於b1到d的最短距離加上5，或是b2到d的最短距離加上2。

同樣的，b1到d的最短距離必然等於c1到d的最短距離加上3或是c2到d的最短距離加上2，……。

我們設g[i]為點i到點d的距離，顯然g[c1]=4，g[c2]=3，g[c3]=5，根據上面的分析，有：

g[b1]=min=5，

g[b2]=min=9，

再就有g[a]=min=10，

所以a到d的最短距離是10，最短路徑是ab1c2d。

二、動態規劃的術語

1．階段

把所給求解問題的過程恰當地分成若干個相互聯絡的階段，以便於求解，過程不同，階段數就可能不同．描述階段的變數稱為階段變數。在多數情況下，階段變數是離散的，用k表示。此外，也有階段變數是連續的情形。

如果過程可以在任何時刻作出決策，且在任意兩個不同的時刻之間允許有無窮多個決策時，階段變數就是連續的。

在前面的例子中，第乙個階段就是點a，而第二個階段就是點a到點b，第三個階段是點b到點c，而第四個階段是點c到點d。

2．狀態

狀態表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉移，也稱為不可控因素。在上面的例子中狀態就是某階段的出發位置，它既是該階段某路的起點，同時又是前一階段某支路的終點。

在前面的例子中，第乙個階段有乙個狀態即a，而第二個階段有兩個狀態b1和b2，第三個階段是三個狀態c1，c2和c3，而第四個階段又是乙個狀態d。

過程的狀態通常可以用乙個或一組數來描述，稱為狀態變數。一般，狀態是離散的，但有時為了方便也將狀態取成連續的。當然，在現實生活中，由於變數形式的限制，所有的狀態都是離散的，但從分析的觀點，有時將狀態作為連續的處理將會有很大的好處。

此外，狀態可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態維數可以不同。

當過程按所有可能不同的方式發展時，過程各段的狀態變數將在某一確定的範圍內取值。狀態變數取值的集合稱為狀態集合。

3．無後效性

我們要求狀態具有下面的性質：如果給定某一階段的狀態，則在這一階段以後過程的發展不受這階段以前各段狀態的影響，所有各階段都確定時，整個過程也就確定了。換句話說，過程的每一次實現可以用乙個狀態序列表示，在前面的例子中每階段的狀態是該線路的始點，確定了這些點的序列，整個線路也就完全確定。

從某一階段以後的線路開始，當這段的始點給定時，不受以前線路（所通過的點）的影響。狀態的這個性質意味著過程的歷史只能通過當前的狀態去影響它的未來的發展，這個性質稱為無後效性。

4．決策

乙個階段的狀態給定以後，從該狀態演變到下一階段某個狀態的一種選擇（行動）稱為決策。在最優控制中，也稱為控制。在許多問題中，決策可以自然而然地表示為乙個數或一組數。

不同的決策對應著不同的數值。描述決策的變數稱決策變數，因狀態滿足無後效性，故在每個階段選擇決策時只需考慮當前的狀態而無須考慮過程的歷史。

決策變數的範圍稱為允許決策集合。

5．策略

由每個階段的決策組成的序列稱為策略。對於每乙個實際的多階段決策過程，可供選取的策略有一定的範圍限制，這個範圍稱為允許策略集合。允許策略集合中達到最優效果的策略稱為最優策略。

給定k階段狀態變數x(k)的值後，如果這一階段的決策變數一經確定，第k+1階段的狀態變數x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那麼可以把這一關係看成(x(k)，u(k))與x(k+1)確定的對應關係，用x(k+1)=tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態轉移規律，稱為狀態轉移方程。

6．最優性原理

作為整個過程的最優策略，它滿足：相對前面決策所形成的狀態而言，餘下的子策略必然構成「最優子策略」。

最優性原理實際上是要求問題的最優策略的子策略也是最優。讓我們通過對前面的例子再分析來具體說明這一點：從a到d，我們知道，最短路徑是ab1c2d，這些點的選擇構成了這個例子的最優策略，根據最優性原理，這個策略的每個子策略應是最優：

ab1c2是a到c2的最短路徑，b1c2d也是b1到d的最短路徑……事實正是如此，因此我們認為這個例子滿足最優性原理的要求。

下面我們列舉歷年國內國際競賽的一些典型動態規劃問題加以分析。

機器分配（hnoi95）

一、問題描述

總公司擁有高效生產裝置m臺，準備分給下屬的n個公司。各分公司若獲得這些裝置，可以為國家提供一定的盈利。問：

如何分配這m臺裝置才能使國家得到的盈利最大？求出最大盈利值。其中m《=15，n〈=10。

分配原則：每個公司有權獲得任意數目的裝置，但總台數不得超過總裝置數m。儲存資料的檔名從鍵盤輸入。

資料檔案格式為：第一行儲存兩個數，第乙個數是裝置台數m，第二個數是分公司數n。接下來是乙個m*n的矩陣，表明了第i個公司分配j臺機器的盈利。

二、分析

這是乙個典型的動態規劃試題。用機器數來做狀態，陣列f[i，j]表示前i個公司分配j臺機器的最大盈利。則狀態轉移方程為

f[i，j]=max （0〈=k〈=j〉

三、參考程式：

program hnoi_95_4;

vara , b , c : array[0..15,0..15] of longint;

d : array[0..15] of longint;

n , m : longint;

procedure init;

varfi : text;

i , j , k : integer;

begin

assign(fi,』input.txt』); reset(fi);

readln(fi,m,n);

for i:= 0 to m do

begin

read(fi,j);

for k := 1 to n do

read(fi,a[k,i]);

readln(fi);

end;

close(fi);

end;

procedure dynamic;

var i , j , k : longint;

begin

for i := 1 to n do

for j := 0 to m do

for k := 0 to j do

if b[i-1,k] + a[i,j-k] > b[i,j] then begin

b[i,j] := b[i-1,k] + a[i,j-k];

end;

writeln(fo,b[n,m]);

end;

begin

init;

dynamic;

end.

最長不下降序列（hnoi97）

一、問題描述

設有整數序列b1,b2,b3,…,bm，若存在i1輸入：整數序列

輸出：最大長度n和所有長度為n的序列個數total

二、分析

此題分為兩個部分：求最大不下降序列長度和序列個數。

首先我們考慮求最大長度。設f(i)為前i個數中的最大不下降序列長度。由題意不難得知，要求f(i)，需要求得f(1)—f(i-1)，然後選擇乙個最大的f(j) ( jbj )，那麼前i個數中最大不下降序列便是前j個數中最大不下降序列後新增bi而得。

可見此任務滿足最優子結構，可以用動態規劃解決。

通過上面的分析可得狀態轉移方程如下：

f(i)=max(j 邊界為f(1)=1

顯然只需要求序列個數即可。很容易想到下面的方法：

設total(i)為前i個數中最長不下降序列的個數。

那麼，要求total(i)，只需找到所有的total(j)滿足j total(i)=∑total(j) (j 在求所有的total(i)(f(i)=max)的累加和即可。

但這樣考慮有乙個致命的錯誤，如

1 2 2

這樣乙個序列，最大不下降序列長度為2。但如果按上述方法計算序列1 2會算兩次。因此，我們對演算法進行改進：

對原序列按b從小到大（當bi=bj時按f從大到小）排序，增設order(i)記錄新序列中的i個數在原序列中的位置。可見，當求total(i)時，當f(j)=f(j+1) , b(j)=b(j+1)且order(j+1)

動態規劃基本原理

動態規劃基本原理

廣告基本原理

LTE OFDM 基本原理

動態規劃基本原理

動態規劃基本原理

廣告基本原理

LTE OFDM 基本原理

相關推薦