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

实验六用分支限界法求解最短布线问题学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：（本程序在ＭｉｃｒｏｓｏｆｔＶｉｓｕａｌＣ＋＋６．０的环境下实现）一、实验内容：布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。实验要求：用分支限界法解此最短布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：（1）队列式（FIFO）（2）优先队列式。分支限界法可广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。举例说明：一个7×7方格阵列布线如下：起始位置是a=(3,2)，目标位置是b=(4,6)，阴影方格表示被封锁的方格。那么一条从a到b的最短布线方案如下图红色路径所示。a到b的最短距离是9。请思考：如何使得构造出的最短布线中的折角数量最少？ab最短布线路径示例二、算法思想：首先从点a出发向上下左右四个方向查找到点b的路径，并且每走一步便做增一标记，到达b点后，将路径长度赋给一个变量，依次递减路径长度，由b点往回查找得到路径。三、实验过程：#includeiostream#includeiomanipusingnamespacestd;structPosition{introw;intcol;};structTEAM{intx;inty;TEAM*next;};Positionstart,end,path[100];TEAM*team_l=NULL;inta[100][100];intm,n,path_len;voidOutput(){inti,j;cout\n-------------------布线区域图-------------------\n;for(i=0;im+2;i++){for(j=0;jn+2;j++){coutsetw(2)a[i][j];}coutendl;}cout------------------------------------------------\n;return;}voidInput_data(){charyes;intx,y;cout请输入区域大小(行列的个数):;cinmn;cout请输入开始点坐标(x,y):;cinstart.rowstart.col;cout请输入结束点坐标(x,y):;cinend.rowend.col;cout区域内是否有被占用点?(y/n);cinyes;while(yes=='y'){cout请输入占用点的坐标(x,y):;cinxy;if(x0||xm+1||y0||yn+1||(x==start.row&&y==start.col)||(x==end.row&&y==end.col)){cout输入错误,请重新输入!!!\n;continue;}else{a[x][y]=-1;}cout是否还有被占用点?(y/n);cinyes;}for(x=0;xm+2;x++){a[0][x]=-1;a[m+1][x]=-1;}for(x=0;xn+2;x++){a[x][0]=-1;a[x][n+1]=-1;}return;}voidInq(Positionp){TEAM*t,*q;q=team_l;t=newTEAM;t-x=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;}Positionoutq(){Positionout;out.row=team_l-x;out.col=team_l-y;team_l=team_l-next;returnout;}voidFind_path(){Positionoffset[4];Positionhere={start.row,start.col};Positionnbr={0,0};intnum_of_nbrs=4;inti,j;offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上if((start.row==end.row)&&(start.col==end.col)){path_len=0;return;}while(1){for(i=0;inum_of_nbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbr.row][nbr.col]==0){a[nbr.row][nbr.col]=a[here.row][here.col]+1;if((nbr.row==end.row)&&(nbr.col==end.col))break;Inq(nbr);//nbr入队}}if((nbr.row==end.row)&&(nbr.col==end.col))//是否到达目标位置finishbreak;if(team_l==NULL)//或节点队列是否为空{cout\n没有结果!!!\n;return;}here=outq();}path_len=a[end.row][end.col];here=end;for(j=path_len-1;j=0;j--)//往回找路径{path[j]=here;for(i=0;inum_of_nbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbr.row][nbr.col]==j)break;}here=nbr;}return;}voidOut_path(){inti;cout\n路径为:;cout(start.row,start.col);for(i=0;ipath_len;i++){cout(path[i].row,path[i].col);}coutendl;return;}voidmain(){Input_data();Output();Find_path();Out_path();Output();}四、实验结果：算法主要耗费在Find_path()函数while循环中．最坏情况下的时间复杂度为O(4n)。空间复杂度为O(n)。