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