实验二 电路布线问题

1、实验二 电路布线问题班级：计算机1405 组别：4 姓名：刘诚阳 学号：201437121. 问题定义及需求分析1.1课题目的和任务问题描述：印刷电路板将布线区域划分为nn个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为a，终止位置为b，求解电路布线问题。实验要求：设计印刷电路板的布线模拟程序。1)采用栈或队列等数据结构。2)采用穷举法的回溯搜索，求a到b可能的布线线路。3)推荐采用层次优先搜索，求a到b最优的布线线路。1.2数据形式输入数据形式：通过生成随机数的函数随机生成一个矩阵。输入值的范围：生成的矩阵中的数值为int型，为0或者1，

2、其中0表示死路，1表示通路。 输出数据形式：输出到显示器。1.3程序功能随机给定一个线路分布矩阵，利用穷举法，通过栈的应用，求出从a到b的可能布线线路；采用层次优先搜索，通过队列的应用，求出a到b的最优布线线路。1.4测试数据测试数据为随机生成的矩阵。2. 概要设计2.1抽象数据类型需要定义一个位置类型的数据，里面包含int型的x和y坐标，用来记录位置信息；再定义一个SWire的通道块数据类型，里面包含该通道块的位置数据，在路径上的序号和方向信息；另外还需要构建栈和队列的基本结构类型。2.2主程序流程及各模块之间的调用关系3. 详细设计3.1存储结构实现typedef struct/位置 in

3、t x; int y;Position;typedef struct/移动标记 int ord; Position seat; int di;SWire;typedef struct/栈 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/队列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;LinkQ;3.2负责模块的伪码算法（1）int WirePath(int* Board,Position start,P

4、osition finish)/寻找路径算法/若有从电路板的入口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(电路板的搜寻图) return 1;/返

5、回 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.di<5) e.di+; Push(S,e); /换下一个方向探索 NextPos(e.seat,e.di);/设定当前位置是该新方向/上的相邻块 curpos.x=e.seat.x; curpos.y=e.seat.y; whi

6、le(S.base!=S.top);printf(没有通路);printf(电路板的搜寻图); return 0;（2）int FindShortWay(int* Board,Position start,Position finish)/搜寻最短布线路径算法 if(finish=start)/到达终点，结束 MShortPath=0; return 1; curpos=start;/标记当前位置 if(Boardstart.xstart.y=0)没有通路!return 0; Boardstart.xstart.y=2;/有通路，则令其值为2while(1)/将第一个通道块赋值2，并将其相邻通

7、道块从右开始，按顺时/针依次入队列，当队列不空时，出队列一个通道块，对其相邻通道块做相/同操作，直至所有的未标记通路通道块都被标记后为止。 for(i=1;i<5;i+)/对其相邻通道块赋值 neighbour=curpos; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour.y=-3)/该通道块可通过且未标记 Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1;/

8、值+1 if(neighbour=finish)break;/到达终点，结束 EnQ(Q,neighbour);/将该通道块入队列 /if /for if(neighbour=finish)break;/已全部标记，结束循环 if(Q.fron=Q.rear)return 0;/没有通路，结束 DeQ(Q,curpos);/出队列 /while /反向搜寻最短布线路径 MShortPath=Boardneighbour.xneighbour.y-2; pathMShortPath=(0,0);curpos=finish;/标记当前位置为结束位置 for(j=MShortPath-1;j>

9、=0;j-)/反向搜索最短路径 pathj=curpos; for(i=0;i<5;i+)/在相邻通道块中找符合的标记值 neighbour=curpos; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=j+2)break; curpos=neighbor;/当前位置为相邻通道块 printf(输出最短布线路径); printf(输出最短路径搜寻矩阵); return 1;4. 调试分析4.1问题分析与解决方法(1)寻找可能路径若当前位置可通过，则纳入当前路径，并继续朝着下一位置探索，即切换下一位置为当前位置，如此重复直至到达出

10、口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。所谓下一位置指的是当前位置四周4个方向（东南西北）上相邻的方块。假设以栈S记录当前路径，则栈顶中存放的是当前路径上的最后一个通道块。由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。通过入栈和出栈操作，使得当前位置找寻到出口位置，从而实现对迷宫一个可能路径的求解。(2)寻找最优路径 标记当前位置，通过队列，将当前位置周围的四个通道块入队列，将当前位置标记值m后，出队列，对该通道块执行相同的操作，并标记值m+，通过

