算法分析报告与设计课程设计：电路布线.doc

PAGE 1 实用文案 标准文档 数学与计算科学学院 学院 信息与计算科学 专业 *** 班 课程名称 HYPERLINK javascript:void(0) 算法分析与设计 题 目 电路布线 任务起止日期： 2010年 12月 20日～ 2010年 1月 3 日 学 生 姓 名 ** 学 号 200******* 指 导 教 师 教研室主任 年 月 日审查 目录 TOC \o 1-3 \h \u HYPERLINK \l _Toc17775 第一章.问题描述 PAGEREF _Toc17775 2 HYPERLINK \l _Toc9445 第二章.问题分析 PAGEREF _Toc9445 3 HYPERLINK \l _Toc25634 2.1用动态规划分析 PAGEREF _Toc25634 3 HYPERLINK \l _Toc10813 2.2用分支定界法分析 PAGEREF _Toc10813 3 HYPERLINK \l _Toc13927 第三章．问题的解决 PAGEREF _Toc13927 5 HYPERLINK \l _Toc30888 3.1方案一：动态规划 PAGEREF _Toc30888 5 HYPERLINK \l _Toc14101 3.2方案二:分支定界法 PAGEREF _Toc14101 6 HYPERLINK \l _Toc32747 第四章.总结 PAGEREF _Toc32747 11 第一章.问题描述 在一块电路板的上、下两端分别有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｝的最大不想交子集。  第二章.问题分析 2.1用动态规划分析 为确定导线集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)，有ti。从而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)。 2.2用分支定界法分析 在布线区域叠上一个网格，该网格把布线区域划分成n ×m个方格，如图6 - 11a 所示。从一个 方格a的中心点连接到另一个方格b的中心点时，转弯处必须采用直角，如图2-1（b）所示。如果 已经有某条线路经过一个方格，则封锁该方格。我们希望使用a和b之间的最短路径来作为布线 的路径，以便减少信号的延迟。 a) 7 ×7 网格