回溯算法框架

从整体到细节,自顶向下,从抽象到具体的框架思维是通用的,不只是学习数据结构和算法,学习其他任何知识都是高效的。

# 回溯算法的要素

回溯算法跟动态规划算法有些类似,动态规划里强调的是状态选择base case,而回溯法里强调的是路径选择列表结束条件

解决一个回溯问题,其实就是一个决策树的遍历过程,只需考虑以下三个问题:

  • 路径:也就是已经做出的选择
  • 选择列表:即当下可以做的选择
  • 结束条件:到达决策树底层,无法再做选择的条件

# 回溯算法框架

result = []
def backtrace(选择列表, 路径):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrace(选择列表,路径)
        撤销选择
1
2
3
4
5
6
7
8
9
10

其核心就是 for 循环里的递归,在递归前做选择,递归后撤销选择。

# 应用例子

全排列、八皇后问题都是很经典的回溯问题,此外,当遇到二维数组、网格移动等问题也可以考虑使用回溯法。