C++用分支限界法求解最短布线问题.doc

《C++用分支限界法求解最短布线问题.doc》由会员分享，可在线阅读，更多相关《C++用分支限界法求解最短布线问题.doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-dateC+用分支限界法求解最短布线问题C+用分支限界法求解最短布线问题实验六 用分支限界法求解最短布线问题学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： （本程序在的环境下实现）一、实验内容：布线问题：印刷电路板将布线区域划分成nm个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避

2、免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。实验要求：用分支限界法解此最短布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO） （2）优先队列式。分支限界法可广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。举例说明：一个77方格阵列布线如下：起始位置是a = (3,2

3、)，目标位置是b = (4,6)，阴影方格表示被封锁的方格。那么一条从a到b的最短布线方案如下图红色路径所示。a到b的最短距离是9。请思考：如何使得构造出的最短布线中的折角数量最少？ a b 最短布线路径示例二、算法思想： 首先从点a出发向上下左右四个方向查找到点b的路径，并且每走一步便做增一标记，到达b点后，将路径长度赋给一个变量，依次递减路径长度，由b点往回查找得到路径。三、实验过程：#include#includeusing namespace std;struct Positionint row;int col;struct TEAMint x;int y;TEAM *next;Pos

4、ition start,end,path100;TEAM *team_l=NULL;int a100100;int m,n,path_len;void Output()int i,j;coutn-布线区域图-n;for(i=0;im+2;i+)for(j=0;jn+2;j+)coutsetw(2)aij;coutendl;cout-n;return;void Input_data()char yes;int x,y;coutmn;coutstart.rowstart.col;coutend.rowend.col;coutyes;while(yes=y)coutxy;if(xm+1 | yn+1

5、 | (x=start.row & y=start.col) | (x=end.row & y=end.col) cout输入错误,请重新输入!n;continue;elseaxy=-1;coutyes;for(x=0;xm+2;x+)a0x=-1;am+1x=-1;for(x=0;xx=p.row;t-y=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.co

6、l=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;offset0.row=0;offset0.col=1; /右offset1.row=1;offset1.col=0; /下offset2.row=0;offset2.col=-1;/左offset3.row=-1;offset3.col=0;/上if(start.row = end.row)&(

7、start.col = end.col)path_len = 0;return;while(1)for(i=0;inum_of_nbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(anbr.rownbr.col=0)anbr.rownbr.col=ahere.rowhere.col + 1;if(nbr.row = end.row) & (nbr.col = end.col)break;Inq(nbr); /nbr入队if(nbr.row = end.row) & (nbr.col = end.col)/是否

8、到达目标位置finishbreak;if(team_l=NULL)/或节点队列是否为空 cout=0;j-)/往回找路径pathj = here;for(i = 0;i num_of_nbrs;i+)nbr.row = here.row + offseti.row;nbr.col = here.col + offseti.col;if(anbr.rownbr.col = j) break;here=nbr;return;void Out_path()int i;coutn路径为:;cout(start.row,start.col);for(i=0;ipath_len;i+)cout(pathi.row,pathi.col);coutendl;return;void main()Input_data();Output();Find_path();Out_path();Output();四、实验结果：算法主要耗费在Find_path()函数while循环中最坏情况下的时间复杂度为O(4n)。空间复杂度为O(n)。-