6-001-什么是回溯算法？

arctic_fox / 2023-05-03 / 原文

回溯算法

定义

回溯算法是一种搜索问题的解的方法，它可以找出所有可能的解，或者找出最优的解。

思想

回溯算法的思想是，从一个初始状态开始，每次尝试一个可能的选择，然后递归地继续搜索下一步。如果发现当前的选择不能达到目标或者不满足条件，就回退到上一步，换一个选择继续尝试。这种不断前进和后退的过程就叫做回溯。

模板

回溯算法可以用以下模板来实现：

void backtracking(参数) {
  if (终止条件) {
    存放结果;
    return;
  }
  for (选择 : 本层集合中元素) {
    处理节点;
    backtracking(路径, 选择列表); // 递归
    回溯, 撤销处理结果;
  }
}

其中：

参数表示传递给函数的变量，例如棋盘、皇后数量等；
终止条件表示搜索到了问题的解或者无法继续搜索；
存放结果表示把找到的解保存起来；
本层集合中元素表示当前可以做出的选择；
处理节点表示对当前状态做出一个选择；
路径表示已经做出的选择；
选择列表表示还可以做出的选择；
回溯表示撤销当前状态做出的选择。

优化

回溯算法是一种比较暴力的方法，它需要遍历所有可能的情况，所以效率不高。为了提高效率，可以在搜索过程中进行剪枝操作，也就是提前排除一些不符合要求或者没有希望的选择。

应用

回溯算法可以用来解决很多问题，例如组合、排列、切割、子集、棋盘等问题。只要能把问题转化成一个有限的解空间，并且能用树形结构来表示搜索过程，就可以用回溯算法来求解。

下面是一些回溯算法的例子：

问题	描述	解空间
八皇后	在3×3的棋盘上放三个皇后，使得它们不能互相攻击	所有可能的摆法
组合	从n个数中选出k个数的集合	所有可能的组合
组合总和	给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合