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

实验六用分支限界法求解最短布线问题学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：(JME序在MicrosoftVisua1C++6.0蚊建建下龄W)一、实验内容：布线问题：印刷电路板将布线区域划分成nXm个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，己布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。实验要求：用分支限界法解此最短布线问题。分支限界法类似回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小耗费优先的方式搜索解空间树T。树T是一棵子集树或排列树。在搜索时，每个结点只有一次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有两种方式：(1)队列式(FIFO)(2)优先队列式。分支限界法可广泛应用于单源最短路径问题，最大团问题，布线问题，电路板排列问题等。举例说明：一个7X7方格阵列布线如下：起始位置是a=(3,2),目标位置是b=(4,6),阴影方格表示被封锁的方格。那么一条从a到b的最短布线方案如下图红色路径所示。a到b的最短距离是9。请思考：如何使得构造出的最短布线中的折角数量最少？最短布线路径示例二、算法思想：首先从点a出发向上下左右四个方向查找到点b的路径，并且每走一步便做增一标记,到达b点后，将路径长度赋给一个变量，依次递减路径长度，由b点往回查找得到路径。三、实验过程：#iiiclude<iostieam>#iiiclude<iomanip>usingnamespacestd;stmctPosition{introw;intcol;};stmctTEAMintx;mty;TEAM*next;}；Positionstart,end.path[100];TEAM*team_l=NULL;inta[100][100];intm,n,path_len;voidOutputQ{mtij;cout«M\n布线区域图\ir；fbi(i=0;i<m+2;i++)for(j=0j<n+2j++)(cout«setw(2)«a[i][j];}cout«endl;}cout«H\nH;retuin;}voidInput_data(){charyes;mtx,y;cout«"请输入区域大小(行列的个数):二ciii»m»n;cout«"请输入开始点坐标(x,y):”；ciii»start.iow»start.col;cout«M请输入结束点坐标(x,y):”；ciii»end.row»end.col;cout«"区域内是否有被占用点？(y/n)”；cm»yes;while(yes=,y,)jcout«M请输入占用点的坐标(x,y):”；cin»x»y；iRx<0||x>m+l||y<0||y>n+l||(x==start.row&&y=start.col)||(x==end.row&&y==end.col))coutvv”输入错误，请重新输入!!!\iT;contmue;)else(a[x][y]=-l;}cout«M是否还有被占用点？(y/n)cin»yes;}fbr(x=0;x<m+2;x++)a[0][x]=-l;a[m+l][x]=-l;}fbr(x=0;x<n+2;x++)fa[x][0]=-l;a[x][n+l]=-l;}retuin;}voidInq(Positionp){TEAM*t,*q;q=teanO；t=newTEAM;t->x=p.row;t->y=p.col;t->next=NULL;if(teamJ==NULL)team_l=t;return;}while(q->next!=NULL)q=q->next;}q->next=t;retuin;Positionoutq()Positionout;out.row=team_l・>x;out.col=team_l->y；teaml=teaml->next;returnout;}voidFmd_path(){Positionoffset[4];Positionhere=(stait.row,stan.col);Positionnbi-(0.0);intnumofnbrs=4;intij;offset[0].row=0;offset[0].col=1;〃右offsetf1].row=1;offset[1].col=0;〃下offset[2].row=0;offset[2].col=-l;//左offset[3].row=-1;offset[3].col=0;//上if((start.row==end.row)&&(start.col=end.col))patlijen=0;return;}wlule(l)fbr(i=0;i<num_ofLubrs;i-H-)(nbr.row—here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(a[nbLrow][nbr.col]==0)(a[nbr.row][nbr.col]=a[here.iow][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(teamJ=NULL)//或节点队列是否为空cout«M\n没有结果!!!";return;)here=outqQ;}path_len=a[end.row][end.col];here=end;for(j=path_len-lj>=0;j--)〃往回找路径JIpath。]=here;fbr(i=0;ivnum_oflnbrs;i-H-)(nbr.row=here.row+offset[i].row;nbr.col=heie.col+offset[i].col;if(a[nbLiow][nbr.col]=j)break;)here=nbr;}retuin;}voidOut_path0{inti;cout«H\n路径为:”;coutvv”("vvstart.rowvv-yvstart.colvv“)”；fdr(i=O;i<path_len;i++)jcout«,,(H«patli[i].row«,\li«path[i].col«H),r;}cout«endl;retuin;}voidmain(){Iiiput_data();OutputQ;Find_path();Out_path();OutputQ;)四、实验结果:-・1：\算法分析与设计\06用分支限界法求解景短布线何袈\Debug\Cppl.exe7?93345455123123>260134y<>>>>>>>>>>>>>>>>>>>>>>>>>>::ynynynynynynynynynynynynyn/，，，，，，，，，，，w二点<x<y<x<y<x<y<xE<x<y<x<y<x<y<x<y<x<y<x<y<x<y<x<y<x<y"<x<x庄标？标？标？标？标？标？标？标？标？标？标？标？标？q虐占坐占占g坐占巫占玺占g坐占座占座占座占座占塑占座占g小坐坐用的用的用的用的用的用的用的用的用的用的用的用的K占g点有占苫占苫占苫占g占占苫占苫点占占苫占苫占苫占g占占苫占小墩葬否禺黑黑塞黑黑黑黑禺黑塞塞黑IX0^1一苫有占有占有占有占有占有占有占有占有占有占有占有占有AX-^^■入正入丕入正入不一^^入正入爪一入正入丕入迅入不一^^入^蕾富蕾富蕾富蕾蕾富蕾富蕾奇值请请区菖宙l^snlAF三-1-1-1-1-1-1-1-1-1-100-10000-1-100-1-1000-1-1RRRR-lRR-1-1000-1-100-1-10000-100-10000-10000-1-1-1-1-1-1-1-1-1-1布线区域图路径为"3,2〉〈4,2〉(5,2〉＜5,3〉＜5,4〉＜6,4〉＜6,5〉＜6,6〉＜5,6〉＜4,