约 373 个字 12 行代码 预计阅读时间 2 分钟

Chap 6 | “Backtracking”

章节启示录

要清明放假啦，本章偷个懒吧……本章的内容主要是一种思想，其实也是比较简单的思想，就是暴力枚举，但是中间我们需要通过剪枝来加快遍历的速度。

结构

一般回溯算法是一个递归的函数，具有终止条件和递归条件，通常会符合下面的结构：

void BackTracing(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        BackTracking(下一个参数); 
        撤销处理;
        BackTracking(下一个参数); 
    }
}

应用

1.Tic-tac-toe（井字棋）

使用评估函数来量化职位的“好坏”。 例如：

\[\large f(P)=W_{Computer}-W_{Human}\]

• W 是位置 P 的潜在获胜次数。
• 圆圈为Human下的，叉叉为Computer下的。

e.g:

注意到：
这里圆圈只有4种win的方式，第一行、第一列、第三行、第三列。而叉叉有6种win的方式，第一列、第三列、第二行、第三行以及两条对角线。
\(f(P)=W_{Computer}-W_{Human}=6-4=2\)

2.α-β pruning（α-β剪枝）

• α剪枝：
  max-min形式，因为DFS是先搜左孩子，所以剪枝只会剪右孩子。若右孩子的父亲比叔叔小（40≤44），那么它的父亲不会被选中，然后黑色区域被剪枝。

• β剪枝：
  min-max形式，因为DFS是先搜左孩子，所以剪枝只会剪右孩子。若右孩子的父亲比叔叔大（68≥44），那么它的父亲不会被选中，然后黑色区域被剪枝。

复习时的一些补充

• It is guaranteed that an exhaustive search can always find the solution in finite time. F（考虑无解的情况）

Comments