最優化原理

1951年美國數學家R．Bellman等人，根據一類多階段問題的特點，把多階段決策問題變換為一系列互相聯繫的單階段問題，然後逐個加以解決。一些靜態模型，只要人為地引進“時間”因素，分成時段，就可以轉化成多階段的動態模型，用動態規劃方法去處理。與此同時，他提出了解決這類問題的“最優化原理”(Principle of optimality)：

“一個過程的最優決策具有這樣的性質：即無論其初始狀態和初始決策如何，其今後諸策略對以第一個決策所形成的狀態作為初始狀態的過程而言，必須構成最優策略”。簡言之，一個最優策略的子策略，對於它的初態和終態而言也必是最優的。

這個“最優化原理”如果用數學化一點的語言來描述的話，就是：假設為了解決某一優化問題，需要依次作出n個決策D1，D2，…，Dn，如若這個決策序列是最優的，對於任何一個整數k，1 < k < n，不論前面k個決策是怎樣的，以後的最優決策只取決於由前面決策所確定的當前狀態，即以後的決策Dk+1，Dk+2，…，Dn也是最優的。

最優化原理是動態規劃的基礎。任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。能採用動態規劃求解的問題都需要滿足一定的條件：

(1) 問題中的狀態必須滿足最優化原理；

(2) 問題中的狀態必須滿足無後效性。

所謂的無後效性是指：“下一時刻的狀態只與當前狀態有關，而和當前狀態之前的狀態無關，當前的狀態是對以往決策的總結”。

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

圖1 動態規劃決策過程示意圖

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

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

(3)確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩段各狀態之間的關係來確定決策。

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

動態規劃的主要難點在於理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的 階段,每個階段的 狀態以及從前一個階段轉化到后一個階段之間的 遞推關係。遞推關係必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重複計算，所以對於大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃演演算法的核心之處。確定了動態規劃的這三要素，整個求解過程就可以用一個 最優決策表來描述，最優決策表示一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關係，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。下面分別以求解最大化投資回報問題和最長公共子序列問題為例闡述用動態規劃演演算法求解問題的一般思路。

實例：

最大化投資回報問題

某人有一定的資金用來購買不同面額的債卷，不同面額債卷的年收益是不同的，求給定資金，年限以及債卷面額、收益的情況下怎樣購買才能使此人獲得最大投資回報。

程序輸入約定：第一行第一列表示資金（1000的倍數）總量，第二列表示投資年限；第二行表示債卷面額總數；從第三行開始每行表示一種債卷，佔用兩列，前一列表示債卷面額，后一列表示其年收益，如下輸入實例，

10000 1

2

4000 400

3000 250

程序實現如下，註釋幾乎說明了一切，所以不再另外分析。

/// 此數組是演演算法的關鍵存儲結構，用來存儲不同階段各種債卷

/// 組合下對應可獲取的最大利息。

int saifa[80005];

/// 此函數用於計算當前債卷在不同購買額下的最優利息情況，

/// 注意此時的利息情況是基於上一次債卷的情況下計算得到的，

/// 也就是說當前利息最優是基於上一次利息最優的基礎上計算出來的，

/// 這也正好體現了動態規劃中“最優化原則”：不管前面的策略如何，

/// 此後的決策必須是基於當前狀態（由上一次決策產生）的最優決策。

void add(int a,int b)

{

cout << a << " " << b << endl; // for debug

for(int i=0;i<=80000;i++)

{

if(i+a > 80000)

{

break;

}

if(saifa[i]+b > saifa[i+a]) // 累計同時購買多種債卷時的利息

{

saifa[i+a] = saifa[i] + b;

}

if(i<200) // for debug

cout << i << "-"<< saifa[i] << " ";

}

cout << endl; // for debug

}

int main(void)

{

int n,d,money,year,pay,bond;

int ii,i;

scanf("%d",&n);

for(ii=0;ii

{

memset(saifa,0,sizeof(saifa));

scanf("%d%d",&money,&year);

scanf("%d",&d);

for(i=0;i

{

scanf("%d%d",&pay,&bond);

add(pay/1000,bond);

}

// 計算指定年限內最優組合的本金利息總額

for(i=0;i

{

cout << saifa[money/1000]<< " "; // for debug

money += saifa[money/1000];

}

cout << endl; // for debug

printf("%d\n",money);

}

return 0;

}

上述程序實現方法同樣適合於背包問題，最優庫存問題等，只是針對具體情況，最優決策表的表示和生成會有所不同。