分支限界求解布线问题

1、摘要分支限界算法对很多实际问题是重要和有效的。论文首先提出了一类电 路布线问题，然后给出了解决该问题的分支限界算法并分析了所给出算 法的复杂度。实验结果验证了所提出方法的有效性。关键字：分支限界算法电路布线问题 复杂度ABSTRACTThe branch-and-bound algorithm is an important and efficient method to many problems. In this paper, a kind of circuit wiring problem is brought up firstly, and then an efficient algo

2、rithm based on branch一and-bound algorithm is presented. Finally, the complexity of the proposed algorithm is analyzedSimulation results show they are efective .Keywords： branchand bound algorithm circuitwiringproblem,complexit目录 TOC o 1-5 h z HYPERLINK l bookmark1 o Current Document 摘要1 HYPERLINK l

3、bookmark4 o Current Document ABSTRACT1 HYPERLINK l bookmark22 o Current Document 1引言3 HYPERLINK l bookmark25 o Current Document 2布线问题的提出3 HYPERLINK l bookmark28 o Current Document 3问题的算法选择3 HYPERLINK l bookmark31 o Current Document 4分支限界算法4FIFO 搜索LIFO搜索优先队列式搜索 HYPERLINK l bookmark19 o Current Docume

4、nt 5布线问题的分支限界算法设计4初始化部分用FIFO分支搜索的过程可布线未知的识别队列的结构类型和操作实例与测试结果复杂性分析 TOC o 1-5 h z HYPERLINK l bookmark48 o Current Document 6结束语6 HYPERLINK l bookmark51 o Current Document 7致谢7 HYPERLINK l bookmark54 o Current Document 8参考文献7 HYPERLINK l bookmark57 o Current Document 9附录71引言随着信息技术的发展和嵌入式设备的广泛使用.电路布线问题

5、越来 越受到人们的重视.要使电子电路获得最佳性能.不仅元器件的布置占 有着重要的地位.而且导线的布设也是非常重要的.特别是在涉及到线 路成本的布线方案中.一个好的布线算法就显得尤为重要本文首先对 一类电路板低成本布线问题进行了分析.进而给出了解决这一问题的分 支限界解法.并对所提出算法的时间复杂度进行了分析和讨论。2问题的提出布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。 精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线 方案。在布线时，电路只能沿直线或直角布线，如图1所示。为了避免 线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线 路不允许穿过被

6、封锁的方格。1134L456156外36181图53问题的算法选择题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪 算法解决问题，也就是从a开始朝着b的方向垂直布线即可。实际上，再 看一下图2,就知道贪婪算法策略是行不通的。因为已布线的放个没有 规律的所以直观上说只能用搜索方法去找问题的解。根据布线方法的要求，除边界或已布线处，每佃-结点分支扩充的 方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4 个活结点。以图2的情况为例，图的搜索过程如图3所示。搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当 然反之也可以）。反过来则到，按序号8-7-6-5-4

7、-3-2-1就可以找到最短的布线方案。从图3中也可以发现最短的布线方案是不唯一的。且由 此可以看出，此问题适合用分支限界搜索。4分支限界算法分支限界搜索法是一种在问题解空间上进行搜索尝试的算法。所谓 “分支”是采用广度优先的策略，依次搜索-结点的所有分支，也就是 所有的相邻结点。和回溯法一样，在生成的结点中，抛弃那些不满足约 束条件（或者说不可能到处最优可行解）的结点，其余结点加入活结点 表。然后从表中选择一个节点作为下一个-结点，继续搜索。选择下一 个E-结点的方式不同，会出现几种不同的分值搜索方式。（1）FIFO搜索先进先出（FIFO）搜索算法要依赖“队”做基本的数据结构。一开 始，根节点

8、是唯一的活结点，根节点入队。从活结点队中取出根节点后， 作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子， 用约束条件检查，把所有满足约束函数的儿子加入或节点队列中。再从 活结点表中取出队首结点（对中最先进来的结点）为当前结点， 直到找到一个解或活结点队列为空为止。（2）LIFO搜索后进先出（LIFO）搜索算法要依赖“栈”做基本的数据结构。一开 始，根结点入栈，从栈中弹出一个结点为当前扩展结点。对当前扩展结 点，从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束 函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当 前扩展结点，直到找到一个解或栈为空为止。（3）

9、优先队列式搜索为了加速搜索的进程，应采用有效的方式选择E-结点进行扩展。优 先队列搜索，对每一个活结点计算一个优先级（某些信息的函数值）， 并根据这些优先级，从当前结点表中优先选择一个优先级最高（最有利） 的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以 便尽快地找出一个最优解。5布线问题的分支限界算法设计i=（1）初始化部分开辟m*n的二维数组模拟布线区域，初始值均为0，表示没有被使用。 已使用的位置，通过键盘输入其下标，将对应值置为-1 .输入方格a、b 的下标，存储在变量中。（2）用FIFO分支搜索的过程一开始，唯一的活结点是a。从活结点表中取出后为当前扩展结点。对当前扩展

