算法设计及分析 电路板布线

《算法设计及分析 电路板布线》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析电路板布线本文由尘一平生贡献doc文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。电路板布线问题印刷电路板将布线区域分成n×m个方格阵列，如下图(a).精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如下图(b)所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允许穿过被封锁的方格。aabb采用队列式(FIFO)分枝限界法解此问题，它的解空间树是一个无向图。首先结点a作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被图（a）图（b）加入

2、到活结点队列，这些结点被加入队列的顺序是：右、下、左、上。将这些方格标记为1，它表示从起始方格a到这些方格的距离为1。接着从活结点队列中取出队首结点作为下一个扩展结点，并将与扩展结点相邻且未标记过的方格标记为2，并以右、下、左、上的顺序将这些结点存放到活结点队列中。这个过程一直持续到算法搜索到目标方格b或者活结点队列为空时停止。注意到，搜索过程在遇到标记封锁的方格时，自动放弃此方格。下图是在7×7方格阵列中布线的例子。其中，起始点的位置是a=(3,2)，目标是位置b=(4，6).有！！号的方格表示被封锁。搜索过程如下图(c)所示。3212!!!!!!2!！1!！!

3、！a12!!12!!!!b234!!!!!!5678图(c)!!!!678!！!！!！a!!!!!!b!!!!!!!!!!图(d)!!!!!!本例中，a到b的最短距离是9。要构造出与最短距离相应的最短路径，须从目标方格开始向起始方格回溯，逐步构造出最优解。每次向比当前方格标号小1的相邻方格移动，直至到达起始方格为止。图(d)给出了该例子的最短路径，它是从目标方格b移动到(5,6)，然后移至(6,6)，…,最终移至起始方格a。在算法实现时，首先定义一个表示电路板上方格位置的类Position，它有两个私有成员row和col，分别表示方格所在的行和列。在电路板的任一方

4、格处，布线可沿右、左、下、上四个方向进行，分别记为移动0，2，offset[i].col=11，3。表示向右前进一步；offset[i].col=-1表示向左前进一步。在这两种情况下，都有，offset[i].row=0。类似地讨论向下和向上前进的情况。一般用一个二维数组grid表示所给的方格阵列。初始时，grid[i][j]=0,表示该方格允许布线，而grid[i][j]=1表示该方格不允许布线（有封锁标记）。为了便于处理边界方格的情况，算法对所给的方格阵列的四周设置一道“围墙”，即增设标记为1的附加方格。算法开始时测试初始方格与目标方格是否相同。若相同，则不必

5、计算，直接返回最短距离0。否则，算法设置方格阵列的围墙，初始化位移矩阵offset。算法将起始位置的距离记为2。因为数字0和1用于表示方格的开放或封闭状态，所以，表示距离不用这两个数字，因而将所有的距离值都加2。实际距离应为标记距离减2。算法从起始位置start开始，首先标记所有标记距离为3的方格，并存入活结点队列，然后依次标记所有标记距离为4，5，…的方格，直至到达目标方格finish或活结点队列为空时为止。程序8-3-1布线问题的队列式分枝限界算法boolFindPath(Positionstart,Positionfinish,int&PathLen,Pos

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

7、初始化相对位移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=start.row;Here.col=start.col;Grid[start.row][start.col]=2;//标记可达方格位置Li

8、nkedQ