6.3 电路布线问题.ppt

6.3 电路布线问题 问题描述： 印刷电路板将布线区域划分成n×n个方格阵列，要求确定连接方格a到方格b的最短布线方案。 在布线时，电路只能沿直线或直角布线，为了避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。 实例： 用队列式分支限界法来考虑布线问题。 从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。 接着，从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法有哪些信誉好的足球投注网站到目标方格b或活结点队列为空时为止。 算法思路： 在实现上述算法时，定义一个表示电路板上方格位置的类型Position。它的2个成员row和col分别表示方格所在的行和列。 在方格处，布线可沿右、下、左、上4个方向进行。沿这4个方向的移动分别记为0，1，2，3。下表中，offset[i].row和offset[i].col(i=0，1，2，3)分别给出沿这4个方向前进1步相对于当前方格的相对位移。 数据结构： 用二维数组grid表示所给的方格阵列。初始时，grid[i][j]=0，表示该方格允许布线，而grid[i][j]=1表示该方格被封锁，不允许布线。起始位置是a=(3，2)，目标位置是b=(4，6)，阴影方格表示被封锁的方格。当算法有哪些信誉好的足球投注网站到目标方格b时，将目标方格b标记为从起始位置a到b的最短距离。 程序说明： 首先给原方格阵列加一道“围墙”，即加封锁标记， 然后初始化相对位移，即下一个结点相对于当前活结点的方向。 运用do-while循环来分别从不同的方向找当前结点的相邻结点，并将其与目标结点finish作比较， 若为目标结点，则跳出循环，完成布线； 否则将其加入活结点队列。 再从活结点队列中取出结点作为新的活结点，并又重复上述步骤，直到找到finish结点为止。 最后利用for循环构造最短布线路径。 主要代码： int grid[9][9]= { // V // 0，1，2，3，4，5，6，7，8 /*0*/ {1，1，1，1，1，1，1，1，1}，//0 /*1*/ {1，0，0，1，0，0，0，0，1}，//1 /*2*/ {1，0，0，1，1，0，0，0，1}，//2 /*3-*/ {1，0，1，0，0，1，0，0，1}，//3 /*4*/ {1，0，0，0，1，1，0，0，1}，//4 /*5*/ {1，1，0，0，0，1，0，0，1}，//5 /*6*/ {1，1，1，1，0，0，0，0，1}，//6 /*7*/ {1，1，1，1，0，0，0，0，1}，//7 /*8*/ {1，1，1，1，1，1，1，1，1} //8 }; typedef struct { int row; int col; }Position; Position offset[4]= { {0，1}，//右 {1，0}，//下 {0，-1}，//左 {-1，0}//上 }; //计算从起始位置start到目标位置finish的最短布线路径 int i; if((start.row==finish.row) (start.col==finish.col)) { PathLen=0; return 0; } here.row=start.row; here.col=start.col; for(i=0;i4;i++) { nbr.row=here.row+offset[i].row; nbr.col=here.col+offset[i].col; if(grid[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)) goto label;//完成布线 Q[r]=nbr; r++; }//if }//for PathLen=grid[finish.row][finish.col]-1; here=finish; for(int j