算法设计与分析 电路板布线.doc

电路板布线问题
印刷电路板将布线区域分成n×m个方格阵列,如下图(a).精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线,如下图(b)所示。为了避免线路相交,已布了线的方格做了封锁标记,其它线路不允许穿过被封锁的方格。

a
b
a
b
图(a)
图(b)



采用队列式(FIFO)分枝限界法解此问题,它的解空间树是一个无向图。首先结点a作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列,这些结点被加入队列的顺序是:右、下、左、上。将这些方格标记为1,它表示从起始方格a到这些方格的距离为1。接着从活结点队列中取出队首结点作为下一个扩展结点,并将与扩展结点相邻且未标记过的方格标记为2,并以右、下、左、上的顺序将这些结点存放到活结点队列中。这个过程一直持续到算法搜索到目标方格b或者活结点队列为空时停止。注意到,搜索过程在遇到标记封锁的方格时,自动放弃此方格。下图是在7×7方格阵列中布线的例子。其中,起始点的位置是a=(3,2),目标是位置b=(4,6).有!!号的方格表示被封锁。搜索过程如下图(c)所示。
!!
!! !!
a !!
!! !! b
!! !!
!! !! !!
!! !! !!
1!
3 2 !!
2 1 !!!!
1 a 1 2 !!
2 1 2 !! !! b
!! 2 3 4 !!
!! !! !! 5 6 7 8
!! !! !! 6 7 8




图(c) 图(d)
本例中,a到b的最短距离是9。要构造出与最短距离相应的最短路径,须从目标方格开始向起始方格回溯,逐步构造出最优解。每次向比当前方格标号小1的相邻方格移动,直至到达起始方格为止。图(d)给出了该例子的最短路径,它是从目标方格b移动到(5,6),然后移至(6,6),…,最终移至起始方格a。
在算法实现时,首先定义一个表示电路板上方格位置的类Position,它有两个私有成员row和col,分别表示方格所在的行和列。在电路板的任一方格处,布线可沿右、下、左、上四个方向进行,分别记为移动0,1,2,3。offset[
i].col=1表示向右前进一步; offset[i].col=-1表示向左前进一步。在这两种情况下,都有,offset[i].row=0。类似地讨论向下和向上前进的情况。
一般用一个二维数组grid表示所给的方格阵列。初始时,grid[i][j]=0,表示该方格允许布线,而grid[i][j]=1表示该方格不允许布线(有封锁标记)。为了便于处理边界方格的情况,算法对所给的方格阵列的四周设置一道“围墙”,即增设标记为1的附加方格。算法开始时测试初始方格与目标方格是否相同。若相同,则不必计算,直接返回最短距离0。否则,算法设置方格阵列的围墙,初始化位移矩阵offset。算法将起始位置的距离记为2。因为数字0和1用于表示方格的开放或封闭状态,所以,表示距离不用这两个数字,因而将所有的距离值都加2。实际距离应为标记距离减2。算法从起始位置start开始,首先标记所有标记距离为3的方格,并存入活结点队列,然后依次标记所有标记距离为4,5,…的方格,直至到达目标方