回溯法搜索解空间树时，常用的两种剪枝函数为（）和（）。

题目

回溯法搜索解空间树时，常用的两种剪枝函数为（）和（）。

相似考题

1.分支限界法在问题的解空间树中,按广度优先策略,从根结点出发搜索解空间树。()此题为判断题(对，错)。

2.以广度优先或以最小耗费(最大收益)优先的方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索,这是分支限界法的第二步。()此题为判断题(对，错)。

3.回溯法中常见的两类典型的解空间树是子集树和排列树。()此题为判断题(对，错)。

4.回溯法解旅行售货员问题时的解空间树是子集树。()此题为判断题(对，错)。

参考答案和解析
正确答案:约束函数；限界函数
更多“回溯法搜索解空间树时，常用的两种剪枝函数为（）和（）。”相关问题

  • 第1题：

    回溯法在问题的解空间树中,按扩展结点优先策略,从根结点出发搜索解空间树。()

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


    正确答案:×

  • 第2题：

    下面哪种函数是回溯法中为避免无效搜索采取的策略（）

    • A、递归函数
    • B、剪枝函数
    • C、随机数函数
    • D、搜索函数

    正确答案:B

  • 第3题：

    回溯法中常见的两类典型的解空间树是什么？并简述其定义。


    正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
    当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
    当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。

  • 第4题：

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


    正确答案:O(h(n))

  • 第5题：

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

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

    正确答案:B

  • 第6题：

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

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

    正确答案:D

  • 第7题：

    填空题
    使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（），只使用约束条件进行裁剪的是（）。

    正确答案： 0/1背包问题,N皇后问题
    解析： 暂无解析

  • 第8题：

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

    广度优先

    B

    活结点优先

    C

    扩展结点优先

    D

    深度优先


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

  • 第9题：

    问答题
    回溯法中常见的两类典型的解空间树是什么？并简述其定义。

    正确答案： 回溯法中常见的两类典型的解空间树是子集树和排列树。
    当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
    当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。
    解析： 暂无解析

  • 第10题：

    单选题
    回溯法解旅行售货员问题时的解空间树是（）。
    A

    子集树

    B

    排列树

    C

    深度优先生成树

    D

    广度优先生成树


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

  • 第11题：

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

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    回溯法求解子集树问题


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

  • 第12题：

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

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

  • 第13题：

    回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数。()

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


    正确答案:√

  • 第14题：

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

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

    正确答案:A

  • 第15题：

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

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

    正确答案:D

  • 第16题：

    回溯法解旅行售货员问题时的解空间树是（）。

    • A、子集树
    • B、排列树
    • C、深度优先生成树
    • D、广度优先生成树

    正确答案:B

  • 第17题：

    使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是（），只使用约束条件进行裁剪的是（）。


    正确答案:0/1背包问题；N皇后问题

  • 第18题：

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

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

    正确答案:A

  • 第19题：

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

    有序树

    B

    子集树

    C

    排列树

    D

    无序树


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

  • 第20题：

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

    广度优先

    B

    活结点优先

    C

    扩展结点优先

    D

    深度优先


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

  • 第21题：

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

    回溯法

    B

    分支限界法

    C

    回溯法和分支限界法

    D

    动态规划


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

  • 第22题：

    单选题
    下面哪种函数是回溯法中为避免无效搜索采取的策略（）
    A

    递归函数

    B

    剪枝函数

    C

    随机数函数

    D

    搜索函数


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

  • 第23题：

    填空题
    回溯法搜索解空间树时，常用的两种剪枝函数为（）和（）。

    正确答案： 约束函数,限界函数
    解析： 暂无解析

相关内容