《布线问题》PPT课件.ppt

布线问题,1.算法思想,布线问题：印刷电路板将布线区域划分成nm个方格如图a所示。精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，如图b所示。为了避免线路相交，已布了线的方格做了封锁标记，其它线路不允穿过被封锁的方格。,布线问题,1.算法思想,一个布线的例子：图中包含障碍。起始点为a，目标点为b。,布线问题,1.算法思想,解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。,接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。,布线问题,Position offset4;offset0.row=0;offset0.col=1;/右 offset1.row=1;offset1.col=0;/下 offset2.row=0;offset2.col=-1;/左 offset3.row=-1;offset3.col=0;/上,定义移动方向的相对位移,for(int i=0;i=m+1;i+)grid0i=gridn+1i=1;/顶部和底部 for(int i=0;i=n+1;i+)gridi0=gridim+1=1;/左翼和右翼,设置边界的围墙,布线问题,for(int i=0;i NumOfNbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=0)/该方格未标记 gridnbr.rownbr.col=gridhere.rowhere.col+1;if(nbr.row=finish.row),找到目标位置后，可以通过回溯方法找到这条最短路径。,