最優(yōu)化原理
1951年美國數(shù)學(xué)家R．Bellman等人，根據(jù)一類多階段問題的特點(diǎn)，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然后逐個(gè)加以解決。一些靜態(tài)模型，只要人為地引進(jìn)“時(shí)間”因素，分成時(shí)段，就可以轉(zhuǎn)化成多階段的動(dòng)態(tài)模型，用動(dòng)態(tài)規(guī)劃方法去處理。與此同時(shí)，他提出了解決這類問題的“最優(yōu)化原理”(Principle of optimality)：
“一個(gè)過程的最優(yōu)決策具有這樣的性質(zhì)：即無論其初始狀態(tài)和初始決策如何，其今后諸策略對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)的過程而言，必須構(gòu)成最優(yōu)策略”。簡言之，一個(gè)最優(yōu)策略的子策略，對(duì)于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。
這個(gè)“最優(yōu)化原理”如果用數(shù)學(xué)化一點(diǎn)的語言來描述的話，就是：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1，D2，…，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k，1 < k < n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng)前狀態(tài)，即以后的決策Dk+1，Dk+2，…，Dn也是最優(yōu)的。
最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問題，如果失去了這個(gè)最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)規(guī)劃求解的問題都需要滿足一定的條件：
(1) 問題中的狀態(tài)必須滿足最優(yōu)化原理；
(2) 問題中的狀態(tài)必須滿足無后效性。
所謂的無后效性是指：“下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無關(guān)，當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)”。
問題求解模式
動(dòng)態(tài)規(guī)劃所處理的問題是一個(gè)多階段決策問題，一般由初始狀態(tài)開始，通過對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。
初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
圖1 動(dòng)態(tài)規(guī)劃決策過程示意圖
(1)劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。
(2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。
(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來確定決策。
(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。
算法實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡單。使用動(dòng)態(tài)規(guī)劃求解問題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：問題的階段,每個(gè)階段的狀態(tài)以及從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過程就可以用一個(gè)最優(yōu)決策表來描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對(duì)應(yīng)此問題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值（如最短路徑，最長公共子序列，最大價(jià)值等），填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過簡單的取舍或者運(yùn)算求得問題的最優(yōu)解。下面分別以求解最大化投資回報(bào)問題和最長公共子序列問題為例闡述用動(dòng)態(tài)規(guī)劃算法求解問題的一般思路。
1. 最大化投資回報(bào)問題：某人有一定的資金用來購買不同面額的債卷，不同面額債卷的年收益是不同的，求給定資金，年限以及債卷面額、收益的情況下怎樣購買才能使此人獲得最大投資回報(bào)。
程序輸入約定：第一行第一列表示資金（1000的倍數(shù)）總量，第二列表示投資年限；第二行表示債卷面額總數(shù)；從第三行開始每行表示一種債卷，占用兩列，前一列表示債卷面額，后一列表示其年收益，如下輸入實(shí)例，
10000 1
2
4000 400
3000 250
程序?qū)崿F(xiàn)如下，注釋幾乎說明了一切，所以不再另外分析。
/// 此數(shù)組是算法的關(guān)鍵存儲(chǔ)結(jié)構(gòu)，用來存儲(chǔ)不同階段各種債卷
/// 組合下對(duì)應(yīng)可獲取的最大利息。
int saifa[80005];
/// 此函數(shù)用于計(jì)算當(dāng)前債卷在不同購買額下的最優(yōu)利息情況，
/// 注意此時(shí)的利息情況是基于上一次債卷的情況下計(jì)算得到的，
/// 也就是說當(dāng)前利息最優(yōu)是基于上一次利息最優(yōu)的基礎(chǔ)上計(jì)算出來的，
/// 這也正好體現(xiàn)了動(dòng)態(tài)規(guī)劃中“最優(yōu)化原則”：不管前面的策略如何，
/// 此后的決策必須是基于當(dāng)前狀態(tài)（由上一次決策產(chǎn)生）的最優(yōu)決策。
/*
動(dòng)態(tài)規(guī)劃的求解過程一般都可以用一個(gè)最優(yōu)決策表來描述，
對(duì)于本程序，以示例輸入為例，對(duì)于第一年，其最優(yōu)決策表如下：
0 1 2 3 4 5 6 7 8 9 10(*1000) -- (1)
0 0 0 0 400 400 400 400 800 800 800 -- (2)
0 0 0 250 400 400 500 650 800 900 900 -- (3)
(1) -- 表示首先選利息為400的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。
(2) -- 表示可用來購買債卷的資金。
(3) -- 表示在已有狀態(tài)下再選擇利息為300的債卷在對(duì)應(yīng)資金下的最優(yōu)利息。
注意上面表格，在求購買利息為300的債卷獲得的最優(yōu)收益的時(shí)候，
參考了以前的最優(yōu)狀態(tài)，以3行8列的650為例，7(*1000)可以
在以前購買了0張4000的債卷的基礎(chǔ)上再2張3000的，也可以在以前購
買了1張4000的基礎(chǔ)上再買1張3000，經(jīng)比較取其收益大的，這就是典
型的動(dòng)態(tài)規(guī)劃中的當(dāng)前最優(yōu)狀態(tài)計(jì)算。
本程序中把上面的最優(yōu)決策二維表用一個(gè)一維數(shù)組表示，值得借鑒。
*/
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]) // 累計(jì)同時(shí)購買多種債卷時(shí)的利息
{
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<n;ii++)
{
memset(saifa,0,sizeof(saifa));
scanf("%d%d",&money,&year);
scanf("%d",&d);
for(i=0;i<d;i++)
{
scanf("%d%d",&pay,&bond);
add(pay/1000,bond);
}
// 計(jì)算指定年限內(nèi)最優(yōu)組合的本金利息總額
for(i=0;i<year;i++)
{ cout << saifa[money/1000] << " "; // for debug
money += saifa[money/1000];
}
cout << endl; // for debug
printf("%d\n",money);
}
return 0;
}
上述程序?qū)崿F(xiàn)方法同樣適合于背包問題，最優(yōu)庫存問題等，只是針對(duì)具體情況，最優(yōu)決策表的表示和生成會(huì)有所不同。
2. 最長公共子串問題：一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。給定兩個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。最長公共子串就是求給定兩個(gè)序列的一個(gè)最長公共子序列。例如，X=“ABCBDAB”，Y=“BCDB”是X的一個(gè)子序列。
問題分析：
給定兩個(gè)序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。如采用列舉A的所有子序列，并一一檢查其是否又是B的子序列，并隨時(shí)記錄所發(fā)現(xiàn)的子序列，最終求出最長公共子序列。這種方法因耗時(shí)太多而不可取。
考慮最長公共子序列問題如何分解成子問題，設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質(zhì)：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個(gè)最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊(yùn)涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長公共子序列。
這樣，在找A和B的公共子序列時(shí)，如有am-1=bn-1，則進(jìn)一步解決一個(gè)子問題，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一個(gè) 最長公共子序列；如果am-1!=bn-1，則要解決兩個(gè)子問題，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個(gè)最長公共子序列 和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個(gè)最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
為了節(jié)約重復(fù)求相同子問題的時(shí)間，引入一個(gè)數(shù)組，不管它們是否對(duì)最終解有用，把所有子問題的解存于該數(shù)組中，這就是動(dòng)態(tài)規(guī)劃法所采用的基本方法，具體說明如下。
定義c[i][j]為序列“a0，a1，…，ai-2”和“b0，b1，…，bj-1”的最長公共子序列的長度，計(jì)算c[i][j]可遞歸地表述如下：
（1）c[i][j] = 0 如果i=0或j=0；
（2）c[i][j] = c[i-1][j-1]+1 如果i,j>0，且a[i-1] = b[j-1]；
（3）c[i][j] = max{c[i][j-1], c[i-1][j]} 如果i,j>0，且a[i-1] != b[j-1]。
按此算式可寫出計(jì)算兩個(gè)序列的最長公共子序列的長度函數(shù)。由于c[i][j]的產(chǎn)生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以從c[m][n]開始，跟蹤c[i][j]的產(chǎn)生過程，逆向構(gòu)造出最長公共子序列。細(xì)節(jié)見程序。
#include <stdio.h>
#include <string.h>
#define N 100
char a[N], b[N], str[N];
int c[N][N];
int lcs_len(char* a, char* b, int c[][N])
{
int m = strlen(a), n = strlen(b), i, j;
for( i=0; i<=m; i++ )
c[i][0]=0;
for( i=0; i<=n; i++ )
c[0][i]=0;
for( i=1; i<=m; i++ )
{
for( j=1; j<=n; j++ )
{
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
return c[m][n];
}
char* build_lcs(char s[], char* a, char* b)
{
int i = strlen(a), j = strlen(b);
int k = lcs_len(a,b,c);
s[k] = '\0';
while( k>0 )
{
if (c[i][j]==c[i-1][j])
i--;
else if (c[i][j]==c[i][j-1])
j--;
else
{
s[--k]=a[i-1];
i--; j--;
}
}
return s;
}
void main()
{
printf("Enter two string (length < %d) :\n",N);
scanf("%s%s",a,b);
printf("LCS=%s\n",build_lcs(str,a,b));
}