分支限界法第6章分支限界法.ppt

第6章 ×n的方格阵列,如下图所示。精确的布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线,为了避免线路相交,已经布线了的方格要做封锁标记,其它线路不允许穿过被封锁了的方格。解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中,并且将这些方格标记为1,即从起始方格a到这些方格的距离为1。,算法从活结点队列中取出队首结点作为下一个扩展结点,并将与当前扩展结点相邻且未标记过的方格标记为2,并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空(表示没有通路)时为止。[4];offset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上定义移动方向的相对位移for(inti=0;i<=m+1;i++)grid[0][i]=grid[n+1][i]=1;//顶部和底部for(inti=0;i<=n+1;i++)grid[i][0]=grid[i][m+1]=1;//(inti=0;i<NumOfNbrs;i++){=+offset[i].row;=+offset[i].col;if(grid[][]==0){//该方格未标记grid[][]=grid[][]+1;if((==)&&(==))break;//(nbr);}}找到目标位置后,可以通过回溯方法找到这条最短路径。分支限界法与回溯法的不同求解目标可能不同搜索方式的不同空间消耗不同分支限界法的搜索策略在扩展结点处,先生成其所有子结点(分支),然后从当前的活结点表中选下一个扩展结点为了有效地选择下一扩展结点,以加速搜索的进程,在每一结点处,计算一个函数值(限界),并根据这些已计算的函数值,从当前活结点表中选择一个最有利的结点作为扩展结点分支限界法基本思想以广度优先或以最小耗费(最大效益)优先的方式搜索;每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。