《算法分析报告与设计课程设计：电路布线》由会员分享，可在线阅读，更多相关《算法分析报告与设计课程设计：电路布线（13页珍藏版）》请在金锄头文库上搜索。
1、实用文案数学与计算科学学院学院 信息与计算科学专业 *班课程名称算法分析与设计题目电路布线任务起止日期：2010年12 月20日2010年1月3日学 生 姓 名*学 号200*指导教师教研室主任年月日审查标准文档目录第一章 . 问题描述 .2第二章 . 问题分析 .32.1 用动态规划分析32.2 用分支定界法分析3第三章问题的解决.53.1 方案一：动态规划53.2 方案二 : 分支定界法6第四章 . 总结 .111第一章 . 问题描述在一块电路板的上、 下两端分别有n 个接线柱。根据电路设计， 要求用导线 (i, (i)将上端接线柱i 与下端接线柱(i)相连，如下图。其中，(i),1 i
2、(j).图 1-1在制作电路板时， 要求将这n 条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = i ， (i)， 1 i n 的最大不想交子集。2第二章 . 问题分析2.1 用动态规划分析为确定导线集Nets = i ， (i)， 1 i n 的最大不想交子集，将待求解问题分解成若干个子问题， 先求解子问题， 然后从这些子问题的解得到原问题的解。现分析最优子结构性质。记 N(i,j) = t|(t, (i) Nets,t i,(t) j . N(i,j)的最大不相交子集为 M
3、NS（i,j ）。 Size(i,j)=|MNS(i,j)|。1） 当 i = 1时MNS(1, j )空, j1N (1, j )1 , j1 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) 的最大不相交子集
4、。否则，子集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) ，有 t1时，Size(i , j )Size(i1, j ), j(i )max Size(i 1, j ), Size(i 1, (i ) 1) 1, j(i)据此可设计解电路布线问题的动态规划算法如下，其中，用二维数组单元sizeij表示函数Size(i， j)void MNS(int C, int n, int *size) / /对于
5、所有的i和 j ，计算 s i z e i j / /初始化 s i z e 1 * for (int j = 0; j C1; j+)size1j = 0;for (j = C1; j = n; j+)size1j = 1;/ 计算 sizei*, 1 i n for (int i = 2; i n; i+) for (int j = 0; j Ci; j+)sizeij = sizei-1j;for (j = Ci; j 1; i-)/ i号 n e t在 M N S 中 ?if (sizeij != sizei-1j)/在 M N S 中Netm+ = i;j = Ci - 1;/1号网
6、组在MNS中?if (j = C1)netm+ = 1; /在 M N S 中此方案的计算复杂度：算法需要n2 计算时间和n2 空间。算法需要n 计算时间。源程序及运行结果见附录。3.2 方案二 : 分支定界法为了找到网格中位置a 和 b 之间的最短路径，先从位置a 开始搜索， 把 a 可到达的相邻方格都标记为1（表示与a 相距为1），然后把标号为1 的方格可到达的相邻方格都标记为 2（表示与a 相距为 2），继续进行下去，直到到达b 或者找不到可到达的相邻方格为止。6图 6-12a演示了这种搜索过程，其中a = ( 3 , 2 )， b = ( 4 , 6 )。图中的阴影方格都是被封锁的方格。a)标识间距b)电线路径图 3-1电路布线按照上述搜索过程， 当我们到达b 时，就可以在b 上标出 b 与 a 之间的距离，在图 3-1(a)中，b 上的标号为9。为了得到a 与 b 之间的最短路径，从 b 开始，首先移动到一个比b的
