违法和不良信息举报 联系客服
免费注册 登录

关于回溯算法和分支限界法，以下（）是不正确描述。

题目
单选题
关于回溯算法和分支限界法，以下（）是不正确描述。
A

回溯法中，每个活结点只有一次机会成为扩展结点

B

分支限界法中，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子加入活结点表中

C

回溯法采用深度优先的结点生成策略

D

分支限界法采用广度优先或最小耗费优先（最大效益优先）的结点生成策略

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

不能保证求得0-1背包问题的最优解。

A．分支限界法

B．贪心算法

C．回溯法

D．动态规划策略


正确答案：B
解析：题中的分支界限法、回溯法和动态规划策略等实质都需要遍历所有可能的情况(分支界限法会避免没必要的计算分支，在一定程度上优化了算法)。而贪心算法只能保证在当前这一步计算是最优的选择，而不能保证全局的最优解。

第2题：

试比较回溯法与分支限界算法，分别谈谈这两个算法比较适合的问题？


正确答案: 不同点：求解目标，搜索方式，空间消耗。
回溯法的求解目标是找出解空间中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
搜索方式：回溯法以深度优先的方式搜索解空间，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间。
回溯法：以深度优先方式系统搜索问题解的算法为回溯法，适合解组合数较大的问题。
分支限界法适合解决大量离散最优化的问题。

第3题：

分支限界法与回溯法完全不同。()

此题为判断题(对，错)。


正确答案:×

第4题：

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


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

第5题：

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

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

正确答案:D

第6题：

● （65） 不能保证求得0-1 背包问题的最优解。

（65）

A. 分支限界法

B. 贪心算法

C. 回溯法

D. 动态规划策略


正确答案：B

第7题：

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


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

第8题：

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

此题为判断题(对，错)。


正确答案:√

第9题：

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

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

正确答案:A

第10题：

回溯算法和分支限界法的问题的解空间树不会是（）

  • A、有序树
  • B、子集树
  • C、排列树
  • D、无序树

正确答案:D

更多相关问题
相关内容