分支限界法求布线问题

布线问题：如图1所示，印刷电路板将布线区域划分成n*m个方格。精确的电路布线问题要求确定连接方格a的中点到b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图1所示。为了避免线路相交，已经布线的方格做了封锁标记（如图1中阴影部分），其他线路不允许穿过被封锁的方格。3问题的算法选择题目的要求是找到最短的布线方案，从图1的情况看，可以用贪婪算法解决问题，也就是从a开始朝着b的方向垂直布线即可。实际上，再看一下图2，就知道贪婪算法策略是行不通的。因为已布线的放个没有规律的所以直观上说只能用搜索方法去找问题的解。根据布线方法的要求，除边界或已布线处，每个E-结点分支扩充的方向有4个：上、下、左、右，也就是说，一个E-结点扩充后最多产生4个活结点。以图2的情况为例，图的搜索过程如图3所示。搜索以a为第一个E-结点，以后不断扩充新的活结点，直到b结束（当然反之也可以）。反过来从b到a，按序号8-7-6-5-4-3-2-1就可以找到最短的布线方案。从图3中也可以发现最短的布线方案是不唯一的。且由此可以看出，此问题适合用分支限界搜索。#includestdio.h#includestdlib.htypedefstructPosition{introw;intcol;}Position;typedefstructteam{intx;inty;structteam*next;}team,*TEAM;Positionstart,end,path[100];TEAMteam_l=NULL;inta[100][100];intm,n,path_len;voidoutput(){inti,j;printf(\n|-------------------布线区域图-------------------|\n);for(i=0;im+2;i++){for(j=0;jn+2;j++){printf(%5d,a[i][j]);}printf(\n);}printf(|------------------------------------------------|\n);return;}voidinput_data(){charyes;intx,y;printf(创建布线区域...\n\n);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);fflush(stdin);while(yes=='y'){printf(请输入占用点的坐标(x,y):);scanf(%d,%d,&x,&y);fflush(stdin);if(x0||xm+1||y0||yn+1||(x==start.row&&y==start.col)||(x==end.row&&y==end.col)){printf(输入错误,请重新输入!!!\n);continue;}else{a[x][y]=-1;}printf(是否还有被占用点?(y/n));scanf(%c,&yes);fflush(stdin);}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){TEAMt,q;q=team_l;t=(TEAM)malloc(sizeof(TEAM));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;//上printf(\n开始搜索路径...\n);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入队}}//是否到达目标位置finishif((nbr.row==end.row)&&(nbr.col==end.col))break;//或节点队列是否为空if(team_l==NULL){printf(\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)//+2)break;}here=nbr;}return;}voidout_path(){inti;printf(\n路径为:\n);printf((%d,%d),start.row,start.col);for(i=0;ipath_len;i++){printf((%d,%d),path[i].row,path[i].col);}printf(\n);return;}voidmain(){input_data();output();find_path();out_path();output();}