动态规划电路布线.doc

课程设计说明书(论文)用纸
摘 要
动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。动态规划思想近来在各类型信息学竞赛中频繁出现，它的应用也越来越受人重视。本文就是讨论如何运用动态规划的思想设计出有效的数学模型来解决问题
常用的解决电路布线问题的算法的时间和空间的复杂度都是O(n2)。这里n为一块电路板的上端(或下端)接线柱的个数。现给出一种时间复杂度为O(log)的新算法。

关键词：动态规划 ，电路布线 目 录
1 问题描述 1
2 问题分析 2
3 建立数学模型 3
4 算法设计 5
5 算法实现 6
结 论 7
参考文献 8

II
1 问题描述
在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤ i <≤n,是｛1,2,…,n｝的一个排列。导线(I, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n,第i条连线和第j条连线相交的充要条件是π(i)> π(j).

图1-1
在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不想交子集。

第4页 共8 页
2 问题分析
为确定导线集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不想交子集，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。现分析最优子结构性质。
记N(i,j) = {t|(t, π(i)) ∈ Nets,t ≤ i, π(t) ≤ j }. N(i,j)的最大不相交子集为MNS（i,j）。Size(i,j)=|MNS(i,j)|。
1） 当i = 1时

2) 当i >1时，
① j <π(i)。此时，(i,π(i)) 不属于N(i,j)。故在这种情况下，N(i,j) = N(i-1,j)，从而Size(i,j)=Size(i-1,j)。
② j ≥π(i)。此时，若(i, π(i))∈MNS(i,j)，则对任意(t, π(i))∈MNS(i,j)有t < i且π(t)< π(i)；否则，(t,π(t))与(i, π(i))相交。在这种情况下MNS(i,j)-{(i, π(i))}是N(i-1, π(i)-1)的最大不相交子集。否则，子集 MNS(i-1,π(i)-1)∪{(i, π(i))}N(i,j) 是比MNS(i,j)更大的N(i,j)的不相交子集。这与MNS(i,j)的定义相矛盾。
若(i, π(i))不属于MNS(i,j)，则对任意(t, π(t))∈MNS(i,j)，有t<i。从而MNS(i,j)包含于N(i-1,j)，因此，Size(i,j)≤Size(i-1,j)。
另一方面，MNS(i-1,j)包含于N(i,j),故又有Size(i,j) ≥Size(i-1,j)，从而Size（i,j）= Size(i-1,j)。

3 建立数学模型
经以上后分析，可电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知：
1)当i=1时，

2）当i>1时，

据此可设计解电路布线问题的动态规划算法如下，其中，用二维数组单元size[i][j]表示函数Size(i，j)
void MNS(int C[], int n, int **size)
{ / /对于所有的i 和j，计算s i z e [ i ] [ j ]
/ /初始化s i z e [ 1 ] [ * ]
for (int j = 0; j < C[1]; j++)
size[1][j] = 0;
for (j = C[1]; j <= n; j++)
size[1][j] = 1;
// 计算size[i][*], 1 < i < n
for (int i = 2; i < n; i++) {
for (int j = 0; j < C[i]; j++)
size[i][j] = size[i-1][j];
for (j = C[i]; j <= n; j++)
size[i][j] = max(size[i-1][j], size[i-1][C[i]-1]+1);
}
size[n][n] = max(size[n-1][n], size[n-1][C[n]-1]+1);
}

接着，构造最优解：根据算法MNS计算出的size[i][j]值，容易由算法traceback构造出最后解MNS（n,n）。
void Traceback(int C[], int **size, int n, int Net[], int& m)
{// 在N e t [ 0 : m - 1 ]中返回M M S
int j = n; // 所允许的底部最大针脚编号
m = 0; // 网组的游标
for (int i = n; i > 1; i--)
// i 号n e t在M N S中?
if (size[i][j] != size[i-1][j]){// 在M N S中
Net[m++] = i;
j = C[i] - 1;}
// 1号网组在M N S中?
if (j >= C[1])
net[m++] = 1; // 在M N S中
}

此方案的计算复杂度：算法ＭＮＳ需要计算时间和空间。算法ｔｒａｃｅｂａｃｋ需要计算时间。
源程序及运行结果见附录。

4 算法设计
对于在一块电路板的上、下两端分别有n个接线柱，在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交德问题。要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。方案一将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。方案二在布线区域叠上一个网格，该网格把布线区域划分成n ×m个方格，转换为用分支定界法方法求解。方案一的计算复杂度：算法ＭＮＳ需要计算时间和空间。算法ｔｒａｃｅｂａｃｋ需要计算时间。
方案二由于任意一个网格位置都至多在队列中出现 1次，所以完成网格编号过程需耗时 （对一个m ×m的网格来说）。而重构路径的过程需耗时 O(L) ，其中L为最短路径的长度
5 算法实现
在程序的中，假定起始位置和结束位置均未被封锁。程序首先检查 s t a r t和f i n i s h是 否相同，如果相同，则路径长度为0，程序终止。否则设置一堵由封锁位置构成的“围墙”，把网格包围起来。然后对o ff s e t数组进行初始化，并在起始位置上标记 2 。（所有标号都增加了2，因为数组中采用0和1来表示空白位置和封锁位置，为了得到如图 6-12a 所示的标号，必须把程序中的每个标号减去2）。借助于队列Q并从位置s t a r t开始，首先移动到与s t a r t相距为1的网格位置，然后移动到与s t a r t相距为2的网格位置，不断进行下去，直到到达位置f i n i s h或者无法继续移动到一个新的、空白的位置。在后一种情况下，将不存在到达位置 f i n i s h的路径，而在前一 种情况下，位置f i n i s h将得到一个相应的编号，如果到达了位置f i n i s h，则可以利用网格上的标号来重构路径。路径上的位置（ start除外）均被存储在数组p a t h之中。
由于任意一个网格位置都至多在队列中出现 1次，所以完成网格编号过程需耗时 （对一个m ×m的网格来说）。而重构路径的过程需耗时 O(L) ，其中L为最短路径的长度。

结 论
对于在一块电路板的上、下两端分别有n个接线柱，在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交德问题。要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。方案一将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。方案二在布线区域叠上一个网格，该网格把布线区域划分成n ×m个方格，转换为用分支定界法方法求解。通过这次课程设计，我们对动态规划算法有了更深的认识，同时也更加熟练了C、C++和JAVA程序设计语言的运用，是开发人员必不可少的有力工具。同时，我们学到了如何用算法的思想分析一个给定的问题，最终动手解决问题。在整个过程中，需要不断的调试，更改代码，当中，我们遇到了很多棘手问题。在不断思考、调试后，不仅锻炼了我的实际动手能力，更锻炼了我们发现问题、分析问题的能力。

参考文献
[1] 严蔚敏,吴伟民.数据结构(c语言版)[M].北京:清华大学出版社,1997．
[2] M.H.ALSUWAIYEL.算法设计技巧与分析[M].北京:电子工业出版社,2004．
[3] 谭浩强.C++面向对象程序设计[M].北京:清华大学出版社,2006．
[4] 常友渠.贪心算法的探讨与研究[M].重庆电力高等专科学报,第13卷，第13期，2008.9.
[5]朱洪.算法设计和分析[M].上海科学技术文献出版社,1989,162-163.
[6]卢开澄.计算机算法导引—设计与分析[M].北京:清华大学出版社,2003．