实验二-电路布线问题

实验二电路布线问题1.问题定义及需求分析1.1课题目的和任务问题描述：印刷电路板将布线区域划分为n╳n个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为a，终止位置为b，求解电路布线问题。实验要求：设计印刷电路板的布线模拟程序。1)采用栈或队列等数据结构。2)采用穷举法的回溯搜索，求a到b可能的布线线路。3)推荐采用层次优先搜索，求a到b最优的布线线路。1.2数据形式输入数据形式：通过生成随机数的函数随机生成一个矩阵。输入值的范围：生成的矩阵中的数值为int型，为0或者1，其中0表示死路，1表示通路。输出数据形式：输出到显示器。1.3程序功能随机给定一个线路分布矩阵，利用穷举法，通过栈的应用，求出从a到b的可能布线线路；采用层次优先搜索，通过队列的应用，求出a到b的最优布线线路。1.4测试数据测试数据为随机生成的矩阵。2.概要设计2.1抽象数据类型需要定义一个位置类型的数据，里面包含int型的x和y坐标，用来记录位置信息；再定义一个SWire的通道块数据类型，里面包含该通道块的位置数据，在路径上的序号和方向信息；另外还需要构建栈和队列的基本结构类型。2.2主程序流程及各模块之间的调用关系开始随机生成电路板矩阵CreateBoard()利用栈搜索可能路径WirePath()输出可能路径和搜索图利用队列搜索最短路径FindShortway()输出可能路径和搜索图结束3.详细设计3.1存储结构实现typedefstruct{//位置intx;inty;}Position;typedefstruct{//移动标记intord;Positionseat;intdi;}SWire;typedefstruct{//栈SWire*base;SWire*top;intstacksize;}Stack;typedefstructQNode{//队列Positiondata;structQNode*next;}QNode,*QP;typedefstruct{QPfron;QPrear;}LinkQ;3.2负责模块的伪码算法（1）intWirePath(int**Board,Positionstart,Positionfinish){//寻找路径算法//若有从电路板的入口start到出口end的通道，则求得一条存放在栈中//（从栈底到栈顶）InitStack(S);curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步do{if(Pass(S,curpos)){//当前位置可通过，即是未曾走到的通道块FootPrint(curpos);//留下足迹e=(curstep,curpos,1);Push(S,e);//加入路径if(curpos==finish){//到达出口（终点）PrintStack(S);//输出路径Printf(电路板的搜寻图)}return1;//返回}NextPos(curpos,1);//下一位置是当前位置的东邻curstep++;//探索下一步}else{//当前位置不能通过Pop(S,e);if(S.top!=S.base){//栈空while(e.di==5&&S.top!=S.base){MarkPrint(e.seat);Pop(S,e);//留下不能通过的标记，并退回一步}}if(e.di5){e.di++;Push(S,e);//换下一个方向探索NextPos(e.seat,e.di);//设定当前位置是该新方向//上的相邻块curpos.x=e.seat.x;curpos.y=e.seat.y;}}}while(S.base!=S.top);printf(没有通路);printf(电路板的搜寻图);return0;}（2）intFindShortWay(int**Board,Positionstart,Positionfinish){//搜寻最短布线路径算法if(finish==start){//到达终点，结束MShortPath=0;return1;}curpos=start;//标记当前位置if(Board[start.x][start.y]==0){没有通路!return0;}Board[start.x][start.y]=2;//有通路，则令其值为2while(1){//将第一个通道块赋值2，并将其相邻通道块从右开始，按顺时//针依次入队列，当队列不空时，出队列一个通道块，对其相邻通道块做相//同操作，直至所有的未标记通路通道块都被标记后为止。for(i=1;i5;i++){//对其相邻通道块赋值neighbour=curpos;NextPos(neighbour,i);if(Board[neighbour.x][neighbour.y]==1||Board[neighbour.x][neighbour.y]==-1||Board[neighbour.x][neighbour.y]==-3){//该通道块可通过且未标记Board[neighbour.x][neighbour.y]=Board[curpos.x][curpos.y]+1;//值+1if(neighbour==finish)break;//到达终点，结束EnQ(Q,neighbour);//将该通道块入队列}//if}//forif(neighbour==finish)break;//已全部标记，结束循环if(Q.fron==Q.rear){return0;}//没有通路，结束DeQ(Q,curpos);//出队列}//while//反向搜寻最短布线路径MShortPath=Board[neighbour.x][neighbour.y]-2;path[MShortPath]=(0,0);curpos=finish;//标记当前位置为结束位置for(j=MShortPath-1;j=0;j--){//反向搜索最短路径path[j]=curpos;for(i=0;i5;i++){//在相邻通道块中找符合的标记值neighbour=curpos;NextPos(neighbour,i);if(Board[neighbour.x][neighbour.y]==j+2){break;}}curpos=neighbor;//当前位置为相邻通道块}printf(输出最短布线路径);printf(输出最短路径搜寻矩阵);return1;}4.调试分析4.1问题分析与解决方法(1)寻找可能路径若当前位置可通过，则纳入当前路径，并继续朝着下一位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。所谓下一位置指的是当前位置四周4个方向（东南西北）上相邻的方块。假设以栈S记录当前路径，则栈顶中存放的是当前路径上的最后一个通道块。由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。通过入栈和出栈操作，使得当前位置找寻到出口位置，从而实现对迷宫一个可能路径的求解。(2)寻找最优路径标记当前位置，通过队列，将当前位置周围的四个通道块入队列，将当前位置标记值m后，出队列，对该通道块执行相同的操作，并标记值m++，通过循环操作，直到当前位置为出口时终止。借助队列，通过循环操作，使每个通道块都被赋值。然后标记当前位置为出口，从出口向入口寻找符合递减值的通道块，从而确定出最短路径。4.2算法的时空分析（1）寻找可能路径时间复杂度：2On空间复杂度：1O（2）寻找最优路径时间复杂度：2On空间复杂度：1O4.3算法的改进设想通过对搜寻可能路径的算法改进，实现能够同时输出多条可能路径的功能。而最优路径也有可能有多条，因此可以改进搜索最优路径的算法，使其能够输出全部的最优路径。可以考虑加入多重标记的方法实现。4.4经验和体会电路板布线问题实际上就是迷宫求解问题，电路板上的布线要求可以转化成迷宫的通路和不通路的问题，当电线可以经过该点时，该点即为通路，而当电线不能经过该点时，它即为死路，利用1,0分别表示通路和死路，就可以建立类似迷宫求解的模型，通过栈和队列的一系列数据结构的辅助，来求解迷宫问题。5.使用说明运行程序，系统会自动给出一个随机电路板矩阵，自动输出一个可能的布线路径和最优布线路径，并给出搜寻路径的标记图；若该电路板不存在可行路径，则会提示没有通路。6.测试结果（截屏）（1）随机生成的电路板矩阵：（2）可能布线路径：（3）最短布线路径：7.附录7.1个人负责模块的程序代码intWirePath(int**Board,Positionstart,Positionfinish){//寻找路径算法inti,j;StackS;SWiree;Positioncurpos;intcurstep;InitStack(S);//设定当前位置为入口位置curpos.x=start.x;curpos.y=start.y;curstep=1;//探索第一步do{if(Pass(S,curpos)){//当前位置可通过，即未走过FootPrint(curpos);//留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=1;Push(S,e);//加入路径if(curpos.x==finish.x&&curpos.y==finish.y){//到达终点PrintStack(S);printf(\n搜寻路径图(-3表示布线，-1表示死路）：\n);for(i=0;in;i++){for(j=0;jn;j++){printf(%d\t,Board[i][j]);}printf(\n);}return1;}NextPos(curpos,1);//下一个位置是当前位置的东邻curstep++;//探索下一步}else{//当前位置不能通过Pop(S,e);if(S.top!=S.base){while(e.di==5&&S.top!=S.base){MarkPrint(e.seat);//留下不能通过标记Pop(S,e);//退一步}}if(e.di5){e.di++;Push(S,e);//换下一个方向探索NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻块curpos.x=e.seat.x;curpos.y=e.seat.y;}}}while(S.base!=S.top);printf(没有通路!\n\n搜寻路径图(-3表示布线，-1表示死路）：\n);for(i=0;in;i++){for(j=0;jn;j++){printf(%d\t,Board[i][j]);}printf(\n);}return0;}intFindShortWay(int**Board,Positionstart,Positionfinish){//搜寻最短布线路径算法if(finish.x==start.x&&finish.y==start.y){//起点为终点，结束MShortPath=0;return1;}LinkQQ;InitQ(Q);inti;Positioncurpos,neighbour;curpos.x=start.x;curpos.y=start.y;//设定起始位置为当前位置if(Board[start.x][start.y]==0){printf(没有通路!\n);return0;}Board[start.x][start.y]=2;while(1){//利用队列，将每个通道块都做上标记，起点标记为2，其余按到达步数依次累加for(i=1;i5;i++){neighbour.x=curpos.x;neighbour.y=curpos.y;NextPos(neighbour,i);if(Board[neig