第九章 分支限界：介绍队列式(FIFO)分支限界法和优先队列式分支限界的基本思想与算法框架，回溯和分支限界的联系和区别，限界函数的改进，运用分支限界法解决实际问题。9.10/1背包问题:引入0-1背包问题，介绍队列式分支限界。[判断题]分支限界法在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点。
9.2旅行商问题:引入旅行商问题，介绍优先队列式分支限界。
9.3基本思想:分支限界的基本思想、基本步骤，回溯和分支限界的联系和区别，限界函数的改进。
错
对
答案：错
[判断题]分支限界法找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
对
错[判断题]队列式分支限界法以最小耗费优先的方式搜索解空间树。
对
错[判断题]优先队列式分支限界法按照队列先进先出的原则，选取下一个节点为扩展结点。
对
错[单选题]分支限界法解旅行商问题时的解空间树是
子集树
深度优先生成树
排列树
广度优先生成树[单选题]优先队列式分支限界法选取扩展结点的原则是
后进先出
先进先出
结点的优先级
随机[多选题]用分支限界法设计算法的步骤是：
确定易于搜索的解空间结构（按树或图组织解）
针对所给问题，定义问题的解空间（对解进行编码）
定义最优子结构
以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索[多选题]分支限界法与回溯法的不同点是什么？
求解目标不同
搜索方式不同
对扩展结点的扩展方式不同
存储空间的要求不同[单选题]FIFO是（ ）的搜索方式。
贪心算法
回溯算法
动态规划
分支限界
[单选题]下面说法不正确的是（）
用约束函数在扩展结点处剪去不满足约束的子树
用限界函数剪去得不到最优解的子树
回溯和分支限界都是动态生成解空间树
使用限界函数作优先级, 第一个加入队列的叶子就是最优解 [单选题]在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。
分支限界
回溯求解子集树问题
回溯
回溯和分支限界
[判断题]使用限界函数作优先级, 第一个扩展的叶子就是最优解
错
对[判断题]分支限界法不能解决0/1背包问题
错
对
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
