图解回溯算法

青旅半醒 2022-11-27 10:14 219阅读 0赞

## 回溯算法 ##

**是什么？**

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

**可以解决什么问题？**

*  排列、组合（子集、幂集、字符全排列）。 在传值时，对于排列问题，是要删掉单个用过的元素；组合问题，是删掉前面所有的元素。
 *  数组、字符串，给定一个特定的规则，尝试搜索迭代找到某个解。
 *  二维数组下的DFS搜索（八皇后、黄金矿工、数独）

**如何理解回溯算法？**

*  为问题建立解空间结构
 *  在解空间结构上进行DFS搜索
 *  设立回溯出口和剪枝点，减少无效搜索，出口处保存有效解

**如何理解回溯的解空间**

回溯算法有两种常见的解空间模型，分别对应数学中的两种暴力思想，组合以及排列。其中子集问题，对应数学中的组合问题。排列问题对应数学中的排列问题。

*  [子集树][Link 3]
 *  [排列树][Link 4]

接下来根据这两道leetcode题目，来分析回溯的解空间应该如何构建，其他的题目大都是基于这两个基础题目变形而形成的。

**全排列问题分析**

案例：对数组\[1,2,3\]进行排序的解空间如下所示，整个树结构可以按照下面的逻辑理解：

*  结点表示当前所处的状态，路径表示当前的选择
 *  每一个结点表示了“全排列”问题求解的不同阶段，这些阶段通过变量的“不同的值”体现，这些值可以称之为状态或者路径
 *  使用DFS遍历整个搜索树，如果搜索结点回溯到上一层，那么则需要将状态进行重置
 *  当遍历到叶子节点时，就退出。判断方法为没有候选元素了，或者根据当前的深度进行判断

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center]

**组合问题分析**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center 1]

组合问题的解空间构成

*  节点代表状态，当前选取了什么元素
 *  每一个分支，代表一种元素选择的方式
 *  扩展节点的时候，可以进行适当的剪枝，如下所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center 2]

**回溯算法的设计思路**

1.  **全局变量**： 保存结果
2.  **参数设计：**
    
     *  候选列表。用来实现解空间舒节点的扩展
     *  路径。用来记录当前节点的列表选择状态
     *  条件变量。用来结束回溯的判断条件，以及用来剪枝的判断条件
     *  全局变量。用来存储每个过程的解
3.  **回溯实现**： 回溯的代码可以主要分为三部分
    
     *  回溯出口。找到满足约束条件下的解，记录该解，然后返回。一般放在函数的入口处
     *  节点扩展。从候选列表中，选择合适的元素进行递归求解，在节点扩展阶段，需要改变路径和条件变量来适应新的节点。
        
         *  扩展的规则主要有排列和组合两种
         *  排列情况。要求每次选择没有选过的元素
         *  组合情况。每次只能往后选，不能向前选，从后往前选就会出现重复问题
         *  选择子串。这种情况下不同于排列和组合（这两种都是每次选择一个元素），现在这种情况将会选择一个连续的序列，属于组合情况的一种特列。
     *  剪枝。剪枝的操作是为了减去解空间中不合适的分支。剪枝可以在回溯的出口处检测，也可以在节点扩展的时候检测。

**算法模板**

result = []//记录最终结果
    func backtrack(选择列表,路径,条件变量):
    	//回溯剪枝
    	//回溯出口，找到指定的解
        if 满足结束条件:
            result.add(路径)
            return
    	//节点扩展
        for 选择 in 选择列表:
            //检查待选元素是否符合题目所规定的规则
    		做检查//check()
    		做选择//更改路径和条件变量的值
            backtrack(选择列表,路径)
            撤销选择//还原路径和条件变量的值

*  选择列表指的是当前层扩展DFS节点的时候，可以选择的元素有哪些
 *  路径用来记录当前层节点的状态
 *  条件变量用来进行剪枝操作和实现递归出口操作

**参考文献**

[回溯算法的模板][Link 5]

[回溯法的解空间表示方法][Link 6]

[通过全排列问题来理解回溯算法][Link 7]

[递归和回溯的区别][Link 8]

《剑指offer》2.4.3节

**回溯法例题**

*  [leetcode排列组合编程题][leetcode]

[Link 1]: https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%E6%9D%A1%E4%BB%B6/1783021
[Link 2]: https://link.zhihu.com/?target=https%3A//baike.baidu.com/item/%E7%8A%B6%E6%80%81/33204
[Link 3]: https://leetcode-cn.com/problems/subsets/
[Link 4]: https://leetcode-cn.com/problems/permutations/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/65dcada2c6094414a55d7bb6558c9bef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/ea8e6e5585c1403e90056a9d51bdf031.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1aTk1MTc1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/7f5911e4e4124f339cd346f49db8ed04.png
[Link 5]: https://zhuanlan.zhihu.com/p/112926891
[Link 6]: https://www.nowcoder.com/discuss/529
[Link 7]: https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
[Link 8]: https://cloud.tencent.com/developer/article/1434886
[leetcode]: https://blog.csdn.net/ccbrid/article/details/98482434