《实验二 电路布线问题》由会员分享，可在线阅读，更多相关《实验二 电路布线问题（18页珍藏版）》请在金锄头文库上搜索。
1、实验二电路布线问题1. 问题定义及需求分析1.1课题目的和任务问题描述：印刷电路板将布线区域划分为nXn个方格阵列。在布线时，电路只 能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。 设起始位置为a,终止位置为b,求解电路布线问题。实验要求：设计印刷电路板的布线模拟程序。1）采用栈或队列等数据结构。2）采用穷举法的回溯搜索，求a到b可能的布线线路。3）推荐采用层次优先搜索，求a到b最优的布线线路。1.2数据形式输入数据形式：通过生成随机数的函数随机生成一个矩阵。输入值的范围：生成的矩阵中的数值为int型，为0或者1，其中0表 示死路，1表示通路。输出数据形式：输出到显示器。1.3
2、程序功能随机给定一个线路分布矩阵，利用穷举法，通过栈的应用，求出从 a到b的可能布线线路；采用层次优先搜索，通过队列的应用，求出a 到b的最优布线线路。1.4测试数据测试数据为随机生成的矩阵。2. 概要设计2.1抽象数据类型需要定义一个位置类型的数据，里面包含int型的x和y坐标，用来 记录位置信息；再定义一个SWire的通道块数据类型，里面包含该通 道块的位置数据，在路径上的序号和方向信息；另外还需要构建栈和 队列的基本结构类型。2.2主程序流程及各模块之间的调用关系开始随机生成电路板矩 多阵 CreateBoard()利用栈搜索可能路 ，径 WirePath()输出可能路/径和搜索图利用队
3、列搜索最短路径 FindShortway()输出可能路径和搜索图3. 详细设计3.1存储结构实现typedef 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 structQP fron;QP rear;L
4、inkQ;3.2负责模块的伪码算法(1) int WirePath(int* Board,Position start,Position 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)
5、/到达出口(终点)PrintStack(S);/输出路径Printf(电路板的搜寻图)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.di5)e.di+;Push(S,e);/换下一个方向探索NextPos(e.seat,e.di);/设定当前位置是该新方向 上的相邻块curpos.x=e.se
6、at.x;curpos.y=e.seat.y;while(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;/有通路，则令其值为 2
7、while(1)(/将第一个通道块赋值2,并将其相邻通道块从右开始，按顺时 针依次入队列，当队列不空时，出队列一个通道块，对其相邻通道块做相 /同操作，直至所有的未标记通路通道块都被标记后为止。for(i=1;i=0;j-)(/反向搜索最短路径pathj=curpos;for(i=0;i5;i+)/在相邻通道块中找符合的标记值neighbour二curpos;NextPos(neighbour,i);if(Boardneighbour.xneighbour.y=j+2)break;curpos=neighbor;/当前位置为相邻通道块printf(输出最短布线路径)；printf(输出最短路径
8、搜寻矩阵)；return 1;4. 调试分析4.1问题分析与解决方法(1) 寻找可能路径若当前位置可通过，则纳入当前路径，并继续朝着下一位置探索，即切 换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应 顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若 该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。所谓 下一位置指的是当前位置四周4个方向(东南西北)上相邻的方块。假设以 栈S记录当前路径，则栈顶中存放的是当前路径上的最后一个通道块。由此， 纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即 为出栈。通过入栈和出栈操作，使得当前位
9、置找寻到出口位置，从而实现对 迷宫一个可能路径的求解。(2) 寻找最优路径标记当前位置，通过队列，将当前位置周围的四个通道块入队列，将当 前位置标记值m后，出队列，对该通道块执行相同的操作，并标记值m+， 通过循环操作，直到当前位置为出口时终止。借助队列，通过循环操作，使 每个通道块都被赋值。然后标记当前位置为出口，从出口向入口寻找符合递 减值的通道块，从而确定出最短路径。4.2算法的时空分析(1) 寻找可能路径时间复杂度：O (h2 )空间复杂度：O (1)(2) 寻找最优路径时间复杂度：O(n2)空间复杂度：O （1）4.3算法的改进设想通过对搜寻可能路径的算法改进，实现能够同时输出多条可
10、能路径的功 能。而最优路径也有可能有多条，因此可以改进搜索最优路径的算法，使其 能够输出全部的最优路径。可以考虑加入多重标记的方法实现。4.4经验和体会电路板布线问题实际上就是迷宫求解问题，电路板上的布线要求可以转化成 迷宫的通路和不通路的问题，当电线可以经过该点时，该点即为通路，而当 电线不能经过该点时，它即为死路，利用1,0分别表示通路和死路，就可以 建立类似迷宫求解的模型，通过栈和队列的一系列数据结构的辅助，来求解 迷宫问题。5. 使用说明运行程序，系统会自动给出一个随机电路板矩阵，自动输出一个可能的布线 路径和最优布线路径，并给出搜寻路径的标记图；若该电路板不存在可行路径， 则会提示没
11、有通路。6. 测试结果（截屏）（1）随机生成的电路板矩阵:迫机生成的1LXW电跄权的力令111情沉为r1可通，。不可通）: rrnn1-11111uu) 1 1C11Cc101 1 11111c10) 1 11111c1u) 1 (|1C111101 1C111100)1U111111u) 1 111C111010(|CCCCc00（2）可能布线路径:I I mm，.l. ：-：. ：.，- .1. ：-： .! - : J-E. I.!/：-：/-. ,?-，.：，：投寻路径图c-aa示布线，-愤朋死j iQ01.1.0000000-3-3-3-3-：010001101 j00-1001111-3-30-1011111-30-1D010101-3-3-10010111-300.1L.1111-3-3001111011-300000000000（3）最短布线路径：豪短市绣路径丸搜寻路径图，000000(1000023456010003i0i7.1i16004567E90150056789w1140060S01
