简介
回溯算法是啥?回溯算法实际上就是一个N叉树的前序遍历加上后序遍历而已,而且回溯算法是有相应的模板套路的,一旦掌握,就能很快解决相关问题。先看回溯算法的模板
算法的整体框架
到这里,我们只需要记住回溯法就是N叉树的遍历即可,这个N代表当前可做选择(choices)的总数,同时,在前序遍历做出选择,choose 过程;然后递归,在后序遍历删除选择,unchoose过程 (也叫恢复现场),伪代码模板如下
"""choiceList:当前可以进行的选择列表
track:可以理解为决策路径,即已经做出一系列选择
answer:用来储存我们的符合条件决策路径
"""
def backtrack(choiceList, track, answer):
if track is OK:
answer.add(track)
else:
for choice in choiceList:
# choose:选择一个 choice 加入 track
backtrack(choices, track, answer)
# unchoose:从 track 中撤销上面的选择
模板很简单吧,是不是就是一个 N 叉树的遍历?你可以理解为,回溯算法相当于一个决策过程,递归地遍历一棵决策树,穷举所有的决策,同时把符合条件的决策挑出来。
举个例子,假如你要吃饭,但是去哪里吃,然后具体吃什么呢?这是个决策问题,而且不太容易,因为选择实在太多了,如下图。
作为人类,可以很直观的知道自己要干嘛,比如在A,要去F吃饭,很容易直观就知道A-C-F这样的路径,但是计算机呢?计算机要穷举所有可能性,挑出满足条件的路径,才能达到目的。
如何让计算机正确地穷举并比较所有决策路径,就需要回溯算法的设计技巧了,回溯算法的核心就在于如何设计 choose 和 unchoose 部分的逻辑。
下面我们通过讲解两个经典的回溯法问题。全排列问题(permutation)和 N 皇后问题来详述回溯算法的原理和技巧
一、全排列问题
leetcode 46.全排列
这个问题我们高中就做过,我们的思路是,先把第一个数固定为 1,然后全排列 2,3;再把第一个数固定为 2,全排列 1,3;再把第一个数固定为 3,全排列 1,2 。
这其实就是个决策的过程。转化成决策树表示一下:
可以发现每向下走一层就是在「选择列表」中挑一个「选择」加入「决策路径」,然后把这个选择从「选择列表」中删除(以免之后重复选择);当一个决策分支探索完成后,我们就要向上回溯,要把该分支的「选择」从「决策列表」中取出,然后把这个「选择」重新加入「选择列表」(供其他的决策分支使用)。
以上,就是模板中 choose 和 unchoose 的过程,choose 过程是向下探索,进行一选择;unchoose 过程是向上回溯,撤销刚才的选择。
这下应该十分清楚了,现在我们可以针对全排列问题来具体化一下回溯算法模板:
"""
choiceList:【选择列表】,当前可以进行选择的列表
track:【决策路径】,即已经做出一系列选择
answer:用来储存完成的全排列
"""
function backtrack(choiceList, track, answer):
if choiceList is empty:
answer.add(track)
else:
for choice in choiceList:
# choose 过程:
# 把choose 加入track
# 把choose 移出 choiceList
backtrack(choices, track, answer)
# unchoose 过程:
# 把choose 移出 track
# 把choose 重新加入 choiceList
代码
N皇后问题
leetcode 51.N皇后问题
直接看代码,套上面模板
代码
「决策路径」:就是棋盘 board,每一步决策即 board 的每一行。row 变量记录着当前决策路径走到哪一步了
「选择列表」:对于给定的一行(即决策的每一步),每一列都可能放置一个 ‘Q’,这就是所有的选择。代码中的 for 循环就在穷举「选择列表」判断是否可以放置皇后。
N 皇后问题不过如此,只要掌握了回溯算法模板,学会了把决策问题抽象成树的遍历,就能看出这种问题只不过是暴力试答案而已。其实再想想,解数独问题是不是也和 N 皇后问题差不多呢?
回溯算法的复杂度是极其高的,甚至比指数级还高,因为树形结构注定了复杂度爆炸的结局。
你可能会问,动态规划不是可以专门优化树形结构的时间复杂度的吗?不是能降维打击吗?
但这里无法做任何优化。再强调一遍,计算机做事的策略就是穷举。动态规划的一大特征:重叠子问题,可以让那类问题“聪明地穷举”。但回顾一下回溯算法的决策树,根本不存在重叠子问题,优化无从谈起。
就好比让你找出数组中最大的元素,你起码得把数组全部遍历一遍吧,还能再优化吗?不可能的。
最后总结
无论如何,能看到这里,给你鼓掌。现在的你,掌握了回溯算法模板,学会了树形搜索的抽象思维,递归功力大涨,解决了两道难度较大的经典问题,并且再次深入体会了计算机做事的逻辑。
「选择列表」+「决策路径」结合树的遍历,简单的组合却能解决一大类问题,这就是算法框架的力量。让我们最后重温一下算法的魅力吧!
def backtrack(choiceList, track, answer):
if track is OK:
answer.add(track)
else:
for choice in choiceList:
if choice is not OK: continue
# choose 过程
backtrack(choiceList, track, answer)
# unchoose 过程
PS:本文参考公用号labuladong对回溯算法的学习总结,想学习更多的算法内容请关注原作者。