分支限界上机题目，是用分支限界法解决0/1背包问题

第1题：

第2题：

第3题：

从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（）之外都是最常见的方式。

• A、队列式分支限界法
• B、优先队列式分支限界法
• C、栈式分支限界法
• D、FIFO分支限界法

正确答案:C

第4题：

简述分支限界法与回溯法的异同。

正确答案: 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：
（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同；
（4）存储空间的要求不同。

第5题：

在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）

• A、回溯法
• B、分支限界法
• C、回溯法和分支限界法
• D、动态规划

正确答案:A

第6题：

简述分支限界法及其算法思想。

正确答案: 这是一种用于求解组合优化问题的排除非解的搜索算法。类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。因此，可以很容易比较回溯法与分枝定界法的异同。相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：分枝限界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：
1）先进先出（FIFO）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
2）（优先队列）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。

第7题：

在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）

• A、回溯法
• B、分支限界法
• C、回溯法和分支限界法
• D、回溯法求解子集树问题

正确答案:B

第8题：

常见的两种分支限界法为（）

• A、广度优先分支限界法与深度优先分支限界法
• B、队列式（FIFO）分支限界法与堆栈式分支限界法
• C、排列树法与子集树法
• D、队列式（FIFO）分支限界法与优先队列式分支限界法

正确答案:D

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

用分支限界法设计算法的步骤是什么？

正确答案: （1）针对所给问题，定义问题的解空间（对解进行编码）；
（2）确定易于搜索的解空间结构（按树或图组织解）；
（3）以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

第16题：

在分支限界算法中，根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下（）描述最为准确。

• A、采用FIFO队列的队列式分支限界法
• B、采用最小值堆的优先队列式分支限界法
• C、采用最大值堆的优先队列式分支限界法
• D、以上都常用，针对具体问题可以选择采用其中某种更为合适的方式

正确答案:D

第17题：

解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是（），需要排序的是（），（）。

正确答案:动态规划；回溯法；分支限界法

第18题：

下列算法中不能解决0/1背包问题的是（）

• A、贪心法
• B、动态规划
• C、回溯法
• D、分支限界法

正确答案:A

第19题：

分支限界法主要有（）分支限界法和（）分支限界法。

正确答案:队列式（FIFO）；优先队列式

第20题：

第21题：

第22题：

第23题：

第24题：