简述回溯法。
题目
简述回溯法。
相似考题
参考答案和解析
正确答案:回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
更多“简述回溯法。”相关问题
-
第1题：
回溯法程序调试策略有什么特点？
正确答案:回溯法的特点是沿程序的控制流程往回追踪源程序代码，直到找出错误根源或确定故障范围为止。对于小程序，回溯法是一种比较好的调试策略，往往能把故障范围缩小为程序中的一小段代码，能确定故障的准确位置。但对于大型程序，由于需要回溯的路径数目太多，以至回溯变得困难起来。 -
第2题：
回溯法中常见的两类典型的解空间树是什么？并简述其定义。
正确答案: 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。 -
第3题：
简述回溯法的基本思想，采用这种算法的关键是什么？
正确答案:回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的 是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。 -
第4题：
在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）
- A、回溯法
- B、分支限界法
- C、回溯法和分支限界法
- D、回溯法求解子集树问题
正确答案:B -
第5题：
什么是回溯推理？简述其在刑事侦查工作中的应用？
正确答案: （1）回溯推理是从结果推测原因或者从推断推论理由的推理。
（2）回溯推理在刑事侦查工作中具有特别重要的作用。在侦查工作中，作案结果是已知的，罪犯作案过程是未知的，通常要用回溯推理的形式，从结果推测原因。但运用回溯推理只是给破案提供了或然性结论，即结论只是可能真，并非必然真。要使可能性结论转化为确定性结论，最终要以实践来检验。 -
第6题：
简单描述回溯法基本思想。
正确答案:回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。 -
第7题：
填空题调试技术包括简单调试归纳法调试演绎法调试回溯法调试109、回溯法调试是从程序产生错误的地方出发，而归纳法调试是从（）入手。正确答案： 测试结果发现的线索解析： 暂无解析 -
第8题：
问答题简述回溯法的基本思想，采用这种算法的关键是什么？正确答案： 回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的 是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。解析： 暂无解析 -
第9题：
问答题回溯法与分支限界法的区别是什么？正确答案： 两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。解析： 暂无解析 -
第10题：
问答题简述分支限界法与回溯法的异同。正确答案： 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：
（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同；
（4）存储空间的要求不同。解析： 暂无解析 -
第11题：
单选题在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）A回溯法
B分支限界法
C回溯法和分支限界法
D回溯法求解子集树问题
正确答案： C解析： 暂无解析 -
第12题：
问答题回溯法程序调试策略有什么特点？正确答案： 回溯法的特点是沿程序的控制流程往回追踪源程序代码，直到找出错误根源或确定故障范围为止。对于小程序，回溯法是一种比较好的调试策略，往往能把故障范围缩小为程序中的一小段代码，能确定故障的准确位置。但对于大型程序，由于需要回溯的路径数目太多，以至回溯变得困难起来。解析： 暂无解析 -
第13题：
简述分支限界法与回溯法的异同。
正确答案: 分支限界法与回溯法的相同点是：都是一种在问题的解空间树T中搜索问题解的算法。
不同点：
（1）求解目标不同；
（2）搜索方式不同；
（3）对扩展结点的扩展方式不同；
（4）存储空间的要求不同。 -
第14题：
调试技术包括简单调试归纳法调试演绎法调试回溯法调试109、回溯法调试是从程序产生错误的地方出发，而归纳法调试是从（）入手。
正确答案:测试结果发现的线索 -
第15题：
回溯法与分支限界法的区别是什么？
正确答案:两者都是问题的解空间树上搜索问题解的算法。回溯法与分支限界法的的求解目标不同，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标是找出解空间树中满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。 -
第16题：
关于回溯搜索法的介绍，下面（）是不正确描述。
- A、回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
- B、回溯法是一种既带系统性又带有跳跃性的搜索算法
- C、回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
- D、回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
正确答案:D -
第17题：
回溯法是指（）。
正确答案:具有限界函数的深度优先生成法 -
第18题：
下列哪个不是常用的调试策略（）。
- A、试探法
- B、回溯法
- C、流程法
- D、演绎法
正确答案:C -
第19题：
问答题简述回溯法。正确答案： 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。解析： 暂无解析 -
第20题：
单选题关于回溯搜索法的介绍，下面（）是不正确描述。A回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解
B回溯法是一种既带系统性又带有跳跃性的搜索算法
C回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯
D回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
正确答案： C解析： 暂无解析 -
第21题：
问答题回溯法中常见的两类典型的解空间树是什么？并简述其定义。正确答案： 回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。这类子集树通常有2n个叶结点，遍历子集树需O（2n）计算时间。
当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O（n!）计算时间。解析： 暂无解析 -
第22题：
单选题在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（）A回溯法
B分支限界法
C回溯法和分支限界法
D动态规划
正确答案： B解析： 暂无解析 -
第23题：
问答题简单描述回溯法基本思想。正确答案： 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。解析： 暂无解析