简答题

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

正确答案

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

答案解析

相似试题
  • 回溯法解旅行售货员问题时的解空间树是()。

    单选题查看答案

  • 回溯法搜索状态空间树是按照()的顺序。

    单选题查看答案

  • 请画出用回溯法解4皇后问题的解空间树和搜索空间树。

    简答题查看答案

  • 回溯算法和分支限界法的问题的解空间树不会是()

    单选题查看答案

  • 请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20,15,10},价值为{20,30,25},背包容量为25时搜索空间树。

    简答题查看答案

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

    填空题查看答案

  • 用状态空间法表示问题时,什么是问题的解?求解过的本质是什么?

    简答题查看答案

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

    单选题查看答案

  • 回溯法在解空间树T上的搜索方式是()

    单选题查看答案