「算法与数据结构」带你看回溯算法之美

16,759 阅读10分钟

前言

这次梳理的是回溯算法,掌握它的解决问题思路,对很多搜索尝试问题,都会在日后学习工作中有所帮助。

我对回溯算法有一定理解:回溯算法建立在DFS基础之上的,但不同的是在搜索的过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索,因此我们可以这样子理解,回溯算法与DFS的区别就是有无状态重置。

如果你还不了解什么是回溯算法,或者知道一些,但是对于它具体是如何实现回溯,那么这篇文章可能适合你阅读。

那么围绕以下几个点来展开介绍回溯算法👇

  • 来源
  • 基本思路
  • 算法框架
  • 经典例题

联系👉TianTianUp,遇到问题的话,可以联系作者噢,愿意陪你一起学习一起探讨问题。


回溯算法的来源

首先,我们得明白啥叫回溯算法,它的由来是什么。

根据维基百科给出的定义👇

回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。

用回溯算法解决问题的一般步骤:

1、 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。

2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

3 、以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

用更加简单的话术来解释的话👇

回溯法可以理解成为通过选择不同的岔路口,来寻找目的地,一个岔路口一个岔路口的去尝试找到目的地,如果走错了路的话,继续返回到上一个岔路口的另外一条路,直到找到目的地。


基本思路

首先,我们得明确这个回溯算法的思路是什么,有了思路,我们才可以根据这个思路写出伪代码,有了伪代码之后,根据实际的问题,写出相应的解决方案。

我们可以把这类回溯问题,看成是解决一个决策树的遍历过程,这样子也方便我们接下来的解释👇

基本思路:

  • 从决策树的一条路开始走,能进则进,不能进则退回来,换一条路试一试。

举个例子来说,还是拿八皇后问题来解释:

  • 第一步按照顺利,也就是在第一行,我们放置第一个皇后。
  • 第二步,我们需要在第二行放置一个皇后,我们需要遍历,将符合要求的位置放置皇后。
  • 第三步,也就是在第三行,我们需要去遍历,找到符合的位置,如果都没有符合要求,我们就需要撤销第二步操作,那么需要改变第二个皇后位置,重新放置第二个皇后位置,直到满足第三个皇后放置的位置。
  • 当你改变第二个皇后位置后,都无法满足第三个皇后位置的时候,我们就需要撤销第一步操作,重新去放置第一个皇后位置,然后按照顺序完成后续操作。

我们可以通过另外一个例子来看,也就是回溯在迷宫搜索中也很常见,简单来说,就是这条路走不通的话,我们就需要撤销上个操作,返回前一个路口,继续下一条路。

似乎你已经发现了,回溯说到底就是穷举法,但是如果你只是单纯的穷举的话,不剪枝的话,时间复杂度是巨大的,那么如何剪枝呢?

我们将回溯优化的方法可以称之为剪枝,或者是剪枝函数,通过这个函数,我们可以减去一些状态,剪去一些不可能到达(最终状态),这里说的最终状态,可以认为是答案状态,这样子的话,就减少了部分空间树节点的生成,具体如何剪枝的话,可以根据做题经验多加练习,这里就不张开了。


算法框架

其实刷了一定的题量,你会发现,对于这种回溯思路而言,都是有一定的套路的,那么接下来就给出伪代码👇

接下来是自己的一点理解,觉得按照这个步骤来的话,也好理解一些👇

可以按照3个步骤来思考这类的问题:

  1. 路径:记录做出的选择。
  2. 选择列表:通常而言,用数组存储可以选择的操作。
  3. 结束条件:一般而言,就是递归的结束点,也就是搜索的结束点。
result = []

function backtrack(路径, 选择列表) {
    if('满足结束条件') {
        // 这里就是对答案做更新,依据实际题目出发
        result.push(路径)
        return
    } else {
        for(let i = 0; i < 选择列表.length; i++) {
            // 对一个选择列表做相应的选择
            
            做选择
            
            backtrack(路径, 选择列表)
            
            // 既然是回溯算法,那么在一次分岔路做完选择后
            // 需要回退我们之前做的操作
            
            撤销选择
        }
    }
}

做过类似的题目都知道,核心的处理就是for循环里面的递归操作,每次在递归之前,做选择,在这种方案结束后,我们需要撤销选择,这样子的话,就不会影响同一层决策树的其他选择。

举个例子,在走迷宫这类题型中,我们需要不断的去搜索,去试探答案,这个过程就是一个回溯算法的过程,每次要走下一个格子的时候,我们需要先将这个格子做个标记,代表这个格子已经走过,然后在往后继续搜索...