11、循环操作，直到当前位置为出口时终止。借助队列，通过循环操作，使每个通道块都被赋值。然后标记当前位置为出口，从出口向入口寻找符合递减值的通道块，从而确定出最短路径。4.2算法的时空分析（1）寻找可能路径时间复杂度：空间复杂度：（2）寻找最优路径时间复杂度：空间复杂度：4.3算法的改进设想通过对搜寻可能路径的算法改进，实现能够同时输出多条可能路径的功能。而最优路径也有可能有多条，因此可以改进搜索最优路径的算法，使其能够输出全部的最优路径。可以考虑加入多重标记的方法实现。4.4经验和体会 电路板布线问题实际上就是迷宫求解问题，电路板上的布线要求可以转化成迷宫的通路和不通路的问题，当电线可以经过该点时

12、，该点即为通路，而当电线不能经过该点时，它即为死路，利用1,0分别表示通路和死路，就可以建立类似迷宫求解的模型，通过栈和队列的一系列数据结构的辅助，来求解迷宫问题。5. 使用说明运行程序，系统会自动给出一个随机电路板矩阵，自动输出一个可能的布线路径和最优布线路径，并给出搜寻路径的标记图；若该电路板不存在可行路径，则会提示没有通路。6. 测试结果（截屏）（1）随机生成的电路板矩阵：（2）可能布线路径：（3）最短布线路径：7. 附录7.1个人负责模块的程序代码int WirePath(int* Board,Position start,Position finish)/寻找路径算法 int i,j

13、; Stack S; SWire e; Position curpos; int curstep; 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

14、.y=finish.y)/到达终点 PrintStack(S); printf("n搜寻路径图(-3表示布线，-1表示死路）：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1; NextPos(curpos,1);/下一个位置是当前位置的东邻 curstep+;/探索下一步 else/当前位置不能通过 Pop(S,e); if(S.top!=S.base) while(e.di=5&&S.top

15、!=S.base) MarkPrint(e.seat);/留下不能通过标记 Pop(S,e);/退一步 if(e.di<5) 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("没有通路!nn搜寻路径图(-3表示布线，-1表示死路）：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt&qu

16、ot;,Boardij); printf("n"); return 0;int FindShortWay(int* Board,Position start,Position finish)/搜寻最短布线路径算法 if(finish.x=start.x&&finish.y=start.y)/起点为终点，结束 MShortPath=0; return 1; LinkQ Q; InitQ(Q); int i; Position curpos,neighbour; curpos.x=start.x;curpos.y=start.y;/设定起始位置为当前位置 if(

17、Boardstart.xstart.y=0)printf("没有通路!n");return 0; Boardstart.xstart.y=2;while(1)/利用队列，将每个通道块都做上标记，起点标记为2，其余按到达步数依次累加 for(i=1;i<5;i+) neighbour.x=curpos.x; neighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour

18、.y=-3)/当前通道块可探索 Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1;/标记 if(neighbour.x=finish.x&&neighbour.y=finish.y)break;/如果邻接通道块为终点，则结束循环 EnQ(Q,neighbour);/该通道块入队列 /if /for if(neighbour.x=finish.x&&neighbour.y=finish.y)break; if(Q.fron=Q.rear)printf("没有通路!n");return 0;/

19、所有通道块均被标记，结束 DeQ(Q,curpos);/出队列 /while /反向搜寻最短布线路径 MShortPath=Boardneighbour.xneighbour.y-2; Position pathMShortPath+1; pathMShortPath.x=0; pathMShortPath.y=0; curpos.x=finish.x; curpos.y=finish.y; int j; for(j=MShortPath-1;j>=0;j-)/反向搜寻符合值 pathj=curpos; for(i=0;i<5;i+) neighbour.x=curpos.x; n

