[其它]算法设计与分析-分支限界法.ppt

第6章 分支限界法 计算机算法设计与分析 内容提要 每一步都非常关键，走好每一步！ 1 理解理解 算法策略算法策略 2 掌握掌握 算法框架算法框架 3 学习学习 应用范例应用范例 归纳总结归纳总结 理解 分支限界法的算法策略 与回溯法的区别？ 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 bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1); / 检查当前扩展结点的右儿子结点 if (up = bestp) / 右子树可能含最优解 AddLiveNode(up, cp, cw, false, i+1); / 取下一个扩展节点（略） 分支限界搜索过 程 批处理作业调度问题 算法描述 算法的while循环完成对排列树内部结点的有序扩展。在while 循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时 间和下界）的结点作为当前扩展结点，并加以扩展。 首先考虑E.s=n的情形，当前扩展结点E是排列树中的叶结点。 E.sf2是相应于该叶结点的完成时间和。当E.sf2 bestc时更新当 前最优值bestc和相应的当前最优解bestx。 当E.sn时，算法依次产生当前扩展结点E的所有儿子结点。对 于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间 和的下界bb。当bb bestc时，将该儿子结点插入到活结点优先队 列中。而当bb bestc时，可将结点node舍去。 76 while (E.s = n ) if (E.s = n ) / 叶结点 if (E.sf2 bestc) bestc = E.sf2; for (int i = 0; i n; i+) bestxi = E.xi; delete E.x; 3. 算法描述 当E.sf2bestc时，更 新当前最优值bestc和相 应的最优解bestx 77 3. 算法描述 else / 产生当前扩展结点的儿子结点 for (int i = E.s; i n; i+) Swap(E.xE.s,E.xi); int f1,f2; int bb=Bound(E,f1,f2,y); if (bb bestc ) MinHeapNode N; N.NewNode(E,f1,f2,bb,n); H.Insert(N); Swap(E.xE.s,E.xi); delete E.x; / 完成结点扩展 当bbbestc时，将 儿子结点插入到活 结点优先队列中