算法分析与实验报告

《算法分析与实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2012级网络工程严坤222012321210160平时作业三：利用分支限界法解决布线问题问题描述：布线问题：印刷电路板将布线区域划分成n×m个方格阵列，要求确定连接方格阵列中的方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。解决算法及代码：#include"stdafx.h" #include #include usingnamespacestd; typedefstruct{ i

2、ntrow; intcol; }Position; typedefstruct{ introw[10000]; intcol[10000]; int7/72012级网络工程严坤222012321210160end; intbegin; }Queue; intgrid[100][100]; Positionstart,finish; intPathLen=0; Position*path; intn,m,a,b,x; boolFindPath(Positionstart,Positionfinish){//计算从起点位置st

3、art到目标位置finish的最短布线路径，找到最短布线路//径则返回true，否则返回false if((start.row==finish.row)&&(start.col==finish.col)){ PathLen=0; returntrue; }//start=finish //设置方格阵列“围墙” inti; for(i=0;i<=m+1;i++) grid[0][i]=grid[n+1][i]=1;//顶部和底部 for(i=0;i<=n+1;i++) grid[i][0]=grid[i][m+1]=1;//左翼

4、和右翼 intj7/72012级网络工程严坤222012321210160; //初始化相对位移 Positionoffset[4]; offset[0].row=0;offset[0].col=1;//右 offset[1].row=1;offset[1].col=0;//下 offset[2].row=0;offset[2].col=-1;//左 offset[3].row=-1;offset[3].col=0;//上 intNumOfNbrs=4;//相邻方格数 Positionhere,nbr; here.row=st

5、art.row; here.col=start.col; grid[start.row][start.col]=2; //标记可达方格位置 //LinkedQueueQ; QueueQ; Q.end=0; Q.begin=0; do{//标记相邻可达方格 for(i=0;i

6、nbr.row][nbr.col]==0) { //该方格未被标记 grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成布线 Q.col[Q.end]=nbr.col; Q.row[Q.end]=nbr.row; Q.end++; } } //是否到达目标位置finish？ if((nbr.row==finish.row)&&(nbr.col==finish.c

7、ol))break;//完成布线 //活结点队列是否非空？ if(Q.begin==Q.end)returnfalse;//无解 else{ here.row=Q.row[Q.begin]; here.col=Q.col[Q.begin]; Q.begin++;//取下一个扩展结点7/72012级网络工程严坤222012321210160 } }while(true); //构造最短布线路径 PathLen=grid[finish.row][finish.col]-2; path=newPosition[PathLen]; /

8、/从目标位置finish开始向起始位置回溯 here=finish; for(j=PathLen-1;j>=0;j--){ path[j]=here; //找前驱位置 for(i=0;i