用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

题目

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

相似考题

1.分支限界法与回溯法的相同点是()A.求解目标相同B.搜索方式相同C.对扩展结点的扩展方式相同D.都是一种在问题的解空间树T中搜索问题解的算法

2.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。()此题为判断题(对，错)。

3.算法是根据一定经验，在问题空间内部分搜索，以图迅速找到解题方法。()

4.回溯法在问题的解空间树中,按扩展结点优先策略,从根结点出发搜索解空间树。()此题为判断题(对，错)。

参考答案和解析
正确答案:O(h(n))
更多“用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在”相关问题

  • 第1题：

    启发法是根据一定经验，在问题空间内部搜索，以图找到解题方法的过程。()


    参考答案：正确

  • 第2题：

    （接上一题）若定义问题的解空间，以深度优先的方式搜索解空间，则采用（65）算法设计策略。

    A.动态规划

    B.贪心

    C.回溯

    D.分支限界


    正确答案：C
    同上一题解析

  • 第3题：

    回溯法在解空间树T上的搜索方式是（）

    • A、深度优先
    • B、广度优先
    • C、最小耗费优先
    • D、活结点优先

    正确答案:A

  • 第4题：

    比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？


    正确答案: 1）回溯法是在约束下带跳跃的深度优先搜索。
    2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。
    3）分枝限界法更适合找最优解。

  • 第5题：

    关于回溯搜索法的介绍，下面（）是不正确描述。

    • A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
    • B、回溯法是一种既带系统性又带有跳跃性的搜索算法
    • C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
    • D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

    正确答案:D

  • 第6题：

    用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。


    正确答案:排列树

  • 第7题：

    用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。


    正确答案:一个（最优）解

  • 第8题：

    单选题
    关于回溯搜索法的介绍，下面（）是不正确描述。
    A

    回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解

    B

    回溯法是一种既带系统性又带有跳跃性的搜索算法

    C

    回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯

    D

    回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径


    正确答案： D
    解析： 暂无解析

  • 第9题：

    填空题
    用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含（）。

    正确答案： 一个（最优）解
    解析： 暂无解析

  • 第10题：

    填空题
    用回溯法解批处理作业调度问题时，该问题的解空间结构为（）结构。

    正确答案： 排列树
    解析： 暂无解析

  • 第11题：

    填空题
    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。

    正确答案： 子集树
    解析： 暂无解析

  • 第12题：

    单选题
    回溯法在解空间树T上的搜索方式是（）
    A

    深度优先

    B

    广度优先

    C

    最小耗费优先

    D

    活结点优先


    正确答案： A
    解析： 暂无解析

  • 第13题：

    回溯法也称为试探法。以下关于回溯法的结论中正确的是(50)。

    A．即使问题的解存在，回溯法不一定能找到问题的解

    B．回溯法找到的问题的解不一定是最优解

    C．回溯法不能找到问题的全部解

    D．回溯法无法避免求出的问题解的重复


    正确答案：B
    解析：回溯法又称为试探法，是找到问题解的一种搜索策略，就是在用某种方法找出的解的过程中，若中间项结果满足所解问题的条件，则一直沿这个方向搜索下去，直到无路可走或无结果，则开始回溯，改变其前一项的方向(或值)继续搜索。若其上一项的方向(或值)都已经测试过，还无路可走或无结果，则再继续回溯到更前一项，改变其方向(或值)继续搜索。若找到了一个符合条件的解，则停止或输出这个结果继续搜索，这个解不一定是最优解；否则继续回溯下去，直到回溯到问题的开始处(不能再回溯)，仍没有找到符合条件的解，则表示此问题无解或已经找到了全部的解。

  • 第14题：

    在求解某问题时，经过分析发现该问题具有最优子结构性质，若定义问题的解空间，以深度优先的方式搜索解空间，则采用（ ）算法设计策略。

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

    答案：C
    解析：
    分治法的设计思想是将一个难以直接解决的大问题分解成一些规模较少的相同问题以便各个击破，分而治之。
    动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。
    贪心法经常用于解决最优化问题，但他的最优往往是从局部最优来考虑的，每一步都选最优的方案，但这种方案不一定能得到整体上的最优解。
    回溯法是一种既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。
    题目描述中提到，需要解决的问题具有最优子结构性质，且求解过程中子问题被重复求解，这种情况下如果采用分治法，效率会很低，所以应采用动态规划法。而“以深度优先的方式搜索解空间”则明显是在采用回溯法。

  • 第15题：

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

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

    正确答案:A

  • 第16题：

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

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

    正确答案:B

  • 第17题：

    用回溯法解0/1背包问题时，该问题的解空间结构为（）结构。


    正确答案:子集树

  • 第18题：

    回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

    • A、广度优先
    • B、活结点优先
    • C、扩展结点优先
    • D、深度优先

    正确答案:D

  • 第19题：

    单选题
    回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。
    A

    广度优先

    B

    活结点优先

    C

    扩展结点优先

    D

    深度优先


    正确答案： D
    解析： 暂无解析

  • 第20题：

    问答题
    比较回溯法和分支限界法的搜索方式，哪种方法更适合找最优解问题？

    正确答案： 1）回溯法是在约束下带跳跃的深度优先搜索。
    2）分枝限界是广度优先方式的按最小代价选择扩展节点，以上界函数对活节点进行限界的搜索。
    3）分枝限界法更适合找最优解。
    解析： 暂无解析

  • 第21题：

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

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    动态规划


    正确答案： B
    解析： 暂无解析

  • 第22题：

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

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    回溯法求解子集树问题


    正确答案： D
    解析： 暂无解析

  • 第23题：

    填空题
    用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

    正确答案： O(h(n))
    解析： 暂无解析

相关内容