电路板的电路布线设计
问题描述：
在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线（i，π（i）） 将上端接线柱i与下端接线柱π（i）相连，如下图。其中，π（i），1≤ i ≤n，是｛1，2，…，n｝的一个排列。导线（I， π（i））称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n，第i条连线和第j条连线相交的充要条件是π（i）》 π（j）。
π（i）=｛8，7，4，2，5，1，9，3，10，6｝
在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = ｛i，π（i），1 ≤ i ≤ n｝的最大的一个子集，这个子集中的导线互相不相交。
问题分析：
显然这是一个组合问题，对于组合问题中求最优解的方法基本都是动态规划算法。现在表述一下如何划分子问题：
用B（i，j）表示最优解，其中，i是上端接线柱的序号，j是下端接线柱的序号，B（i，j）表示序号小于或等于i的上端接线柱和序号小于或等于j的下端接线柱中不相交连线的最大集合。 用size（i，j）表示集合中导线的数目（size（i，j）=|B（i，j）|）。B（i，j）的值蕴含在B（i-1，j）和B（i，j-1）这俩个子问题中，对于有2xN个接线柱的电路板，那么B（N，N）就是其解了。
对于上端接线柱t，用 π（t）表示与他相连的下端接线柱
那么递推公式为：
递推公式证明：
对于从B（i-1，j）或B（i，j-1）到B（i，j）要么会多加一条导线，要么不加。
1. 当 j==π（i）时，（i，j）则是一条导线，且这条导线对B（i-1，j-1）的值没有影响，因为B（i-1，j-1）中的任意的一条导线的节点序号（无论是上端节点序号还是下端节点序号）都小于i，j，这由其空间位置决定的。
现在求B（i，j）， 即求序号小于或等于i的上端接线柱和序号小于或等于j的下端接线柱中不相交导线的最大集合。显然应是B（i-1，j-1）U（i，j）。
2 。 当j！= π（i）时。假如问题是从B（i，j-1）到B（i，j），那么下端新加入的接线柱j要么与上端的1至i-1个接线柱构成导线（与第i个接线柱构成导线的情况在上面已经讨论），要么不构成。
如果构成的话那么这种情况其实已经在B（i-1，j）中讨论了，这里不再考虑。那么B（i，j） 应是序号区间比他小一点的子问题的解。小一点是多少，肯定就是少一个接线柱了，也就是B（i-1，j）。
如果不构成的话，那么B（i，j）肯定就是序号区间比他小一点的子问题的解了。
对于B（i，j）可能由B（i-1，j）或B（i，j-1）过渡而来，所以B（i，j）取其中较大的一个。
-
电路板
+关注
关注
140文章
4951浏览量
97686 -
电路设计
+关注
关注
6673文章
2451浏览量
204125
发布评论请先 登录
相关推荐
如何实现良好的电路板布局布线
电磁兼容和印刷电路板(理论、设计和布线)
印制电路板的布线技术
用PROTEL DXP设计电路板的原则
PCB设计高频电路板的布线技巧和注意事项详细概述
印制电路板的布线流程
紫外激光器在工业领域PCB中的4大主要应用
电路板级的EMC设计（3） PCB布线技术
工商网监
评论