登录回溯 = 深度优先搜索(DFS) + 剪枝
“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。
深度优先搜索 (DFS)
DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。
剪枝/Pruning
剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。
回溯算法/Backtracking
回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。
结合三者的理解
DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索；
剪枝 则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。
因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。
例子：Alpha-beta 算法剪枝
Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。
alpha-beta-pruning
Alpha-beta 剪枝：这是用于减少博弈论中极小极大算法中评估节点数量的一种技术。
回溯算法：Alpha-beta 剪枝确实可以被视为回溯的一种形式，因为它系统地探索潜在解决方案（在本例中为游戏动作）并修剪保证不会影响最终决策的路径。
深度优先搜索 (DFS)：Alpha-beta 剪枝通常使用 DFS 对树结构进行操作，在回溯之前深入探索节点。
剪枝技术：Alpha-beta 剪枝的主要特征是“剪枝”部分，其中跳过不可能影响最终决策的树的分支。
英文：Backtracking Algorithm = Depth First Search + Pruning
本文一共 810 个汉字, 你数一下对不对.
相关文章：
- 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
- 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
- 软件工程师面试技巧之: 使用哈希表降复杂度 最近在刷题, 倒不是为了找工作, 主要是为了练练脑子, 日子过得太舒服, 人脑不动容易变笨. 程序员应该都了解并能熟悉使用 Hash 哈希表, 哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N). 我们来看一道简单的面试题: 给定一个数组,找出相差为2的数对,比如: {1, 3, 5,...
- 升级到 Delphi 10 西雅图 公司前不久买了DELPHI XE8 (花了1400多英镑 一套). 并且买一送一, 我选择了 Delphi 2007. 因为D2007是 ANSI版本中最好的WIN32开发利器. 由于当时选了一年的升级服务 所以昨天发布的 Delphi 10 Seattle...
- 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
- 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
- Javascript 中 sleep 函数实现 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1 2 3...
- 在英国开车走公交通道 Bus Lane 被罚款的经历 昨天才发现有一封信没有打开, 打开后心凉了一下, 原来是媳妇开车不小心走 Bus Lane (公交通道)被摄像头拍到, 需要交罚款. 走公交通道 Bus Lane可以申诉么? 信上说, 如果有足够的理由, 可以在28天内提交相关的证据来申诉抗议, 会有人来审核, 当然不一定能保证通过....
