一、什么是動(dòng)態(tài)規(guī)劃算法
動(dòng)態(tài)規(guī)劃算法是通過(guò)拆分問(wèn)題,定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系,使得問(wèn)題能夠以遞推(或者說(shuō)分治)的方式去解決。
動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類(lèi)似,也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題(階段),按順序求解子階段,前一子問(wèn)題的解,為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí),列出各種可能的局部解,通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解,丟棄其他局部解。依次解決各子問(wèn)題,最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
二、動(dòng)態(tài)規(guī)劃算法的實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì),也就是上面4個(gè)步驟的確定,一旦設(shè)計(jì)完成,實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。使用動(dòng)態(tài)規(guī)劃求解問(wèn)題,最重要的就是確定動(dòng)態(tài)規(guī)劃三要素:
?。?)問(wèn)題的階段
?。?)每個(gè)階段的狀態(tài)
?。?)從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。
遞推關(guān)系必須是從次小的問(wèn)題開(kāi)始到較大的問(wèn)題之間的轉(zhuǎn)化,從這個(gè)角度來(lái)說(shuō),動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來(lái)實(shí)現(xiàn),不過(guò)因?yàn)檫f推可以充分利用前面保存的子問(wèn)題的解來(lái)減少重復(fù)計(jì)算,所以對(duì)于大規(guī)模問(wèn)題來(lái)說(shuō),有遞歸不可比擬的優(yōu)勢(shì),這也是動(dòng)態(tài)規(guī)劃算法的核心之處。
確定了動(dòng)態(tài)規(guī)劃的這三要素,整個(gè)求解過(guò)程就可以用一個(gè)最優(yōu)決策表來(lái)描述,最優(yōu)決策表是一個(gè)二維表,其中行表示決策的階段,列表示問(wèn)題狀態(tài),表格需要填寫(xiě)的數(shù)據(jù)一般對(duì)應(yīng)此問(wèn)題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值(如最短路徑,最長(zhǎng)公共子序列,最大價(jià)值等),填表的過(guò)程就是根據(jù)遞推關(guān)系,從1行1列開(kāi)始,以行或者列優(yōu)先的順序,依次填寫(xiě)表格,最后根據(jù)整個(gè)表格的數(shù)據(jù)通過(guò)簡(jiǎn)單的取舍或者運(yùn)算求得問(wèn)題的最優(yōu)解。f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}
三、動(dòng)態(tài)規(guī)劃算法基本思想與策略
編輯動(dòng)態(tài)規(guī)劃算法的基本思想與分治法類(lèi)似,也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題(階段),按順序求解子階段,前一子問(wèn)題的解,為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí),列出各種可能的局部解,通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解,丟棄其他局部解。依次解決各子問(wèn)題,最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn),為減少重復(fù)計(jì)算,對(duì)每一個(gè)子問(wèn)題只解一次,將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
四、動(dòng)態(tài)規(guī)劃算法基本框架
for(j=1; j《=m; j=j+1) // 第一個(gè)階段
xn[j] = 初始值;
for(i=n-1; i》=1; i=i-1)// 其他n-1個(gè)階段
for(j=1; j》=f(i); j=j+1)//f(i)與i有關(guān)的表達(dá)式
xi[j]=j=max(或min){g(xi-1[j1:j2]), 。。。。。。, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子問(wèn)題的最優(yōu)解求解整個(gè)問(wèn)題的最優(yōu)解的方案
print(x1[j1]);
for(i=2; i《=n-1; i=i+1)
{
t = t-xi-1[ji];
for(j=1; j》=f(i); j=j+1)
if(t=xi[ji])
break;
}
五、電路布線問(wèn)題的幾種動(dòng)態(tài)規(guī)劃算法
/*
Name:
Copyright:
Author:巧若拙
Date: 01-04-17 07:48
Description: 電路布線
【問(wèn)題描述】
在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì),要求用導(dǎo)線(i,π(i))將上端接線柱i與下端接線柱π(i)相連。
其中,π(i),1《=i《=n是{1,2,…,n}的一個(gè)排列。導(dǎo)線(i,π(i))稱(chēng)為該電路板上的第i條連線。對(duì)于任何1《=i π(j)。
在制作電路板時(shí),要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。
你的任務(wù)是要確定將哪些連線安排在第一層上,使得該層上有盡可能多的連線。
換句話說(shuō),就是確定導(dǎo)線集Nets={ i,π(i),1《=i《=n}的最大不相交子集。
【輸入形式】
輸入文件第一行為整數(shù)n;第二行為用一個(gè)空格隔開(kāi)的n個(gè)整數(shù),表示π(i)。
【輸出形式】
輸出文件第一行為最多的連線數(shù)m,第2行到第m+1行輸出這m條連線(i,π(i))。
【輸入樣例】
10
1 8
2 7
3 4
4 2
5 5
6 1
7 9
8 3
9 10
10 6
【輸出樣例】
4
算法1:int MNS(int i, int j);//自頂向下的備忘錄算法
設(shè)置一個(gè)備忘錄數(shù)組s[N+1][N+1],s[i][j]表示從上接線柱1-i發(fā)出的導(dǎo)線連接到下接線柱1-j,能生成的不相交導(dǎo)線的最大條數(shù)。
利用原問(wèn)題的遞歸關(guān)系,使用遞歸函數(shù)來(lái)求解。
狀態(tài)方程:當(dāng)i=1時(shí),s[1][j] = (j《c[1]) ? 0 : 1;
當(dāng)i》1時(shí),若j《c[i],則s[i][j] = s[i-1][j]; 否則s[i][j] = max(s[i-1][c[i]-1]+1, s[i-1][j]);
算法2:int MNS_2(int n);//自底向上的動(dòng)態(tài)規(guī)劃算法
從i=1開(kāi)始,依次記錄每一個(gè)s[i][j],最后獲得最優(yōu)解s[N][N]。
算法3:int MNS_3(int n);//優(yōu)化的動(dòng)態(tài)規(guī)劃算法
是對(duì)算法2的優(yōu)化,算法2中用到的備忘錄數(shù)組s[N+1][N+1]占空間較大,實(shí)際上下一行數(shù)據(jù)是利用上一行的數(shù)據(jù)生成的,
與更早的數(shù)據(jù)沒(méi)有關(guān)系,于是可以用兩個(gè)一維數(shù)組pre[N+1]和cur[N+1]代替s[N+1][N+1]。
最后寫(xiě)了一個(gè)函數(shù)void Traceback(int n); //輸出滿(mǎn)足條件的導(dǎo)線
該函數(shù)需要用到備忘錄數(shù)組s[N+1][N+1],故只能對(duì)算法1和算法2產(chǎn)生的結(jié)果有效。
算法4:與算法2相似,但思路更清晰明了的一種算法。算法的邏輯,與最長(zhǎng)公共子序列很相似。
設(shè)a[i][j]為上端接線柱i與下端接線柱j前的最大不相交子集,則:
若i與j相連,則a[i][j] = a[i-1][j-1] + 1
若i與j不相連,則a[i][j] = max(a[i][j-1], a[i-1][j])
說(shuō)明:算法2雖然代碼更復(fù)雜,但是它做了分類(lèi)判斷,減少了很多不必要的計(jì)算,效率更高。
算法5:對(duì)算法4的改進(jìn):分階段討論,避免不必要的計(jì)算。
與算法2相類(lèi)似,對(duì)下端的接線柱j進(jìn)行了分段討論:分成j《c[i], j==c[i]和j》c[i]三個(gè)區(qū)間,分別求a[i][j]的值,效率更高。
算法6:int MNS_4(int n);//將問(wèn)題轉(zhuǎn)化為求最長(zhǎng)不下降序列
注意到電線上端的接線柱已經(jīng)按順序排列,問(wèn)題可以轉(zhuǎn)化為求數(shù)組c[N+1]的最長(zhǎng)不下降序列
*/
#include《iostream》
#include《string》
using namespace std;
int MNS(int i, int j);//自頂向下的備忘錄算法
int MNS_2(int n);//自底向上的動(dòng)態(tài)規(guī)劃算法
void Traceback_1(int n); //輸出滿(mǎn)足條件的導(dǎo)線
void Traceback_2(int n); //輸出滿(mǎn)足條件的導(dǎo)線
void Traceback_3(int n); //輸出滿(mǎn)足條件的導(dǎo)線
int MNS_3(int n);//優(yōu)化的動(dòng)態(tài)規(guī)劃算法
int MNS_4(int n);//另一種思路的動(dòng)態(tài)規(guī)劃算法
int MNS_5(int n);//對(duì)算法4的改進(jìn):分階段討論,避免不必要的計(jì)算
int MNS_6(int n);//將問(wèn)題轉(zhuǎn)化為求最長(zhǎng)不下降序列
const int N = 10;
int c[N+1] = {0,8,7,4,2,5,1,9,3,10,6};
int s[N+1][N+1];
int a[N+1][N+1];
int b[N+1][N+1];
int pre[N+1]; //上一行記錄
int cur[N+1]; //當(dāng)前行記錄
int S[N+1]; //記錄到元素i為止的最長(zhǎng)上升子序列的長(zhǎng)度
int main()
{
cout 《《 MNS(N, N) 《《 endl;
cout 《《 MNS_2(N) 《《 endl;
cout 《《 MNS_3(N) 《《 endl;
cout 《《 MNS_4(N) 《《 endl;
cout 《《 MNS_5(N) 《《 endl;
cout 《《 MNS_6(N) 《《 endl;
Traceback_1(N);
Traceback_2(N);
Traceback_3(N);
return 0;
}
int MNS(int i, int j)//自頂向下的備忘錄算法
{
if (s[i][j] 》 0)
return s[i][j];
if (i == 1) //處理第一根導(dǎo)線
{
s[i][j] = (j 《 c[i]) ? 0 : 1;
}
else
{
s[i][j] = MNS(i-1, j);
if (j 》= c[i] && MNS(i-1, c[i]-1)+1 》 s[i][j])
s[i][j] = s[i-1][c[i]-1] + 1; //s[i-1][c[i]-1]在if語(yǔ)句中記錄過(guò)了
}
return s[i][j];
}
int MNS_2(int n)//自底向上的動(dòng)態(tài)規(guī)劃算法
{
//先處理第一根導(dǎo)線
for (int j=1; j《c[1]; j++)
s[1][j] = 0;
for (int j=c[1]; j《=n; j++)
s[1][j] = 1;
//然后處理中間的導(dǎo)線
for (int i=2; i《n; i++)
{
for (int j=1; j《c[i]; j++)
{
s[i][j] = s[i-1][j];
}
for (int j=c[i]; j《=n; j++)
{
s[i][j] = (s[i-1][c[i]-1]+1 》 s[i-1][j]) ? s[i-1][c[i]-1]+1 : s[i-1][j];
}
}
//再處理最后一根導(dǎo)線
s[n][n] = (s[n-1][c[n]-1]+1 》 s[n-1][n]) ? s[n-1][c[n]-1]+1 : s[n-1][n];
return s[n][n];
}
void Traceback_1(int n) //輸出滿(mǎn)足條件的導(dǎo)線
{
int j = n;
for (int i=n; i》1; i--)
{
if (s[i][j] 》 s[i-1][j])
{
cout 《《 i 《《 “ - ” 《《 c[i] 《《 endl;
j = c[i] - 1;
}
}
if (j 》= c[1])
{
cout 《《 1 《《 “ - ” 《《 c[1] 《《 endl;
}
}
void Traceback_2(int n) //輸出滿(mǎn)足條件的導(dǎo)線
{
int j = n;
for (int i=n; i》1; i--)
{
if (a[i][j] 》 a[i-1][j])
{
cout 《《 i 《《 “ - ” 《《 c[i] 《《 endl;
j = c[i] - 1;
}
}
if (j 》= c[1])
{
cout 《《 1 《《 “ - ” 《《 c[1] 《《 endl;
}
}
void Traceback_3(int n) //輸出滿(mǎn)足條件的導(dǎo)線
{
int j = n;
for (int i=n; i》1; i--)
{
if (b[i][j] 》 b[i-1][j])
{
cout 《《 i 《《 “ - ” 《《 c[i] 《《 endl;
j = c[i] - 1;
}
}
if (j 》= c[1])
{
cout 《《 1 《《 “ - ” 《《 c[1] 《《 endl;
}
}
int MNS_3(int n)//優(yōu)化的動(dòng)態(tài)規(guī)劃算法
{
//先處理第一根導(dǎo)線
for (int j=1; j《c[1]; j++)
pre[j] = 0;
for (int j=c[1]; j《=n; j++)
pre[j] = 1;
//然后處理中間的導(dǎo)線
for (int i=2; i《n; i++)
{ //處理當(dāng)前行cur
for (int j=1; j《c[i]; j++)
{
cur[j] = pre[j];
}
for (int j=c[i]; j《=n; j++)
{
cur[j] = (pre[c[i]-1]+1 》 pre[j]) ? pre[c[i]-1]+1 : pre[j];
}
//復(fù)制當(dāng)前行信息cur到pre
for (int j=1; j《=n; j++)
{
pre[j] = cur[j];
}
}
//再處理最后一根導(dǎo)線
cur[n] = (pre[n-1]+1 》 pre[n]) ? pre[n-1]+1 : pre[n];
return cur[n];
}
int MNS_4(int n)//另一種思路的動(dòng)態(tài)規(guī)劃算法,與最長(zhǎng)公共子序列很相似
{
for (int i=1; i《=n; i++)
{
for (int j=1; j《=n; j++)
{
if (j == c[i])
a[i][j] = a[i-1][j-1] + 1;
else
a[i][j] = max(a[i-1][j], a[i][j-1]);
}
}
return a[n][n];
}
int MNS_5(int n)//對(duì)算法4的改進(jìn):分階段討論,避免不必要的計(jì)算
{
for (int i=1; i《=n; i++)
{
for (int j=1; j《c[i]; j++)//在接線柱c[i]的左側(cè)區(qū)域,最優(yōu)解與不包含接線柱i的一致
{
b[i][j] = b[i-1][j];
}
b[i][c[i]] = b[i-1][c[i]-1] + 1;
for (int j=c[i]+1; j《=n; j++)//在接線柱c[i]的右側(cè)區(qū)域,最優(yōu)解可能包含接線柱i,也可能不包含i
{
b[i][j] = max(b[i-1][j], b[i][j-1]);
}
}
return a[n][n];
}
int MNS_6(int n)//將問(wèn)題轉(zhuǎn)化為求最長(zhǎng)不下降序列
{
S[1] = 1; //默認(rèn)到元素i為止的最長(zhǎng)上升子序列的長(zhǎng)度為1
for (int i=2; i《=n; i++)
{
int m = 0;
for (int j=i-1; j》0; j--)//逆序查找不大于A[i],且最長(zhǎng)的元素
{
if (c[i] 》 c[j] && S[j] 》 m)
{
m = S[j];
}
}
S[i] = m + 1;
}
int len = S[n];
for (int i=n-1; i》0; i--)
{
if (S[i] 》 len)
{
len = S[i];
}
}
return len;
}
評(píng)論
查看更多