20、eighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=j+2)break;/符合即结束记录 curpos.x=neighbour.x; curpos.y=neighbour.y; /输出最短布线路径 printf("(1,1)->"); for(i=0;pathi.x!=0&&pathi.y!=0;i+) printf("(%d,%d)",pathi.x,pathi.y); if(pathi.x!=8|pathi.y!=8)printf(&

21、quot;->"); printf("n"); /输出最短路径搜寻矩阵 printf("n搜寻路径图：n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1;7.2程序全部代码#include<stdio.h>#include<iostream>using namespace std;#include<stdlib.h>#include<t

22、ime.h>#define SIZE 100#define INCH 10typedef struct/位置 int x; int y;Position;typedef struct/移动标记 int ord; Position seat; int di;SWire;typedef struct/栈 SWire* base; SWire* top; int stacksize;Stack;typedef struct QNode/队列 Position data; struct QNode* next;QNode,*QP;typedef struct QP fron; QP rear;L

23、inkQ;int* Board;/电路板int MShortPath;/最短路径const int n=10;/电路板大小int CreateBoard()/创建一个电路板 int i,j; Board=(int*)malloc(sizeof(int*)*(n); for(i=0;i<n;i+) Boardi=(int*)malloc(sizeof(int)*(n); i=0; srand(time(NULL); for(i=0;i<n;i+) for(j=0;j<n;j+) if(i=0|i=n-1|j=0|j=n-1) Boardij=0; else Boardij=1;

24、 if(rand()%2=0) if(rand()%2=0) Boardij=0; printf("随机生成的10X10电路板的分布情况为（1可通，0不可通）:n"); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 1;int DestroyBoard()/摧毁电路板 free(Board); return 0;int InitStack(Stack &S)/创建空栈 S.base=(SWire*)malloc(

25、SIZE*sizeof(SWire); if(!S.base)return(0); S.top=S.base; S.stacksize=SIZE; return 1;int Pass(Stack& S,Position f)/电线通过判定 if(Boardf.xf.y=0|Boardf.xf.y=-3|Boardf.xf.y=-1)return 0; return 1;int FootPrint(Position f)/布线 Boardf.xf.y=-3; return 1;int Push(Stack &S,SWire e)/入栈 if(S.top-S.base>=S.

26、stacksize) S.base=(SWire*)realloc(S.base,(S.stacksize+INCH)*sizeof(SWire); if(!S.base)return(0); S.top=S.base+S.stacksize; S.stacksize+=INCH; *S.top=e; S.top+; return 1;int Pop(Stack &S,SWire &e)/出栈 if(S.base=S.top)return(0); e=*(-S.top); return 1;int NextPos(Position& f,int i)/1=EAST,2=

27、SOURTH,3=WEST,4=NORTH/尝试相邻位置 if(i=1)f.y+; if(i=2)f.x+; if(i=3)f.y-; if(i=4)f.x-; return 1;int MarkPrint(Position f)/留下不可布线的标志 Boardf.xf.y=-1; return 1;int PrintStack(Stack& S)/输出栈内存储的布线路径 do printf("(%d,%d)",S.base->seat.x,S.base->seat.y); if(S.base->seat.x=8&&S.base-&

28、gt;seat.y=8) else printf("->"); S.base+; while(S.top!=S.base); printf("n"); return 1;int WirePath(int* Board,Position start,Position finish)/寻找路径算法 int i,j; Stack S; SWire e; Position curpos; int curstep; InitStack(S); curpos.x=start.x; curpos.y=start.y; curstep=1; do if(Pass(

29、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;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"

30、;); return 1; 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.di<5) 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("没有通路!nn搜寻路径图(-3表示布线，-1表示死路）：n&q

31、uot;); for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%dt",Boardij); printf("n"); return 0;/队列int InitQ(LinkQ& Q)/创建空队列 Q.fron=Q.rear=(QP)malloc(sizeof(QNode); if(!Q.fron)return 0; Q.fron->next=NULL; return 1;int DestroyQ(LinkQ& Q)/摧毁队列 while(Q.fron) Q.rear=Q.fron->n

32、ext; free(Q.fron); Q.fron=Q.rear; return 1;int EnQ(LinkQ& Q,Position e)/入队列 QP p; p=(QP)malloc(sizeof(QNode); if(!p)return 0; p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return 1;int DeQ(LinkQ& Q,Position& e)/出队列 if(Q.fron=Q.rear)return 0; QP p; p=Q.fron->next; e=p->

33、;data; Q.fron->next=p->next; if(Q.rear=p)Q.rear=Q.fron; free(p); return 1;int FindShortWay(int* Board,Position start,Position finish)/搜寻最短布线路径算法 if(finish.x=start.x&&finish.y=start.y) MShortPath=0; return 1; LinkQ Q; InitQ(Q); int i; Position curpos,neighbour; curpos.x=start.x;curpos.y

34、=start.y; if(Boardstart.xstart.y=0)printf("没有通路!n");return 0; Boardstart.xstart.y=2; while(1) for(i=1;i<5;i+) neighbour.x=curpos.x; neighbour.y=curpos.y; NextPos(neighbour,i); if(Boardneighbour.xneighbour.y=1|Boardneighbour.xneighbour.y=-1|Boardneighbour.xneighbour.y=-3) Boardneighbour.xneighbour.y=Boardcurpos.xcurpos.y+1; if(neighbour.x=finish.x&&neighbour.y=fini