威廉希尔官方网站 布线问题的几种动态规划算法

　　一、什么是动态规划算法

　　动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

　　动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

　　二、动态规划算法的实现

　　动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。使用动态规划求解问题，最重要的就是确定动态规划三要素：

　　（1）问题的阶段

　　（2）每个阶段的状态

　　（3）从前一个阶段转化到后一个阶段之间的递推关系。

　　递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。

　　确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。f（n，m）=max{f（n-1，m）， f（n-1，m-w［n］）+P（n，m）}

　　三、动态规划算法基本思想与策略

　　编辑动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

　　由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

　　四、动态规划算法基本框架

　　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有关的表达式

　　xi［j］=j=max（或min）{g（xi-1［j1:j2］）， 。。。。。。， g（xi-1［jk:jk+1］）};

　　t = g（x1［j1:j2］）; // 由子问题的最优解求解整个问题的最优解的方案

　　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;

　　}

　　五、威廉希尔官方网站 布线问题的几种动态规划算法

　　/*

　　Name：

　　Copyright：

　　Author：巧若拙

　　Date： 01-04-17 07:48

　　Description： 威廉希尔官方网站 布线

　　【问题描述】

　　在一块威廉希尔官方网站 板的上、下两端分别有n个接线柱。根据威廉希尔官方网站 设计，要求用导线（i，π（i））将上端接线柱i与下端接线柱π（i）相连。

　　其中，π（i），1《=i《=n是{1，2，…，n}的一个排列。导线（i，π（i））称为该威廉希尔官方网站 板上的第i条连线。对于任何1《=i π（j）。

　　在制作威廉希尔官方网站 板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。

　　你的任务是要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。

　　换句话说，就是确定导线集Nets={ i，π（i），1《=i《=n}的最大不相交子集。

　　【输入形式】

　　输入文件第一行为整数n；第二行为用一个空格隔开的n个整数，表示π（i）。

　　【输出形式】

　　输出文件第一行为最多的连线数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）;//自顶向下的备忘录算法

　　设置一个备忘录数组s［N+1］［N+1］，s［i］［j］表示从上接线柱1-i发出的导线连接到下接线柱1-j，能生成的不相交导线的最大条数。

　　利用原问题的递归关系，使用递归函数来求解。

　　状态方程：当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）;//自底向上的动态规划算法

　　从i=1开始，依次记录每一个s［i］［j］，最后获得最优解s［N］［N］。

　　算法3：int MNS_3（int n）;//优化的动态规划算法

　　是对算法2的优化，算法2中用到的备忘录数组s［N+1］［N+1］占空间较大，实际上下一行数据是利用上一行的数据生成的，

　　与更早的数据没有关系，于是可以用两个一维数组pre［N+1］和cur［N+1］代替s［N+1］［N+1］。

　　最后写了一个函数void Traceback（int n）; //输出满足条件的导线

　　该函数需要用到备忘录数组s［N+1］［N+1］，故只能对算法1和算法2产生的结果有效。

　　算法4：与算法2相似，但思路更清晰明了的一种算法。算法的逻辑，与最长公共子序列很相似。

　　设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］三个区间，分别求a［i］［j］的值，效率更高。

　　算法6：int MNS_4（int n）;//将问题转化为求最长不下降序列

　　注意到电线上端的接线柱已经按顺序排列，问题可以转化为求数组c［N+1］的最长不下降序列

　　*/

　　#include《iostream》

　　#include《string》

　　using namespace std;

　　int MNS（int i， int j）;//自顶向下的备忘录算法

　　int MNS_2（int n）;//自底向上的动态规划算法

　　void Traceback_1（int n）; //输出满足条件的导线

　　void Traceback_2（int n）; //输出满足条件的导线

　　void Traceback_3（int n）; //输出满足条件的导线

　　int MNS_3（int n）;//优化的动态规划算法

　　int MNS_4（int n）;//另一种思路的动态规划算法

　　int MNS_5（int n）;//对算法4的改进：分阶段讨论，避免不必要的计算

　　int MNS_6（int 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）//自底向上的动态规划算法

　　{

　　//先处理第一根导线

　　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）//优化的动态规划算法

　　{

　　//先处理第一根导线

　　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）//另一种思路的动态规划算法，与最长公共子序列很相似

　　{

　　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］的左侧区域，最优解与不包含接线柱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］的右侧区域，最优解可能包含接线柱i，也可能不包含i

　　{

　　b［i］［j］ = max（b［i-1］［j］， b［i］［j-1］）;

　　}

　　}

　　return a［n］［n］;

　　}

　　int MNS_6（int 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;

　　}