此题为判断题(对,错)。
第1题:
回溯法中,如果解空间树是子集树,当所给的问题规模为n时,通常有2^n个叶结点,遍历子集树需O(2^n)计算时间 。
第2题:
子集和问题:给定n个不同的正整数,已知其和大于c,要求找出一个子集使其和等于c。 该问题除解空间树是子集树的回溯法外,还有解空间树是排列树的回溯算法,思考该问题, 从如下选项中找到关于该算法的正确的描述。
A.当解空间树是排列树时, 搜索时,可以将从根结点到当前扩展结点的路径上的数看成是一个子集。
B.剪枝条件:当路径上的数之和>c时剪枝
C.该算法搜索至排列树的叶子结点(即第n层结点)时, 就找到了一个解。
D.数据预处理,将n个数按从小到大排序存放于x[1:n],可以提高该算法的搜索效率。
第3题:
回溯法解旅行商问题的解空间树为()注意:填空填1234中的某个数,不填汉字 1. 子集树 2. 排列树 3. 二叉树 4. 三叉树
第4题:
【单选题】分支限界法解旅行商问题时的解空间树是()。
A.子集树
B.排列树
C.深度优先生成树
D.广度优先生成树
第5题:
回溯算法和分支限界法的问题的解空间树不会是()注意:填空填1234中的某个数,不填汉字 1. 有序树 2. 子集树 3. 排列树 4. 无序树