利用分支限界法寻求问题的最优解时,与回溯法类似,可以用加速搜索()
A: 代价函数
B: 剪枝函数
C: 活结点表
D: 扩展节点
A: 代价函数
B: 剪枝函数
C: 活结点表
D: 扩展节点
举一反三
- 比较分支限界法和回溯法,两者的不同是() A: 在一般情况下,分支限界法与回溯法的求解目标不同 B: 分支限界法与回溯法的搜索方式不同 C: 分支限界法需要借助活结点表数据结构,而回溯法则不需要。 D: 扩展节点的扩展方式不同。 E: 回溯法需要确定搜索范围,分支限界法则不需要。 F: 分支限界法保留下来的活结点是有可能导致可行解或最优解的节点,回溯法则不是。
- 回溯法常用剪枝函数来减少对解空间树的搜索,剪枝函数包括()。 A: 约束函数 B: 最优函数 C: 限界函数 D: 最小函数
- 比较分支限界法和回溯法,说法错误的是() A: 分支限界法保留下来的活结点是有可能导最优解的结点,回溯法则不是。 B: 分支限界法与回溯法的搜索方式不同 C: 分支限界法需要借助活结点表数据结构,而回溯法则不需要。 D: 回溯法和分支限界法搜索之前都需要先确定搜索范围。
- 在回溯法中,可以用限界函数在扩展结点处剪去不满足约束的子树,用约束函数剪去得不到最优解的子树。
- 回溯法中,下面关于显约束、隐约束及剪枝条件等的解释不正确的是? A: 显约束决定了一个扩展结点可展开的分支个数及每个分支的取值 B: 隐约束是解空间树的剪枝条件,是在搜索时剪掉不满足隐约束的分支,避免无效搜索 C: 隐约束包含约束函数和限界函数。对于子集树,约束函数对0分支剪枝,限界函数对1分支剪枝。 D: 对解空间树是n叉树或者排列树来说,回溯法搜索时对每个分支的剪枝条件(函数)是完全相同的。