使用队列求电路图的最短布线

 

在最短路径的回溯中,从尾到头进行浏览,如果不是相邻点就舍弃,得到的就将是所求的路径。

 

分支限界法

电路布线中的一个基本问题的背景

在印刷电路板上的某一个矩形区域布线,通常是将矩形区域划分成n×m个方格阵列如下图所示。

精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。对每段布线,要求与矩形的边平行,如下图所示。为了避免线路相交,对已布了线的方格做了封锁标记,要求要布的线路不穿过被封锁的方格。

问题的叙述

已知一个带有封锁标记的 n×m个方格阵列。今给定阵列中没被封锁的任意两个方格a和b,要求找出从a到b的最短布线的路径和路长。如左图。黑格表示被封锁。

问题求解的基本思想

在可布线的方格区域内,依次找出从a出发1步、2步、3步、…能到达的方格,直到所找到的方格是b为止。这时,所经历的步数就是a到b的最短路长。然后,沿着到达b的‘足迹’,按照路长逐步减1回溯到a,所经过的方格序列便是从b到a的最短路径,其逆便是所要求的从a到b的最短路径。这里,用的方法是从a出发广度优先搜索b。

需要注意的是:按布线的规则,当前方格走1步只能到达它的上 、下、左、或右方格。

问题所涉及的对象的数学化

电路板方格阵列中的一个方格用它所在的行row和列col表示.这些行列对构成的方格类用Position表示。

电路板方格阵列用一个n×m的矩阵grid表示。而且 当grid[i][j]=0时表示方格(i,j)允许布线,当grid[i][j]=1时表示方格(i,j)不允许再布线。为了便于处理方格边界的情况,引入技巧:在所给方格阵列四周设置一道“围墙”,即增设标记为“1”的附加方格。

电路板方格阵列中一个方格移动1步的状态变化用一个记录数组offset[4]表示。

问题的数学化

已知NumOfNbrs = 4、记录数组offset[4]、和初始化为0/1的二维整数组grid[n+2][m+2] 。其中约定
grid[0][j]=grid [n+1][j]=1,j=0,1,2,…,m+1; grid [i][0]=grid[i][m+1]=1,i= 1,2,…,n。

今给定起始位置start和目的位置finish,要求找出从start到finish的一条最短的布线路长和相应的最短路径。

解上述基本问题的算法作为一个函数来实现

 

解上述基本问题的算法的复杂度

我们看到上述的算法明显地分成4大步:

(1)处理start=finish的情形。需要O(1)的时间。
(2)从start出发的广度优先搜索准备工作。需要O(1)的时间。
(3)开始搜索,直到找到finish,然后转入(4);否则反馈‘不可能找到finish’。由于每个方格成为队列Q的成员最多1次,因此队列中的成员最多n×m个。而考察每个方格只需时间O(1),因此,这一步共耗时O(n×m)。
(4)计算实际最短路长,然后回溯找最短路径。这一步只需要O(l)时间(l是最短布线路径的长度)。而l=O(n+m)。

因此,解上述基本问题的算法的复杂度为O(n×m)。

 

未经允许不得转载:TacuLee » 使用队列求电路图的最短布线

赞 (0)

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址