电路板电路布线设计相关问题
问题
在一块电路板的上下两端分别有n个接线柱。根据电路设计，要求用导线 （i，π（i）），将上端接线柱 i 与下端接线柱 π（i） 相连，
如图，其中 π（i），1《=i《=n，是（1，2……，n）的一个排列。导线（i，π（i））称为该电路板上的第i条连线。对于任何 1《=i《s《=n，第i条连线和第s条连线相交的充分且必要条件是 π（i） 》 π（s）。
ps：注意 π（pi） 和 n，不是小写的n，别看错了
问：在制作电路板时，要求将这n条线分布到若干个绝缘层上，在同一层上的连线不能相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。
详细说明
首先 上下各有 n 个接线柱，用 a［i］ 数组表示 与 上接线柱 相连线的 下接线柱，再用 set［i］［j］ 表示上接线柱 i 与下接线柱 j 相连线的 左边（包括 i ，j 连线）的最大不相交连线的个数。
ps（这里的 j ，i 和上面问题中说的不是一个东西，这里的 i指的是上接线柱，j指的是下接线柱）
1、公式如下：
如果 j ！= a［i］ 则 max（ set［i-1］［j］，set［i］［j-1］ ）
set［i，j］ =
如果 j == a［i］ 则 set［i-1］［j-1］ + 1
循环遍历 i 和 j ，具体使用 i X j 的嵌套循环，其实就是每一个上接线柱和每一个下接线柱做一次匹配，这样就可以得出结果，set［n］［n］即我们想要的结果。最后通过回溯把结果输出出来
==》 j == a［i］，表示当上图中的某个上下接线柱相连时，这时这两个点不会在和其他的接线柱相连，
这时在 （i ，j） 处的最大不相交连线的个数就应该是就是 第 i-1个上接线柱 和第 j-1个下接线柱时的 最大不相交连线的个数 + 1。这个+1很重要。
==》 j ！= a［i］，表示当上图中的某个上下接线柱相连时，这时 i 点和 非 j 点相连， j 点和 非 i 点相连，
这时在（ i ，j） 处的最大不相交连线的个数就应该和 （ i - 1，j ） 处最大不相交连线的个数、 （ i，j - 1）处最大不相交连线的个数中较大的最大不相交连线的个数相同。
2、参考图如下：
红色标明的就是算法选择的路径（向上优先，也可以用向左优先，答案都是四个，但值会有一点不同）。在斜角值改变时可以取得所求的子集。即 9-》10，7-》9， 5-》5， 3-》4
代码块
#include 《stdio.h》
#include 《stdlib.h》
#define MAX（ a， b ） （ （a） 》 （b） ？ （a） ： （b） ）
void circut（ int a［］， int set［］［11］， int n ）;
void back_track（ int i， int j， int set［］［11］ ）;
int main（）
{
int a［］ = { 0， 8， 7， 4， 2， 5， 1， 9， 3， 10， 6 };
int set［11］［11］;
circut（ a， set， 10 ）;
printf（ “max set： %d \n”， set［10］［10］ ）;
back_track（ 10， 10， set ）;
printf（ “\n” ）;
system（ “pause” ）;
return（0）;
}
void circut（ int a［］， int set［］［11］， int n ）
{
int i， j;
for （ i = 0; i 《 n; i++ ）
{
set［i］［0］ = 0;
set［0］［i］ = 0;
}
for （ i = 1; i 《= n; i++ ）
{
for （ j = 1; j 《= n; j++ ）
{
if （ a［i］ ！= j ）
set［i］［j］ = MAX（ set［i - 1］［j］， set［i］［j - 1］ ）;
else
set［i］［j］ = set［i - 1］［j - 1］ + 1;
}
}
}
void back_track（ int i， int j， int set［］［11］ ）
{
if （ i == 0 ）
return;
if （ set［i］［j］ == set［i - 1］［j］ ）
back_track（ i - 1， j， set ）;
else if （ set［i］［j］ == set［i］［j - 1］ ）
back_track（ i， j - 1， set ）;
else{
back_track（ i - 1， j - 1， set ）;
printf（ “（%d，%d） ”， i， j ）;
}
}
时间复杂度
circut 的时间复杂度为O（n2）
back_track的时间复杂度为 O（n）
如有错误请指正。
-
电路板
+关注
关注
140文章
4951浏览量
97686 -
电路设计
+关注
关注
6673文章
2451浏览量
204125
发布评论请先 登录
相关推荐
电路板布线设计（一）探索双层板布线技艺
如何实现良好的电路板布局布线
电磁兼容和印刷电路板(理论、设计和布线)
印制电路板的布线技术
用PROTEL DXP设计电路板的原则
PCB设计高频电路板的布线技巧和注意事项详细概述
印制电路板的种类有哪些_印制电路板布线要求
印制电路板的布线流程
电路板级的EMC设计（3） PCB布线技术
工商网监
评论