算法笔记——回溯

算法笔记——回溯

回溯法实际上就是把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，如果遍历的过程中发现已不满足求解条件时，就“回溯”（即回退），尝试别的路径。

思想

回溯法从根结点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。当搜索至树中的任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界限，也就是判断该结点是否可能包含问题的可行解：

如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝； 否则，进入以该结点为根的子树，继续按照深度优先策略搜索并进行判断。 注意： 在算法运行时并不需要构造一棵真正的解空间树结构，只需要存储从根结点到当前结点的路径。

回溯算法需要设计合适的剪枝策略，尽量避免不必要的搜索。

常用的剪枝策略包括两大类：

约束函数剪枝：根据约束条件，状态空间图中的部分状态可能是不合法的。 因此，在状态空间图中以不合法状态为根的子树是不可能包含可行解的，故其子空间不需要搜索。 限界函数剪枝：这种策略一般应用于最优化问题。假设搜索算法当前访问的状态为𝑆，且存在一个判定函数：它能判定以𝑺为根的子树不可能包含最优解， 因此该子树可以剪除而无需搜索。 用约束函数在扩展结点处剪除不满足约束的子树，即剪除不可行解； 用限界函数剪去得不到问题解或最优解的子树。

所以，回溯算法 = 深度优先搜索 + 剪枝策略

这一部分参考回溯算法

模板

以八皇后为例

void search(int cur)
{
    if (cur == n) //递归边界，若走到这里，所有皇后必然不冲突
        tot++;
    else
    {
        for (int i = 0; i