一 问题描述： 布线问题：印刷电路板将布线区域划分成 n×m 个方格阵列，要求确定连接方格阵列中的方 格 a 的中点到方格 b 的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，为了 避免线路相交，已布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方格。 二 算法应用： 用分支限界法解此布线问题。分支限界法类似回溯法，也是一种在问题的解空间树 T 上搜 索问题解的算法。但分支限界法只找出满足约束条件的一个最优解，并且以广度优先或最小 耗费优先的方式搜索解空间树 T。树 T 是一棵子集树或排列树。在搜索时，每个结点只有一 次机会成为扩展结点，并且一次性产生其所有儿子结点。从活结点表中选择下一扩展结点有 两种方式：（1）队列式（FIFO） （2）优先队列式。分支限界法广泛应用于单源最短路径 问题，最大团问题，布线问题，电路板排列问题等。 三 求解思路： 用队列式分支限界法来考虑布线问题。布线问题的解空间是一个图，则从起始位置 a 开始将 它作为第一个扩展结点。与该扩展结点相邻并可达的方格成为可行结点被加入到活结点队列 中，并且将这些方格标记为 1，即从起始方格 a 到这些方格的距离为 1。接着，从活结点队 列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为 2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格 b 或活结点队列为空时为 止。 四 算法思路： 在实现上述算法时， （1） 定义一个表示电路板上方格位置的类 Position。 它的 2 个成员 row 和 col 分别表示方格所在的行和列。在方格处，布线可沿右、下、左、上 4 个方向进行。沿这 4 个方向的移动分别记为 0，1，2，3。下表中，offset[i].row 和 offset[i].col(i= 0,1,2,3)分别给出沿这 4 个方向前进 1 步相对于当前方格的相对位移。 移动 i 0 1 2 3 方向 右 下 左 上 offset[i].row offset[i].col 0 1 0 -1 1 0 -1 0 （2） 用二维数组 grid 表示所给的方格阵列。 初始时，grid[i][j] = 0, 表示该方格允许布线，而 grid[i][j] = 1 表示该方格被封锁，不允许布 线。 五 举例说明： 一个 7×7 方格阵列布线如下： 起始位置是 a = (3,2),目标位置是 b = (4,6),阴影方格表示被封锁的方格。当算法搜索到目标方 格 b 时，将目标方格 b 标记为从起始位置 a 到 b 的最短距离。此例中， a 到 b 的最短距离 是 9。 

3 2 1 2 2 1 a 1 2 1 2 3 b 8 7 8 9 8 9 4 5 6 6 7 a b (a) 标记距离 (b) 最短布线路径 六 程序实现： #include typedef struct { int row; int col; }Position; int FindPath (Position start, Position finish, int &PathLen, Position *&path) { //计算从起始位置 start 到目标位置 finish 的最短布线路径，找到返回 1，否则，返回 0 i; int if ((start.row = = finish.row) && (start.col = = finish.col)) { PathLen = 0; return 0; } //start = finish //设置方格阵列”围墙” 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; //左翼和右翼 //初始化相对位移 int NumOfNbrs = 4; //相邻方格数 Position offset[4], here, nbr; offset[0].row = 0; offset[0].row = 1; offset[0].row = 0; offset[0].row = -1; here.row = start.row; here.col = start.col; LinkedQueue Q; //标记可达方格位置 do { offset[0].col = 1; offset[0].col = 0; offset[0].col = -1; offset[0].row = 0; //右 //下 //左 //上 for (i = 0; i< NumOfNbrs; 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)) break;//完成布线 

Q.Add(nbr); } } if ((nbr.row = = finishi.row) && (nbr.col = = finish.col)) if (Q.IsEmpty()) //活队列是否为空 break;//完成布线 return 0; //无解 Q.delete(here); //取下一个扩展结点 }while (1); //构造最短布线路径 PathLen = grid[finish.row][finish.col] － 2; path = new Position[PathLen]; here = finish; for (int j = PathLen – 1; j >= 0; j--) { //找前驱位置 path[j] = here; for (i = 0; i< NumOfNbrs; i++) { nbr.row = here.row + offset[i].row ; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] = = j+2) break; } here = nbr; //向前移动 } return 1; } void main () { int grid[8][8]; int PathLen, *path; Position start, finish; start.row = 3; start.col = 2; finish.row = 4; finish.col = 6; FindPath (start, finish, PathLen, path); } 七 程序分析： 程序中函数 FindPath 的功能是找到最短布线路径。首先给原方格阵列加一道“围墙”，即加 封锁标记，然后初始化相对位移，即下一个结点相对于当前活结点的方向。运用 do-while 循环来分别从不同的方向找当前结点的相邻结点，并将其与目标结点 finish 作比较，若为目 标结点，则跳出循环，完成布线；否则将其加入活结点队列。再从活结点队列中取出结点作 为新的活结点，并又重复上述步骤，直到找到 finish 结点为止。最后利用 for 循环构造最短 布线路径。