实验二 电路布线问题Word文件下载.docx
《实验二 电路布线问题Word文件下载.docx》由会员分享，可在线阅读，更多相关《实验二 电路布线问题Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
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）;
//留下不能通过得标记,并退回一步
if（e、di<
5）{
e、di++;
//换下一个方向探索
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;
//标记当前位置
if（Board[start、x][start、y]==0）{没有通路!
return0;
Board[start、x][start、y]=2;
//有通路,则令其值为2
while
（1）{//将第一个通道块赋值2,并将其相邻通道块从右开始,按顺时
//针依次入队列,当队列不空时,出队列一个通道块,对其相邻通道块做相
//同操作,直至所有得未标记通路通道块都被标记后为止。
for（i=1;
i<
5;
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;
//值+1
if（neighbour==finish）break;
//到达终点,结束
EnQ（Q,neighbour）;
//将该通道块入队列
}//if
}//for
//已全部标记,结束循环
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=MShortPath1;
j>
=0;
j）{//反向搜索最短路径
path[j]=curpos;
for（i=0;
i++）{//在相邻通道块中找符合得标记值
if（Board[neighbour、x][neighbour、y]==j+2）{break;
curpos=neighbor;
//当前位置为相邻通道块
printf（输出最短布线路径）;
printf（输出最短路径搜寻矩阵）;
4.调试分析
4、1问题分析与解决方法
（1）寻找可能路径
若当前位置可通过,则纳入当前路径,并继续朝着下一位置探索,即切换下一位置为当前位置,如此重复直至到达出口;
若当前位置不可通,则应顺着来向退回到前一通道块,然后朝着除来向之外得其她方向继续探索;
若该通道块得四周4个方块均不可通,则应从当前路径上删除该通道块。
所谓下一位置指得就是当前位置四周4个方向（东南西北）上相邻得方块。
假设以栈S记录当前路径,则栈顶中存放得就是当前路径上得最后一个通道块。
由此,纳入路径得操作即为当前位置入栈;
从当前路径上删除前一通道块得操作即为出栈。
通过入栈与出栈操作,使得当前位置找寻到出口位置,从而实现对迷宫一个可能路径得求解。
（2）寻找最优路径
标记当前位置,通过队列,将当前位置周围得四个通道块入队列,将当前位置标记值m后,出队列,对该通道块执行相同得操作,并标记值m++,通过循环操作,直到当前位置为出口时终止。
借助队列,通过循环操作,使每个通道块都被赋值。
然后标记当前位置为出口,从出口向入口寻找符合递减值得通道块,从而确定出最短路径。
4、2算法得时空分析
时间复杂度:
空间复杂度:
4、3算法得改进设想
通过对搜寻可能路径得算法改进,实现能够同时输出多条可能路径得功能。
而最优路径也有可能有多条,因此可以改进搜索最优路径得算法,使其能够输出全部得最优路径。
可以考虑加入多重标记得方法实现。
4、4经验与体会
电路板布线问题实际上就就是迷宫求解问题,电路板上得布线要求可以转化成迷宫得通路与不通路得问题,当电线可以经过该点时,该点即为通路,而当电线不能经过该点时,它即为死路,利用1,0分别表示通路与死路,就可以建立类似迷宫求解得模型,通过栈与队列得一系列数据结构得辅助,来求解迷宫问题。
5.使用说明
运行程序,系统会自动给出一个随机电路板矩阵,自动输出一个可能得布线路径与最优布线路径,并给出搜寻路径得标记图;
若该电路板不存在可行路径,则会提示没有通路。
6.测试结果（截屏）
（1）随机生成得电路板矩阵:
（2）可能布线路径:
（3）最短布线路径:
7.附录
7、1个人负责模块得程序代码
intWirePath（int**Board,Positionstart,Positionfinish）{//寻找路径算法
inti,j;
StackS;
SWiree;
Positioncurpos;
intcurstep;
curpos、x=start、x;
curpos、y=start、y;
if（Pass（S,curpos））{//当前位置可通过,即未走过
e、ord=curstep;
e、seat、x=curpos、x;
e、seat、y=curpos、y;
e、di=1;
if（curpos、x==finish、x&
curpos、y==finish、y）{//到达终点
printf（"
\n搜寻路径图（3表示布线,1表示死路）:
\n"
）;
n;
i++）{
for（j=0;
j<
j++）{
%d\t"
Board[i][j]）;
//下一个位置就是当前位置得东邻
//留下不能通过标记
//退一步
//换下一个方向探索
//设定当前位置就是该新方向上得相邻块
没有通路!
\n\n搜寻路径图（3表示布线,1表示死路）:
intFindShortWay（int**Board,Positionstart,Positionfinish）{//搜寻最短布线路径算法
if（finish、x==start、x&
finish、y==start、y）{//起点为终点,结束
LinkQQ;
InitQ（Q）;
inti;
Positioncurpos,neighbour;
curpos、y=start、y;
//设定起始位置为当前位置
if（Board[start、x][start、y]==0）{printf（"
while
（1）{
//利用队列,将每个通道块都做上标记,起点标记为2,其余按到达步数依次累加
neighbour、x=curpos、x;
neighbour、y=curpos、y;
if（Board[neighbour、x][neighbour、y]==1||Board[neighbour、x][neighbour、y]==1||Board[neighbour、x][neighbour、y]==3）{//当前通道块可探索
//标记
if（neighbour、x==finish、x&
neighbour、y==finish、y）break;
//如果邻接通道块为终点,则结束循环
//该通道块入队列
if（Q、fron==Q、rear）{printf（"
}//所有通道块均被标记,结束
Positionpath[MShortPath+1];
path[MShortPath]、x=0;
path[MShortPath]、y=0;
curpos、x=finish、x;
curpos、y=finish、y;
intj;
j）{//反向搜寻符合值
}//符合即结束记录
curpos、x=neighbour、x;
curpos、y=neighbour、y;
//输出最短布线路径
（1,1）>
"
path[i]、x!
=0&
path[i]、y!
（%d,%d）"
path[i]、x,path[i]、y）;
if（path[i]、x!
=8||path[i]、y!
=8）{printf（"
>
//输出最短路径搜寻矩阵
\n搜寻路径图:
7、2程序全部代码
#include<
stdio、h>
iostream>
usingnamespacestd;
stdlib、h>
time、h>
#defineSIZE100
#defineINCH10
int**Board;
//电路板
intMShortPath;
//最短路径
constintn=10;
//电路板大小
intCreateBoard{//创建一个电路板
Board=（int**）malloc（sizeof（int*）*（n））;
Board[i]=（int*）malloc（sizeof（int）*（n））;
i=0;
srand（time（NULL））;
if（i==0||i==n1||j==0||j==n1）{
Board[i][j]=0;
else{
Board[i][j]=1;
if（rand%2==0）{
随机生成得10X10电路板得分布情况为（1可通,0不可通）:
intDestroyBoard{//摧毁电路板
free（Board）;
intInitStack（Stack&
S）{//创建空栈
S、base=（SWire*）malloc（SIZE*sizeof（SWire））;
if（!
S、base）return（0）;
S、top=S、base;
S、stacksize=SIZE;
intPass（Stack&
S,Positionf）{//电线通过判定
if（Board[f、x][f、y]==0||Board[f、x][f、y]==3||Board[f、x][f、y]==1）return0;
intFootPrint（Positionf）{//布线
Board[f、x][f、y]=3;
intPush（Stack&
S,SWiree）{//入栈
if（S、topS、base>
=S、stacksize）{
S、base=（SWire*）realloc（S、base,（S、stacksize+INCH）*sizeof（SWire））;
S、top=S、base+S、stacksize;
S、stacksize+=INCH;
*S、top=e;
S、top++;
intPop（Stack&
S,SWire&
e）{//出栈
if（S、base==S、top）return（0）;
e=*（S、top）;
intNextPos（Position&
f,inti）{//1=EAST,2=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;
intMarkPrint（Positionf）{//留下不可布线得标志
Board[f、x][f、y]=1;
intPrintStack（Stack&
S）{//输出栈内存储得布线路径
S、base>
seat、x,S、base>
seat、y）;
if（（S、base>
seat、x==8&
S、base>
seat、y==8））{}
elseprintf（"
S、base++;
}while（S、top!
=S、base）;
if（Pass（S,curpos））{
curpos、y==finish、y）{
升级会员 