实验二电路布线问题

教育资料教育资料实验二电路布线问题问题定义及需求分析1.课1题目的和任务问题描述：印刷电路板将布线区域划分为X个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为，终止位置为，求解电路布线问题。实验要求：设计印刷电路板的布线模拟程序。1采）用栈或队列等数据结构。采用穷举法的回溯搜索，求到可能的布线线路。推荐采用层次优先搜索，求到最优的布线线路。.数2据形式输入数据形式：通过生成随机数的函数随机生成一个矩阵。输入值的范围：生成的矩阵中的数值为 型，为或者，其中表示死路，1表示通路。输出数据形式：输出到显示器。.程3序功能随机给定一个线路分布矩阵，利用穷举法，通过栈的应用，求出从到的可能布线线路；采用层次优先搜索，通过队列的应用，求出到的最优布线线路。.测4试数据测试数据为随机生成的矩阵。概要设计.抽1象数据类型需要定义一个位置类型的数据，里面包含型的和坐标，用来记录位置信息；再定义一个 的通道块数据类型，里面包含该通道块的位置数据，在路径上的序号和方向信息；另外还需要构建栈和队列的基本结构类型。主2程序流程及各模块之间的调用关系［开始)随机生成电路板矩

阵CreateBoard()利用栈搜索可能路

径WirePath()/输出可能路/ 径和搜索图利用队列搜索最短

路径FindShortway()/输出可能路径和搜索图详细设计3.存1储结构实现位置移动标记队列负2责模块的伪码算法寻/找路径算法若有从电路板的入口到出口 的通道，则求得一条存放在栈中(/从栈底到栈顶)InitStack(S);设定当前位置为入口位置探索第一步do{当前位置可通过，即是未曾走到的通道块留下足迹e=(curstep,curpos,1);加入路径到达出口(终点)输出路径电路板的搜寻图}返回return1;若若}下一位置是当前位置的东邻探索下一步}当前位置不能通过Pop(S,e);栈空留下不能通过的标记，并退回一步换下一个方向探索设定当前位置是该新方向/上/的相邻块没有通路电路板的搜寻图/搜寻最短布线路径算法到达终点，结束标记当前位置没有通路有通路，则令其值为将第一个通道块赋值2并将其相邻通道块从右开始，按顺时/针依次入队列，当队列不空时，出队列一个通道块，对其相邻通道块做相/同操作，直至所有的未标记通路通道块都被标记后为止。对其相邻通道块赋值该通道块可通过且未标记到达终点，结束将该通道块入队列已全部标记，结束循环没有通路，结束出队列反/向/搜寻最短布线路径标记当前位置为结束位置反向搜索最短路径th[j]=curpos;在相邻通道块中找符合的标记值当前位置为相邻通道块输出最短布线路径输出最短路径搜寻矩阵调试分析4.问1题分析与解决方法（1寻）找可能路径若当前位置可通过，则纳入当前路径，并继续朝着下一位置探索，即切换下一位置为当前位置，如此重复直至到达出口；若当前位置不可通，则应顺着来向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周4个方块均不可通，则应从当前路径上删除该通道块。所谓下一位置指的是当前位置四周4个方向（东南西北）上相邻的方块。假设以栈记录当前路径，则栈顶中存放的是当前路径上的最后一个通道块。由此，纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。通过入栈和出栈操作，使得当前位置找寻到出口位置，从而实现对迷宫一个可能路径的求解。（2寻）找最优路径标记当前位置，通过队列，将当前位置周围的四个通道块入队列，将当前位置标记值后，出队列，对该通道块执行相同的操作，并标记值 ,通过循环操作，直到当前位置为出口时终止。借助队列，通过循环操作，使每个通道块都被赋值。然后标记当前位置为出口，从出口向入口寻找符合递减值的通道块，从而确定出最短路径。.算2法的时空分析（1）寻找可能路径时间复杂度：O（n2）空间复杂度：O（1）（2）寻找最优路径时间复杂度：O（n2）空间复杂度：O（D4.算3法的改进设想通过对搜寻可能路径的算法改进，实现能够同时输出多条可能路径的功能。而最优路径也有可能有多条，因此可以改进搜索最优路径的算法，使其能够输出全部的最优路径。可以考虑加入多重标记的方法实现。4.经4验和体会电路板布线问题实际上就是迷宫求解问题，电路板上的布线要求可以转化成迷宫的通路和不通路的问题，当电线可以经过该点时，该点即为通路，而当电线不能经过该点时，它即为死路，利用1,分0别表示通路和死路，就可以建立类似迷宫求解的模型，通过栈和队列的一系列数据结构的辅助，来求解迷宫问题。使用说明运行程序，系统会自动给出一个随机电路板矩阵，自动输出一个可能的布线路径和最优布线路径，并给出搜寻路径的标记图；若该电路板不存在可行路径，则会提示没有通路。.测试结果（截屏）（1）随机生成的电路板矩阵：一-If国胜成的1DX1口电路板的分布情况为（可通,口不口J通）:) 0D000000D)11111010D)11011001D)11111101D)11111101D)1D101111D) 01011110D)1D111111D)111101110) 0D000000D（2）可能布线路径：

卜能布线踣径为1(1,D-Xl, 4)-XL5)->(2, 5)->(3,G)->(4, 6)->(5,T)->(6,7)->(T,7)->(.7,3)->(8,8)［搜寻路径图（■裱示布线,T表不死路）：0 0000000000 -3-3-3-3-30100Q 11D1-30-10 1111-3-3।-110 11111-3i"-1■-I0 L01U1-3-3-100 010111-300； L01111-3-300 1111011-3.1Q UDD0000（3）最短布线路径：信能布线踣径为।(Ln D->t3nD-X4,l)->(4n2)-)(4,3)->(4>4”>〔虫5)->(5n5)->(6,5)->(7,5)->(?n6)->(8,G]-J(Sn7)->(E,S)搜寻路径图.0 D000000000 2a45601000 34067001600 4567B901500 57891001400 60801011121300 D1121112L30001014131213L41500 111514014L51600 00ii0iiiaProcessreturosc10go：BxscutinntlDDUB：0.798Pres2anykeytc\cantinue.附录.个1人负责模块的程序代码寻找路径算法设定当前位置为入口位置探索第一步当前位置可通过，即未走过

留下足迹加入路径到达终点PrintStack(S);搜寻路径图 表示布线，表示死路)：下一个位置是当前位置的东邻探索下一步}当前位置不能通过留下不能通过标记退一步Pop(S,e)换下一个方向探索设定当前位置是该新方向上的相邻块没有通路 搜寻路径图 表示布线，表示死路):路径算法搜寻最短布线起点为终点，结束设定起始位置为当前位置没有通路/利用队列，将每个通道块都做上标记，起点标记为2，其余按到达步数依次累加当前通道块可探索标记如/果邻接通道块为终点，则结束循环该通道块入队列没有通路所有通道块均被没有通路标记，结束出队列反/向搜/寻最短布线路径输出/最/短布线路径输出/最/短路径搜寻矩阵搜寻路径图：程2序全部代码反向搜寻符合值符合即结束记位置移动标记队列电路板最短路径电路板大小创建一个电路板随机生成的 电路板的分布情况为（可通，不可通）摧毁电路板创建空栈电线通过判定布线入栈出栈尝试相邻位置留下不可布线的标志输出栈内