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

  • 关注下方微信公众号，在线模考后查看

热门试题