回溯算法理论基础

比眉伴天荒 2024-03-30 17:45 65阅读 0赞

### **什么是回溯法** ###

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

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯。

回溯是递归的副产品，只要有递归就会有回溯。

**所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数**。

### **回溯法的效率** ###

回溯法的性能如何呢，这里要和大家说清楚了，**虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法**。

**因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案**，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。

### **回溯法解决的问题** ###

回溯法，一般可以解决如下几种问题：

*  组合问题：N个数里面按一定规则找出k个数的集合

*  切割问题：一个字符串按一定规则有几种切割方式

*  子集问题：一个N个数的集合里有多少符合条件的子集

*  排列问题：N个数按一定规则全排列，有几种排列方式

*  棋盘问题：N皇后，解数独等等

**相信大家看着这些之后会发现，每个问题，都不简单！**

另外，会有一些同学可能分不清什么是组合，什么是排列？

**组合是不强调元素顺序的，排列是强调元素顺序**。

例如：\{1, 2\} 和 \{2, 1\} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，\{1, 2\} 和 \{2, 1\} 就是两个集合了。

记住组合无序，排列有序，就可以了。

### **如何理解回溯法** ###

**回溯法解决的问题都可以抽象为树形结构**，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，**集合的大小就构成了树的宽度，递归的深度，就构成了树的深度**。

是递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

### **回溯法模板** ###

递归有递归的三部曲，这里给大家列出回溯三部曲。

*  回溯函数递归函数参数以及返回值

在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯函数伪代码如下：

void backtracking(参数)

1

*  回溯函数终止条件

既然是树形结构，那么我们在讲解二叉树的递归的时候，就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

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

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

*  回溯搜索的遍历过程（确定单层搜索/递归逻辑）

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

![810258df004544c8129b7f27cc18b737.png][]

注意图中，特意举例集合大小和孩子的数量是相等的！

回溯函数遍历过程伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

大家可以从图中看出**for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历**，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找到其中一个结果了。

分析完过程，回溯算法模板框架如下：

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

**这份模板很重要，做回溯法的题目都靠它了！**

### **总结** ###

本篇我们讲解了，什么是回溯算法，知道了回溯和递归是相辅相成的。

接着提到了回溯法的效率，回溯法其实就是暴力查找，并不是什么高效的算法。

然后列出了回溯法可以解决几类问题，可以看出每一类问题都不简单。

最后我们讲到回溯法解决的问题都可以抽象为树形结构（N叉树），并给出了回溯法的模板。

[810258df004544c8129b7f27cc18b737.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/148d9440b7e8470296f18b6fe6b9bba7.png

发表评论取消回复

表情：

评论列表（有 0 条评论，65人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-回溯算法

一、回溯 1、定义：通过选择不同的岔路口来通往目的地（找到想要的结果）每一步都选择一条路出发，`能进则进，不能进则退回上一步（回溯）`，换一条路再

曾经终败给现在/ 2024年04月08日 09:49/ 0 赞/ 83 阅读

相关回溯算法理论基础

什么是回溯法 -------------------- 回溯法也可以叫做回溯搜索法，它是一种搜索的方式。在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以

比眉伴天荒/ 2024年03月30日 17:45/ 0 赞/ 66 阅读

相关贪心算法理论基础

什么是贪心算法贪心的本质是选择每一阶段的局部最优，从而达到全局最优。 “局部最优是什么，能不能推导出全局最优”这个思考方式也是贯彻贪心算法解题过程的贪心的两个极

Love The Way You Lie/ 2024年03月29日 16:16/ 0 赞/ 70 阅读

相关回溯算法理论基础

目录什么是回溯法回溯法的效率回溯法解决的问题如何理解回溯法回溯法模板什么是回溯法

快来打我*/ 2024年03月27日 17:52/ 0 赞/ 69 阅读

相关【算法】回溯

回溯本质上就是递归，是一种穷举的算法，可以进行剪枝 n叉树递归的过程可以抽象为n叉树 ![在这里插入图片描述][bf42cfb5a3b74b96973fd6

Bertha 。/ 2024年03月26日 12:23/ 0 赞/ 70 阅读

相关回溯算法理论基础

回溯算法理论基础题目分类理论基础什么是回溯法回溯法的效率回溯法解决的问题组合和排列的区

Love The Way You Lie/ 2023年10月16日 12:18/ 0 赞/ 59 阅读

相关回溯算法和贪心算法_回溯（类型和算法）

回溯算法和贪心算法回溯 (Backtracking) The name backtrack was first given by [D. H. Lehmer][

r囧r小猫/ 2023年03月05日 15:50/ 0 赞/ 21 阅读

相关算法基础之回溯

算法基础之回溯（C++示例）回溯法（BackTracking）也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。若探索到某一步，发现原先选择并不优或达不到目

傷城~/ 2022年09月07日 00:08/ 0 赞/ 215 阅读

相关回溯算法

引自：http://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741376.html 作者写的通俗易懂，学习。 1、

小鱼儿/ 2022年08月01日 13:43/ 0 赞/ 218 阅读

相关回溯算法

回溯算法有“通用解题”之称。用它可以系统地搜索所有的解。它既可以系统的搜索又可以跳跃式的搜索所有子集。回溯算法主要有三点必须要彻底的弄清楚【1】问题解空间的集合，合理的

谁践踏了优雅/ 2021年11月11日 04:02/ 0 赞/ 408 阅读