回溯

组合枚举、棋盘路径、子集和、整数约束搜索都可以放进同一个框架:搜索树的节点是局部状态,边是一次选择。

四步

列出候选 → 做出选择 → 递归往下 → 撤销这次选择。最要紧的是恢复现场:同一个可变的状态对象被很多分支轮流使用。

def backtrack(path, candidates):
    if finished(path):
        record(path)
        return
    for x in candidates:
        if not valid(path, x):
            continue
        path.append(x)
        backtrack(path, next_candidates(path))
        path.pop()

剪枝要先证明

剪枝是断言「这个分支下面一定没有解」,所以必须先证明。例子见 子集和:全是非负数时「当前和已经超过目标」可以剪,有负数就不行。

和 BFS 的 visited 不一样

BFS 发现一个状态就永久标记,防止重复入队。回溯要枚举所有合法路径,同一个格子可以出现在不同的答案里,所以只禁止当前路径重复经过,返回时要取消占用。把两种 visited 混用会漏解。

什么时候变成动态规划

不同的路径走到同一个状态,而且从这个状态往后的选择完全一样,就可以把这个状态的结果缓存起来——这就是 动态规划。如果走过的历史会影响以后能怎么选,就得把那部分历史也编进状态里,不能随便合并。

分支方式完全由规则决定、不需要判断可不可行的递归,典型是汉诺塔:$n$ 个盘的步数 $T(n)=2T(n-1)+1$,$T(1)=1$,解得 $T(n)=2^n-1$。

用到它的地方

• 讲义 图的表示、BFS 与 DFS
• 知识库 动态规划
• 知识库 图的表示、BFS 与 DFS
• 知识库 子集和

核对

这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。