10、结点，按上、下、左、右的顺序，找出可布线的位置， 加入活结点队列中，再从活结点队列中取出后为当前扩展结点。依此类推，直到搜索到达b结点，然后按序号8-7-6-5-4-3-2-瑜 出最短布线方案，算法结束。或活结点队列已为空，表示无解，算法结 束。可布线未知的识别可布线位置不能简单地认为是结点为-1的点，因为还要考虑数组越 界的情况。反过来说，不可布线的位置有两种情况：已占用结点，标识为0.21J451a456)14613278-1X图4布线区域外的结点，标识比较复杂，是一 个含4个关系表达式的逻辑表达式，结点下标(i,j) 满足：not (i0 and i0 and j=n)第二种情况逻辑表达

11、式比较复杂，可以用设 置“边界空间”的技巧，把以上两种不可布线的 情况都归纳为第一种情况，如图4所示，把布线区 域扩充为(m+2)*(n+2)数组，边界置占用状态，就 无需做越界的检查了。这也是用空间效率换取时 间效率的技巧。队列的结构类型和操作为了突出算法思想，关于队列的结构类型和操作，只用抽象的符号 代替：team :为队列的类型说明符，具体本文用的是链表；inq(p):结点入队；out():结点从队列中出对，并返回队首结点；empty():判断队列是否为空，空返回“真”，非空返回“假”。实例与测试结果在图4寻找布线路径-111 xC:Documents and 5ettingsAdmin

12、istrator面 1 算法iPB_&SiH01DetMjgmain.eKe3 3 3 3 2 1 )2 5 n 2 3 4 5 5 5 玫：/ y yyV y n 4.- 2 5 MJ : : : : : : 卜 - - ynynyllynynyn _T7T / ,z/，z 5tz yv与IIxyxyxyx如xyxy Ex,策杭?杭次杭?杭一栋?c杭? 用禀占坐点坐点坐点坐点坐点坐点 羞半薯童宙甫贵童用 大点点有点占点占点占点占点占点占 域始束否用被用被用被用被用被用被 区开结是占有占有占有占有占有占有 入入入内入还入还入迅入还入还入还 输杏输舌输否输否输否输否 请请请E请是请是请是请是请是

13、请是-右线区域图1 -1 -1-11000-1any key M continue开始搜索路径 路径为：复杂性分析算法主要耗费在find_path()函数while循环中.最坏情况下的时间 复杂度为O(4n)。空间复杂度为O(n)。6结束语本文给出了一类电路布线问题的分支限界解法。分支限界法，对于 规模较小的问题来说，效率很高，但对规模较大的问题，它所耗费的空 间和时间都比较大。所有这些都有待于进一步通过对实际问题的解决来 积累经验。7致谢感谢我的导师罗毅老师在毕业设计期间给我的巨大帮助，是在他的 帮助下我的论文下得以完成，也感谢这期间所有帮助过我的老师同学。8参考文献吕国英主编，任瑞征钱宇华

14、参编，算法设计与分析，清华大学出版社。9附录#include #include typedef struct Position(int row;int col;Position;typedef struct team(int x;int y;struct team *next;team,*TEAM;Position start,end,path100;TEAM team_l=NULL;int a100100;int m,n,path_len;void output()int i,j;printf(n|布线区域图|n);for(i=0;im+2;i+)(for(j=0;jn+2;j+)(prin

15、tf(%5d,aij);printf(n)；printf(|n);return;void input_data()(char yes;int x,y;printf(创建布线区域.nn)；printf(请输入区域大小(行列的个数)：)；scanf(d,%d，&m,&n);printf(请输入开始点坐标(x,y):);scanf(d,%d，&start.row,&start.col);printf(请输入结束点坐标(x,y):);scanf(d,%d，&end.row,&end.col);printf(-区域内是否有被占用点？(y/n);fflush(stdin);scanf(%c,&yes);f

16、flush(stdin);while(yes=y)(printf(请输入占用点的坐标(x,y):);scanf(%d,%d,&x,&y);fflush(stdin);if(xm+1 | yn+1 | (x=start.row & y=start.col) | (x=end.row & y=end.col)(printf（输入错误，请重新输入n）; continue;else(axy=-1;printf(是否还有被占用点？(y/n);scanf(c,&yes);fflush(stdin);for(x=0;xm+2;x+)(a0 x=-1;am+1x=-1;for(x=0;xx=p.row;t-y

17、=p.col;t-next=NULL;if(team_l=NULL)(team_l=t;return ;while(q-next!=NULL)q=q-next;q-next=t;return;Position outq()(Position out;out.row=team_l-x;out.col=team_l-y;team_l=team_l-next;return out;void find_path()(Position offset4;Position here=start.row,start.col;Position nbr=(0,0;int num_of_nbrs=4;int i,j

18、;offset0.row=0;offset0.col=1; /右offset1.row=1;offset1.col=0; /下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上printf(n开始搜索路径.n);if(start.row = end.row)&(start.col = end.col)( path_len = 0;return;while(1)(for(i=0;i=0;j-)(pathj = here;for(i = 0;i num_of_nbrs;i+)(nbr.row = here.row + offseti.row;nbr.col = here