[其它]算法设计与分析-分支限界法.ppt
《[其它]算法设计与分析-分支限界法.ppt》由会员分享,可在线阅读,更多相关《[其它]算法设计与分析-分支限界法.ppt(79页珍藏版)》请在三一文库上搜索。
1、第6章 分支限界法 计算机算法设计与分析 内容提要 每一步都非常关键,走好每一步! 1 理解理解 算法策略算法策略 2 掌握掌握 算法框架算法框架 3 学习学习 应用范例应用范例 归纳总结归纳总结 理解 分支限界法的算法策略 与回溯法的区别? 1 分支限界法 基本思想 算法思想 解此问题的队列式分支限界法从起始位置a开始将它作 为第一个扩展结点。与该扩展结点相邻并且可达的方格成为 可行结点被加入到活结点队列中,并且将这些方格标记为1 ,即从起始方格a到这些方格的距离为1。 接着,算法从活结点队列中取出队首结点作为下一个扩 展结点,并将与当前扩展结点相邻且未标记过的方格标记为 2,并存入活结点队
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+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其它 算法 设计 分析 分支 限界
链接地址:https://www.31doc.com/p-2001942.html