回溯算法
是什么？
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
可以解决什么问题？
- 排列、组合（子集、幂集、字符全排列）。 在传值时，对于排列问题，是要删掉单个用过的元素；组合问题，是删掉前面所有的元素。
- 数组、字符串，给定一个特定的规则，尝试搜索迭代找到某个解。
- 二维数组下的DFS搜索（八皇后、黄金矿工、数独）
如何理解回溯算法？
- 为问题建立解空间结构
- 在解空间结构上进行DFS搜索
- 设立回溯出口和剪枝点，减少无效搜索，出口处保存有效解
如何理解回溯的解空间
回溯算法有两种常见的解空间模型，分别对应数学中的两种暴力思想，组合以及排列。其中子集问题，对应数学中的组合问题。排列问题对应数学中的排列问题。
- 子集树
- 排列树
接下来根据这两道leetcode题目，来分析回溯的解空间应该如何构建，其他的题目大都是基于这两个基础题目变形而形成的。
全排列问题分析
案例：对数组[1,2,3]进行排序的解空间如下所示，整个树结构可以按照下面的逻辑理解：
- 结点表示当前所处的状态，路径表示当前的选择
- 每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现，这些值可以称之为状态或者路径
- 使用DFS遍历整个搜索树，如果搜索结点回溯到上一层，那么则需要将状态进行重置
- 当遍历到叶子节点时，就退出。判断方法为没有候选元素了，或者根据当前的深度进行判断
组合问题分析
组合问题的解空间构成
- 节点代表状态，当前选取了什么元素
- 每一个分支，代表一种元素选择的方式
- 扩展节点的时候，可以进行适当的剪枝，如下所示
回溯算法的设计思路
- 全局变量： 保存结果
- 参数设计：
- 候选列表。用来实现解空间舒节点的扩展
- 路径。用来记录当前节点的列表选择状态
- 条件变量。用来结束回溯的判断条件，以及用来剪枝的判断条件
- 全局变量。用来存储每个过程的解
- 回溯实现： 回溯的代码可以主要分为三部分
- 回溯出口。找到满足约束条件下的解，记录该解，然后返回。一般放在函数的入口处
- 节点扩展。从候选列表中，选择合适的元素进行递归求解，在节点扩展阶段，需要改变路径和条件变量来适应新的节点。
- 扩展的规则主要有排列和组合两种
- 排列情况。要求每次选择没有选过的元素
- 组合情况。每次只能往后选，不能向前选，从后往前选就会出现重复问题
- 选择子串。这种情况下不同于排列和组合（这两种都是每次选择一个元素），现在这种情况将会选择一个连续的序列，属于组合情况的一种特列。
- 剪枝。剪枝的操作是为了减去解空间中不合适的分支。剪枝可以在回溯的出口处检测，也可以在节点扩展的时候检测。
算法模板
result = []//记录最终结果 func backtrack(选择列表,路径,条件变量): //回溯剪枝 //回溯出口，找到指定的解 if 满足结束条件: result.add(路径) return //节点扩展 for 选择 in 选择列表: //检查待选元素是否符合题目所规定的规则 做检查//check() 做选择//更改路径和条件变量的值 backtrack(选择列表,路径) 撤销选择//还原路径和条件变量的值 - 选择列表指的是当前层扩展DFS节点的时候，可以选择的元素有哪些
- 路径用来记录当前层节点的状态
- 条件变量用来进行剪枝操作和实现递归出口操作
参考文献
回溯算法的模板
回溯法的解空间表示方法
通过全排列问题来理解回溯算法
递归和回溯的区别
《剑指offer》2.4.3节
回溯法例题
- leetcode排列组合编程题
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199423.html原文链接：https://javaforall.net
