工学
单选题回溯法搜索状态空间树是按照（）的顺序。A 中序遍历B 广度优先遍历C 深度优先遍历D 层次优先遍历
题目
单选题
回溯法搜索状态空间树是按照（）的顺序。
A
中序遍历
B
广度优先遍历
C
深度优先遍历
D
层次优先遍历
参考答案和解析
正确答案：
C
解析：
暂无解析
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案
第1题：
回溯法中常见的两类典型的解空间树是子集树和排列树。()
此题为判断题(对，错)。
正确答案:√
第2题：
回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数。()
此题为判断题(对，错)。
正确答案:√
第3题：
分支限界法与回溯法的相同点是()
A.求解目标相同
B.搜索方式相同
C.对扩展结点的扩展方式相同
D.都是一种在问题的解空间树T中搜索问题解的算法
参考答案：D
第4题：
回溯法中常见的两类典型的解空间树是什么？并简述其定义。
正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。
第5题：
回溯法在解空间树T上的搜索方式是（）
- A、深度优先
- B、广度优先
- C、最小耗费优先
- D、活结点优先
正确答案:A
第6题：
回溯法在问题的解空间树中,按扩展结点优先策略,从根结点出发搜索解空间树。()
此题为判断题(对，错)。
正确答案:×
第7题：
考虑表6—1的实例，假设有3个物品，背包容量为22。图6—6中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字I／O分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6)。
对于表6—1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为 (7) ，而用了上述回溯法，搜索树的结点数为 (8) .
正确答案：(5)2与3(6) 35(7) 15(8) 8
(5)2与3(6) 35(7) 15(8) 8 解析：本题实质上是一个0-1背包问题，该问题最优化的目标函数是
max∑vixi(xi=0，1)；
约束函数是：
∑pixi≤M(xi=0，1)。
0-1背包问题可用动态规划策略求得最优解，求解的递归式为
[*]
其中，nv[i][j]表示由前i项物品组合且价格不超过i的背包的总价值。问题最终要求的背包的总价值为nv[n][M]，根据上述递归式，可以很容易以自底向上的方式编写伪代码。
[问题1]中伪代码的第1行到第12行计算数组nv的元素值，第1行到第4行计算i为0或者j为0时nv[i]的值，对应递归式的第一种情况；第7行和第8行计算当j<pi时即不能选择mi时nv[i][j]的值，对应递归式的第二种倩况；第9行到第12行对应递归式的第三种情况，故根据递归式，空(1)的答案为nv[i-1][j]；nv[i-1][j-p[i]]+v[i]。伪代码的第13行到第19行求解哪些物品放入到背包中，物品项从后向前考虑，若nv[i][j]：nv[i-1][j]，表示物品mj没有放入背包中，即x[i]=0，故空(2)的答案为nv[i][j]=nv[i-1][j]。相反，若物品mj放入背包中，则x[i]=l，同时背包还能选择不超过l-p[i]的价格的物品，故空(3)的答案为j=j-p[i]。
(5)2与3(6) 35(7) 15(8) 8 解析：本题实质上是一个0-1背包问题，该问题最优化的目标函数是
max∑vixi(xi=0，1)；
约束函数是：
∑pixi≤M(xi=0，1)。
0-1背包问题可用动态规划策略求得最优解，求解的递归式为
[*]
其中，nv[i][j]表示由前i项物品组合且价格不超过i的背包的总价值。问题最终要求的背包的总价值为nv[n][M]，根据上述递归式，可以很容易以自底向上的方式编写伪代码。
[问题1]中伪代码的第1行到第12行计算数组nv的元素值，第1行到第4行计算i为0或者j为0时nv[i]的值，对应递归式的第一种情况；第7行和第8行计算当j<pi时即不能选择mi时nv[i][j]的值，对应递归式的第二种倩况；第9行到第12行对应递归式的第三种情况，故根据递归式，空(1)的答案为nv[i-1][j]；nv[i-1][j-p[i]]+v[i]。伪代码的第13行到第19行求解哪些物品放入到背包中，物品项从后向前考虑，若nv[i][j]：nv[i-1][j]，表示物品mj没有放入背包中，即x[i]=0，故空(2)的答案为nv[i][j]=nv[i-1][j]。相反，若物品mj放入背包中，则x[i]=l，同时背包还能选择不超过l-p[i]的价格的物品，故空(3)的答案为j=j-p[i]。
第8题：
回溯法解旅行售货员问题时的解空间树是子集树。()
此题为判断题(对，错)。
正确答案:√
第9题：
在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）
- A、回溯法
- B、分支限界法
- C、回溯法和分支限界法
- D、动态规划
正确答案:A
第10题：
回溯法搜索状态空间树是按照（）的顺序。
- A、中序遍历
- B、广度优先遍历
- C、深度优先遍历
- D、层次优先遍历
正确答案:C