回溯算法——我欲修仙（功法篇）

太过爱你忘了你带给我的痛 2024-04-13 14:15 21阅读 0赞

> 个人主页：[【😊个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]

![壁纸][1bd9b9f34db140198b948814371263e2.jpeg_pic_center]

--------------------

## 系列文章目录 ##

第一章 ❤️ [学习前的必知知识][Link 3]  
第二章 ❤️ [二分查找][Link 4]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  回溯算法🤔🤔🤔
 *  回溯算法一般可以解决的问题
 *  回溯算法的实现
 *  回溯算法的固定模板(回溯三部曲)
 *   *  回溯函数模板返回值以及参数
     *  回溯函数终止条件
     *  回溯搜索的遍历过程
 *  总结

--------------------

## 回溯算法🤔🤔🤔 ##

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为:

> 1、定义一个解空间，它包含问题的解。  
> 2、利用适于搜索的方法组织解空间。  
> 3、利用深度优先法搜索解空间。  
> 4、利用限界函数避免移动到不可能产生解的子空间。

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
    在二叉树系列中，我们提到过回溯，例如二叉树：
    以为使用了递归，其实还隐藏着 回溯 (opens new window)。
     回溯是递归的副产品，只要有递归就会有回溯。
     回溯函数也就是递归函数，指的都是一个函数。

*问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。*

![在这里插入图片描述][57bf9444ef85411bbcd8dcb05bb50bdb.png_pic_center]

## 回溯算法一般可以解决的问题 ##

>  *  组合问题：N个数里面按一定规则找出k个数的集合
>  *  切割问题：一个字符串按一定规则有几种切割方式
>  *  子集问题：一个N个数的集合里有多少符合条件的子集
>  *  排列问题：N个数按一定规则全排列，有几种排列方式
>  *  棋盘问题：N皇后，解数独等等

## 回溯算法的实现 ##

> 使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。例如，在解决列举集合\{1,2,3\}所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：

![在这里插入图片描述][a4f1f28c1c1644c3ab3d69a50a861fb9.png_pic_center]

> 回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的答案。图中的状态树是满二叉树，得到的叶子结点全部都是问题的解。  
> 在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，有时会发现此种情况下，再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。

## 回溯算法的固定模板(回溯三部曲) ##

### 回溯函数模板返回值以及参数 ###

> 在回溯算法中，习惯是为函数命名为backtracking，这个起名是随意。  
> 回溯算法中函数返回值一般为void。  
> 回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯函数伪代码如下：

void backtracking(参数)

### 回溯函数终止条件 ###

> 既然是树形结构，那么我们在讲解二叉树的递归 (opens new window)的时候，就知道遍历树形结构一定要有终止条件。  
> 所以回溯也有要终止条件。  
> 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

所以回溯函数终止条件伪代码如下：

if (终止条件) {
        
        存放结果;
        return;
    }

### 回溯搜索的遍历过程 ###

> 回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

回溯函数遍历过程伪代码如下：
    void backtracking(参数) {
        
        if (终止条件) {
        
            存放结果;
            return;
        }
    
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }
    
    }

> for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。  
> 函数这里自己调用自己，实现递归。  
> 我们可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

## 总结 ##

> 解决问题时，每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯算法。

![在这里插入图片描述][533c5d042e8b4887a2234e8ac174d8c1.gif_pic_center]

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[1bd9b9f34db140198b948814371263e2.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/5520542683c44e0b9399ceaa50f42172.jpeg
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129731407?spm=1001.2014.3001.5501
[57bf9444ef85411bbcd8dcb05bb50bdb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/0d0541338a5145019cdf3ee1dddff549.png
[a4f1f28c1c1644c3ab3d69a50a861fb9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/6b5e6412f7604afa9f108392e773fd9f.png
[533c5d042e8b4887a2234e8ac174d8c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/68a23f6fd46b4616b2d54b4aba4aae9c.gif