当这个方案不合理的时候,我们是不是需要将之前标记的格子清除标记呢?仔细想一想的话,这样子是非常合理的,在当前方案行不通的时候,我们要将这个步骤撤销掉

对于以上的基础知识,有了一定了解,接下来我们就通过这么基础知识来解决问题。


怎么样写回溯

做一些题目后,对回溯算法有初步认识后,我觉得可以参考下面的步骤来刻意练习👇

  • 首先画出递归树,找到状态变量(这里可以理解成回溯函数参数)。
  • 确定递归出口,一般根据具体题目条件而言。
  • 找准选择列表(一般而言与函数参数有关)。
  • 剪枝,对于一些情况而言,可以适当剪枝。
  • 做出选择,递归调用,进入下一层。
  • 撤销选择。

我觉得这个对回溯算法的总结,是挺不错的,可以借鉴下。


2个例子

接下来,我们通过三个题目作为例子,来看看怎么根据我们之前提及的算法框架来解决问题👇

字母大小写全排列⭐

链接:字母大小写全排列

给定一个字符串S,通过将字符串S中的每个字母转变大小写,我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

示例:

输入:S = "a1b2" 输出:["a1b2", "a1B2", "A1b2", "A1B2"]

输入:S = "3z4" 输出:["3z4", "3Z4"]

输入:S = "12345" 输出:["12345"]

提示:

S 的长度不超过12。 S 仅由数字和字母组成。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/letter-case-permutation 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


嗯,这题的话,可以通过画图举个例子来说,我这里就借鉴网上的图了👇

字母全排列
字母全排列

对于数字而言的话,我们直接跳过,字母的话,无非就是两种状态,大小写字母,那么我们就有接下来的思路👇

  • 遇到数字的话,不会涉及新的分支,我们就直接往后搜,这样子的话,对于数字就只需要搜索一次。
  • 对于单个字母而言,我们需要搜索2次,小写字母搜索一次,大写字母搜索一次。
  • 我们可以去维护一个index,遇到数字的话,index+1,继续递归,遇到字母的话,需要递归两次,假设当字母是小写时,我们递归一次(index+1),然后回溯时将字母转为大写,又去递归一次。
  • 递归尽头:即搜索完整个字符串为止,我们前面维护的index,这个时候就可以作为条件判断。

按照这个思路走的话,我们就可以写出完整的解题代码

代码👇

回溯算法代码-1
回溯算法代码-1

代码点这里☑️


子集🐍⭐⭐

链接:子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


做这类题目的时候,不太懂的话,可以先画图,从上面的题来看,我们可以画类似一个树的结构,然后看看如何去遍历这个决策树,看看能不能剪枝,直接借鉴一下网上的图👇

子集的递归树
子集的递归树

其实把这个图画出来,你应该就成功一半了,从这个图来看,我们似乎又可以去遍历这颗树。

首先我们得把我们思路整理一下👇

  • 这题肯定是求树的所有节点!
  • 对这颗树而言,我们可以遍历它的分支,选择其中一个分支,然后继续向下操作,不选这个分支的话,选择另外一个分支又是另外一个情况,所以每次枚举下一个数字的时候,也就是两种选择:选或不选。
  • 可以考虑使用一个index指针来记录节点的状态,即当前递归考察的数字nums[index]
  • 递归结束的条件: index === nums.length, 这个时候代表考察完所有的数字,把当前的子集加入题解,结束当前递归分支。
  • 每次结束一个分支,即结束递归,需要撤销当前的选择,(从list中删除),回到选择前的状态,做另外一个选择,即不选择当前的数字,往下递归,继续生成子集。

根据以上的伪代码,我们基本上就能解出这个题目👇

回溯算法题解-2
回溯算法题解-2

代码点这里☑️


题目是做不完的,做完这些题目后,希望你能找出回溯算法的规律,能对它有更加深入的理解~,接下来准备了些题集,希望对你们有帮助~

进阶题目汇总

以下是我在网上看到一套不错的回溯算法题集,如果你还在刻意找的话,可以看看这里。

类型 题目链接
子集,组合 子集子集 II组合组合总和组合总和 II
全排列 全排列全排列 II字符串的全排列字母大小写全排列
搜索 解数独单词搜索N皇后分割回文串二进制手表

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话:

  1. 点赞支持下吧,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
  2. 关注公众号前端UpUp,联系作者,我们一起学习一起进步。
  3. 觉得不错的话,也可以阅读TianTian近期梳理的文章(感谢掘友的鼓励与支持🌹🌹🌹):

本文使用 mdnice 排版