電子發(fā)燒友App
一、什么是動(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;
}
工商網(wǎng)監(jiān)
評(píng)論