计算机算法设计与分析 第6章 分支限界法[借鉴].ppt

6.4 布线问题 1. 算法思想 解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中并且将这些方格标记为1即从起始方格a到这些方格的距离为1 接着算法从活结点队列中取出队首结点作为下一个扩展结点并将与当前扩展结点相邻且未标记过的方格标记为2并存入活结点队列这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止即加入剪