回溯法的含义是指加剪枝的深度优先展开方法，这样的说法正确吗？

[单选题]

```
正确
```
```
不正确
```

推荐

白驹之过隙

选A。

回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。其特点是探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。
深度优先是采用递归的方法，先沿一条路搜到底，再递归回上一个节点，沿另一个方向搜索，以此类推。
剪枝分为两种：最优化剪枝，如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中，总长度已经大于等于L的走法，就可以直接放弃，不用走到底了；可行性剪枝，如果当前到达已大于k，或者等于k且没有到达终点，就可以直接放弃。

编辑于 2019-10-31 14:24:48 回复(1)

chenzhizhen2020

正确

回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

剪枝,属于算法优化范畴；通常应用在DFS 和 BFS 搜索算法中；剪枝策略就是寻找过滤条件，提前减少不必要的搜索路径。

剪枝分为可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。

最优性剪枝，如果当前花费已经超过当前搜索最优解，那么无论之后采取多么优秀的策略到达递归边界都不肯能更新答案

极端法：通过对当前节点进行理想式扩展，通过否定这样的情况来避免对当前的节点扩展；

调整法：基本思想通过对子树的比较剪掉重复子树和明显不是最有前途的子树；

数学方法：利用专门剪枝知识，借助数学模型

可行性剪枝：该方法判断继续搜索能否得出答案，如果不能直接回溯。

综上，回溯法就是带剪枝的dfs

编辑于 2019-10-31 14:32:38 回复(3)

天尊墨宇

选A

回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。其特点是探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。

深度优先是采用递归的方法，先沿一条路搜到底，再递归回上一个节点，沿另一个方向搜索，以此类推。

剪枝分为两种：最优化剪枝，如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中，总长度已经大于等于L的走法，就可以直接放弃，不用走到底了；可行性剪枝，如果当前到达已大于k，或者等于k且没有到达终点，就可以直接放弃。

发表于 2020-06-20 14:15:53 回复(0)

提交观点

问题信息

搜索

上传者：蜡蜡

难度：

3条回答 90收藏 5385浏览

回溯法的含义是指加剪枝的深度优先展开方法，这样的说法正确吗？

问题信息

热门推荐

相关试题