一些高级搜索优化技巧

A*

我们考虑bfs+优先队列优化寻找最短路的过程。

我们有三类点（本质是状态）：

• 当前已经确定点（1）
• 队列中的点（2）
• 还未探索过的点（3）

初始时起始点在1类点，终止点为3类点。当终止点变成1类点时，我们就可以直接结束。

我们考虑会优先把哪个2类点丢到1类点中：假设当前到某个2类点的最优是（已走路径长度） $f(i)$，我们会选择**$f(i)$ 最小的点**进行下一步。

以上是我们传统的做法，接下来介绍 A*

我们考虑我们增加一个预测函数 $g(i)$，代表从 $i$ 号点到终点预估需要的代价是 $g(i)$，而实际上是 $h(i)$。我们强制要求我们构造的 $g(i)$ 必须满足以下条件：

$$0 \le g(i)\le h(i)$$

此时我们在2类点转1类点时，我们优先选 $f(i)+g(i)$ 最小的点

以上就是 A*

对于 $g(i)$：

• 我们必须满足其小于 $h(i)$，那样子结果才准确（绝对乐观）。否则我们可能会因为其太大而错过这条路。而其他比他还小的错误预估，我们走着走着就发现估错了，现在这里更优了。

• $g(i)$ 越接近 $h(i)$，我们的速度越快。

  • 当 $g(i)=h(i)$，我们相当于开了全局视角。我们直接就可以走到终点了

  • 当 $g(i)=0$，就退化到我们最开始的情况了

比如在类似华容道问题时，我们的 $g(i)$ 可以是：

1. 当前不在自己位置上的棋子数目

2. 当前不在自己位置上的棋子数组离自己目标位置的曼哈顿距离之和

显然，我们估算的这两者均为下界，满足 $g(i)\le h(i)$。

而第二种办法 $g(i)$ 更大，因此结果更优。

IDA*

IDA* 的原理和 A* 相同，只不过 A* 用在广搜上。

但是传统的广搜我们也知道，会有状态数的爆炸。因此我们引入的办法叫做迭代加深搜索。

我们现在不过是在迭代加深搜索里，运用到 A* 的估值方法。

这种估值方法可以让我们迅速剪枝。（其实在很多题目中，我们预判未来的最少步数就已经用到了这种思想）

Dancing Links

我们考虑一个朴素问题：

一个棋盘，每个格子为0或1。

我们要选择其中一些行，使选完后每一列的棋子数目恰好为1

1的数目比较少

如果在常规棋盘上搜索，复杂度可能很大。但由于1的数目比较少，所以我们可以对棋盘进行优化：

这样子下来，我们整个棋盘就变成了用链表维护的Dancing Link，非常有利于我们搜索了。

我们很多问题都可以转化为这个棋盘问题。

• 每一列，就是题目的一个限制
• 每一行，就是我们的一种选择

以9x9的数独为例：

• 我们总共有9 x 3 x 9列，每一列代表数独中的某一行/列/放个的数字 $a$
• 我们有9 x 9 x 9行，分别代表我们选择在数独中 $(x,y)$ 的位置放入 $a$，那样子我们就在我们的转化棋盘中的第 $x$ 行、第 $y$ 列、相应方格的数字 $a$ 处放入1（即共三个1）
• 我们的目标是选择一些行（放置），使剩余每列恰有1个1

这样子就转化为DLX问题了

Alpha-Beta 剪枝

Alpha-Beta剪枝运用在Minimax问题中。

Minimax问题是指，在双人博弈问题中，一方（A）希望令分数最大，另一方（B）希望令分数最小。

这种问题我们的搜索树是按层分的，奇偶交替。

我们在搜索过程中，维护两个值 $\alpha$ 与 $\beta$。分别代表在我们之前搜过的情况中（通过回溯来传），A可以让分数最大为 $\alpha$，B可以让分数最小为 $\beta$

剪枝的判定条件为：

• 如果某一时刻 $\beta\ge \alpha$，我们就没有必要再搜索当前节点的其他分支了（直接return）

因为如果走到了这个节点，对方有一条路往下走，而这条路必然导致我的分数劣于我之前的那个分数，那我肯定不会走到这个节点。

可以用伪代码来解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function 搜索(节点, 深度, α, β, 是不是我走):
    如果到底了: 返回 局面评分

    如果 是我走 (MAX层):
        遍历每一个走法:
            分数 = 搜索(子节点, 深度-1, α, β, False) // 轮到对手
            α = max(α, 分数)  // 我要最大的，更新我的保底
            如果 α >= β: 
                剪枝! 别遍历了，直接跳出循环
        返回 α

    如果 是对手走 (MIN层):
        遍历每一个走法:
            分数 = 搜索(子节点, 深度-1, α, β, True) // 轮到我
            β = min(β, 分数)  // 对手要最小的，更新对手的上限
            如果 α >= β: 
                剪枝! 别遍历了，直接跳出循环
        返回 β