回溯算法

725 阅读6分钟

简介

回溯算法是啥?回溯算法实际上就是一个N叉树的前序遍历加上后序遍历而已,而且回溯算法是有相应的模板套路的,一旦掌握,就能很快解决相关问题。先看回溯算法的模板


“树”的遍历框架虽然简单,但是算法见了多后,你都会发现它们有一个共同点,
就是解空间其实就是一个N叉树,很多算法的解题过程都离不开抽象成一个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对回溯算法的学习总结,想学习更多的算法内容请关注原作者。