回溯 = 深度优先搜索(DFS) + 剪枝

JustYY.com 小赖子的英国生活和资讯

2 weeks ago

“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。

DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。

剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。

回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。

DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索；

剪枝则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。

因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。

Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。

alpha-beta-pruning

Alpha-beta 剪枝：这是用于减少博弈论中极小极大算法中评估节点数量的一种技术。

回溯算法：Alpha-beta 剪枝确实可以被视为回溯的一种形式，因为它系统地探索潜在解决方案（在本例中为游戏动作）并修剪保证不会影响最终决策的路径。

深度优先搜索 (DFS)：Alpha-beta 剪枝通常使用 DFS 对树结构进行操作，在回溯之前深入探索节点。

剪枝技术：Alpha-beta 剪枝的主要特征是“剪枝”部分，其中跳过不可能影响最终决策的树的分支。

微信公众号: 小赖子的英国生活和资讯 JustYYUK