关于回溯搜索法的介绍,下面()是不正确描述。A、回溯法有“通用解题法”之称,它可以系统地搜索一个问题的所有解或任意解B、回溯法是一种既带系统性又带有跳跃性的搜索算法C、回溯算法在生成解空间的任一结点时,先判断该结点是否可能包含问题的解,如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向祖先结点回溯D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径

题目

关于回溯搜索法的介绍,下面()是不正确描述。

  • A、回溯法有“通用解题法”之称,它可以系统地搜索一个问题的所有解或任意解
  • B、回溯法是一种既带系统性又带有跳跃性的搜索算法
  • C、回溯算法在生成解空间的任一结点时,先判断该结点是否可能包含问题的解,如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向祖先结点回溯
  • D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
参考答案和解析
正确答案:D
如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

回溯法是一种既带有系统性又带有跳跃性的搜索算法。()

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


正确答案:√

第2题:

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。()

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


正确答案:√

第3题:

分支限界法与回溯法的相同点是()

A.求解目标相同

B.搜索方式相同

C.对扩展结点的扩展方式相同

D.都是一种在问题的解空间树T中搜索问题解的算法


参考答案:D

第4题:

【问题 1】(8 分)

用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。

回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。

下面给出 0-1背包问题的回溯算法伪代码。

函数参数说明如下:

W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。

变量说明如下:

cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。


正确答案:
(1)k←1或其等价形式(2)cw←cw+w[k]或其等价形式(3)k←k–1或其等价形式(4)k←k+l或其等价形式

第5题:

回溯法也称为试探法。以下关于回溯法的结论中正确的是(50)。

A.即使问题的解存在,回溯法不一定能找到问题的解

B.回溯法找到的问题的解不一定是最优解

C.回溯法不能找到问题的全部解

D.回溯法无法避免求出的问题解的重复


正确答案:B
解析:回溯法又称为试探法,是找到问题解的一种搜索策略,就是在用某种方法找出的解的过程中,若中间项结果满足所解问题的条件,则一直沿这个方向搜索下去,直到无路可走或无结果,则开始回溯,改变其前一项的方向(或值)继续搜索。若其上一项的方向(或值)都已经测试过,还无路可走或无结果,则再继续回溯到更前一项,改变其方向(或值)继续搜索。若找到了一个符合条件的解,则停止或输出这个结果继续搜索,这个解不一定是最优解;否则继续回溯下去,直到回溯到问题的开始处(不能再回溯),仍没有找到符合条件的解,则表示此问题无解或已经找到了全部的解。

第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]。

第8题:

关于分支限界法的搜索策略描述错误的是()

A.在扩展结点处,先生成其所有的儿子结点(分支)

B.从当前的活结点表中选择上一个扩展结点。

C.为了有效地选择下一扩展结点,加速搜索的进程,在每一个活结点处,计算一个函数值(限界)

D.根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。


参考答案:B

第9题:

【问题2】(7分)

考虑表4-1的实例,假设有3个物品,背包容量为22。图4-1中是根据上述算法构造的搜索树,其中结点的编号表示了搜索树生成的顺序,边上的数字1/0分别表示选择/不选择对应物品。除了根结点之外,每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值,右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解,应该选择物品 (5) ,获得的价值为 (6) 。

对于表4-1的实例,若采用穷举法搜索整个解空间,则搜索树的结点数为 (7) ,而用了上述回溯法,搜索树的结点数为 (8) 。


正确答案:
(5)物品2和物品3(2分)(6)35(1分)(7)15(2分)(8)8(2分)

第10题:

回溯法是一种既带有()又带有()的搜索算法。


正确答案:系统性;跳跃性

更多相关问题