算法分析与设计课程设计--电路布线

《算法分析与设计课程设计--电路布线》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数学与计算科学学院学院信息与计算科学专业***班课程名称算法分析与设计题目电路布线任务起止日期：2010年12月20日～2010年1月3日学生姓名**学号200*******指导教师教研室主任年月日审查11目录第一章.问题描述2第二章.问题分析32.1用动态规划分析32.2用分支定界法分析3第三章．问题的解决53.1方案一：动态规划53.2方案二:分支定界法6第四章.总结1111第一章.问题描述在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i))将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤i<≤n,是｛1,2,…,n｝的一个排列。导线(I

2、,π(i))称为该电路板上的第i条连线。对于任何1≤i≤j≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j).图1-1在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不想交子集。11第二章.问题分析2.1用动态规划分析为确定导线集Nets=｛i，π(i)，1≤i≤n｝的最大不想交子集，将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。现分析最优子结构性质。记N(i,j)={t

3、

4、(t,π(i))∈Nets,t≤i,π(t)≤j}.N(i,j)的最大不相交子集为MNS（i,j）。Size(i,j)=

5、MNS(i,j)

6、。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

7、集。否则，子集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

8、11所示。从一个方格a的中心点连接到另一个方格b的中心点时，转弯处必须采用直角，如图2-1（b）所示。如果已经有某条线路经过一个方格，则封锁该方格。我们希望使用a和b之间的最短路径来作为布线的路径，以便减少信号的延迟。a)7×7网格b)a与b之间的电线图2-1电路布线示例从起点位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出对手结点作为下一个扩展结点，并将与当前扩展结点相邻并且未标记过的方格标记为2，并存入活结点队列，这个过程一直持续到算法搜索到目标方格b

9、或活结点队列为空时为止。11第三章．问题的解决3.1方案一：动态规划经以上后分析，可电路布线问题的最优值为Size(n,n)。由该问题的最优子结构性质可知：1)当i=1时，2）当i>1时，据此可设计解电路布线问题的动态规划算法如下，其中，用二维数组单元size[i][j]表示函数Size(i，j)voidMNS(intC[],intn,int**size){//对于所有的i和j，计算size[i][j]//初始化size[1][*]for(intj=0;j

10、],1