计算机五大算法之四，回溯算法

一、基本思想和策略

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标，但当搜索到某一步时，发现原来选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的算法为回溯法，而满足回溯条件某个状态的点称为'回溯点'。

基本思想：回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。搜索至解空间树任一点时，先判断该点是否包含问题的解，如果肯定不包含(剪枝过程)，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先策略搜索。

回溯法就是对隐式图的深度优先搜索算法，

为了避免生成那些不可能产生最优解的问题状态，要不断的利用限界函数，来剪枝那些实际上不可能产生最优解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。(回溯法=穷举+剪枝)

二、回溯法一般步骤

1) 针对所给问题，定义问题的解空间

2) 确定易搜索的解空间结构

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

两个常用的剪枝函数：

1) 约束函数：在扩展结点中剪去不满足约束的子树

2) 限界函数：剪去得不到最优解的子树

三、算法特点总结

回溯法一个显著特征是在搜索过程中动态产生问题的解空间，在任何时间，算法只保存从根结点到当前扩展结点的路径。

四、实际场景

八皇后问题、全排列、0-1 背包、正则表达式匹配等。

8皇后问题