当前位置: article > 正文

回溯法与DFS_回溯算法是dfs吗

作者：Monodyee | 2024-04-24 06:45:27

踩

回溯算法是dfs吗

回溯法 = DFS + 剪枝
回溯法采用的是深度优先搜索的策略，当搜索到解空间树的某一结点时，用约束条件判断对该结点是否需要剪枝，如果结点不可行需要剪枝，则跳过以当前结点为根节点的子树的搜索，回溯到父结点；否则，继续按DFS策略搜索子树。

单纯的DFS以深度为关键词进行搜索时，不会对约束条件进行判断，而是在搜索完成（到达边界）时才会判断是否满足约束条件，进而判断是否形成一个可行解。

例如DFS求解01背包问题，深度优先搜索物品的过程中没有判断已选物品是否超过背包最大容量，而是在所有物品遍历完成后才判断。当然可以在搜索的过程中对每个结点进行背包容量约束条件判断（剪枝），这就相于跳过当前子树，返回父结点，进而搜索另一子树，这就是回溯法（=DFS+剪枝）。剪枝形成了回溯，子树剪掉，返回父结点，进入另一子树。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/478052