state：状态#

状态 $s\in S$ 描述系统当前与后续决策有关的情形。

状态应保留完成任务所必需的信息，同时删去无关细节。不同问题中的状态可以是：

• 路径规划中的当前位置；
• 八数码问题中的棋盘布局；
• 博弈问题中的棋盘局面与当前行动方。

其中：

• $S$：状态空间，所有可能状态的集合；
• $s_0$：初始状态；
• 目标状态：满足任务要求的状态。

action：动作#

动作表示在当前状态下可执行的操作。

动作通常按一次决策来离散地描述。例如“从舟山乘大巴到杭州”可以看作一个动作。

state transition：状态转移#

状态转移函数描述执行动作后系统到达哪里：

动作回答“做什么”，状态转移回答“做完后到哪里”。

path：路径#

从初始状态出发，依次执行动作

并得到状态序列

这一状态序列及其对应动作序列构成一条路径。

cost：路径代价#

单步代价记为

从初始状态到结点 $n=s_k$ 的累计路径代价为

代价可以表示：

• 行驶时间；
• 路程；
• 票价；
• 能量消耗；
• 风险；
• 多个指标的加权结果。

WARNING

路径步数与路径代价必须区分。

路径更短，不代表总代价更小。例如一条路经过的路口少，却可能严重拥堵；另一条路绕得更远，却可能更快。

goal test：目标测试#

目标测试函数判断当前状态是否满足任务目标：

目标测试只回答“是否到达目标”。

它不能单独判断当前路径是否为最优路径。算法第一次找到目标后是否可以立即停止，取决于具体搜索策略及其最优性保证。

搜索树#

搜索过程可以看作一棵搜索树的逐步构建：

• 根结点对应初始状态；
• 每次扩展一个结点，就生成其后继结点；
• 每条根到结点的路径，对应一种动作序列；
• 当某个结点通过目标测试时，找到一条解路径。

配图占位：插入第 3 章 PPT 第 9 页“搜索过程可视为搜索树的构建”。重点保留同一状态 A 通过不同路径重复出现的示意图。

状态与结点的区别#

• 状态：只描述系统当前情形；
• 结点：搜索树中的记录单元，还包含到达该状态的路径、父结点与累计代价等信息。

因此，不同结点可以对应同一个状态。

例如下列三条路径都回到了状态 A：

搜索树中会出现三个标记为 A 的结点，因为它们记录了三条不同路径。

搜索图#

若将所有相同状态合并，并记录某个状态是否已经访问过，就得到搜索图的观点。

• 树搜索：按路径展开，同一状态可能被多次生成；
• 图搜索：检查重复状态，避免无意义的反复访问。

图搜索通常需要维护已访问状态，并在发现同一状态的更优路径时决定是否更新。

OPEN / frontier：边缘集合、开表#

OPEN 保存：

已经生成、尚未扩展、以后仍可能被选中的全部候选结点。

它不只包含“刚扩展结点的孩子”，还包含之前保留下来的其他候选结点。

CLOSED / explored：已扩展集合、闭表#

CLOSED 保存已经被取出并完成扩展的结点或状态，用于：

• 记录搜索历史；
• 检测环路；
• 处理重复状态。

expand：结点扩展#

扩展结点 $n$ 通常包括：

1. 从 OPEN 中取出 $n$；
2. 对 $n$ 进行目标测试；
3. 若尚未到达目标，生成 $n$ 的合法后继；
4. 按规则将后继加入 OPEN；
5. 将 $n$ 记入 CLOSED。

统一搜索框架可以写成：

1
OPEN ← {初始结点}
2
CLOSED ← ∅
3

4
while OPEN 非空:
5
    n ← 从 OPEN 中按某种规则选一个结点
6
    从 OPEN 中删除 n
7

8
    if Goal(n):
9
        return 从初始结点到 n 的路径
10

11
    将 n 加入 CLOSED
12
    生成 n 的合法后继
13
    将需要保留的后继加入 OPEN
14

15
return 搜索失败

不同算法最主要的区别集中在两处：

• pick_from(OPEN)：下一步从 OPEN 中选谁；
• successor_nodes(n)：哪些后继可以进入 OPEN，哪些需要剪枝。

老师强调的 OPEN 例子#

设初始时：

扩展结点 1，生成结点 2、3、4：

接着取出结点 2，并生成结点 5、6。此时：

其中 3、4 仍在 OPEN 中，并不会因为算法开始探索 2 的后继就消失。

WARNING

OPEN 是当前全部候选结点的集合。

做搜索过程题时，最常见的错误是只保留刚生成的孩子，漏掉先前尚未扩展的兄弟结点。

环路剪枝#

若路径出现

算法可能永远在 A 与 B 之间循环。

只要发现新状态已经出现在当前路径的祖先中，就可以停止扩展该分支。

劣势分支剪枝#

若某个分支即使继续展开，也不可能优于当前已有结果，则可以直接剪去。

例如从舟山去杭州时，“舟山 $\rightarrow$ 北京 $\rightarrow$ 杭州”通常明显劣于更直接的路线，可以在有可靠判据时放弃。

后面的 Alpha-Beta 剪枝就是这种思想在博弈树中的严格实现。

配图占位：插入第 3 章 PPT 第 12 页“搜索树构建示意”。保留实线结点、虚线边缘结点及环路剪枝示意。

completeness：完备性#

当问题存在解时，算法是否保证最终找到一个解。

完备性只保证“能找到”，不保证“找到的是最好解”。

optimality：最优性#

算法找到的第一个解是否一定为最优解。

最优的具体含义由代价函数决定，例如：

• 路程最短；
• 时间最少；
• 总费用最低。

time complexity：时间复杂度#

通常用算法扩展的结点数量衡量。

space complexity：空间复杂度#

通常用算法运行过程中同时保存的结点数量衡量。

搜索复杂度常与以下量有关：

若每个结点平均有 $b$ 个孩子，搜索到深度 $d$，结点数约为

当 $b>1$ 时，结点数随深度呈指数增长，这就是 组合爆炸 的根源。

depth-first search：深度优先搜索#

• 沿当前分支持续向深处探索；
• 走不通时回溯到最近的分叉点；
• 类似走迷宫时始终优先走最右边的一条路，走到尽头再退回。

优点：占用内存较少。

局限：可能沿错误分支走得很深，也可能陷入环路；若没有深度限制和去重机制，不一定完备。

breadth-first search：广度优先搜索#

• 先扩展当前层全部结点；
• 再进入下一层；
• 搜索过程按“由近到远”逐层推进。

优点：在每步代价相同时，第一个找到的解是最少步数解。

局限：需要同时保存大量边缘结点，空间消耗较大。

本章课堂重点不在两者的具体实现，理解它们与启发式搜索的区别即可：

无信息搜索按固定结构展开；启发式搜索使用额外信息决定优先扩展方向。

informed / heuristic search#

利用与问题相关的额外信息指导搜索，称为：

• 有信息搜索（informed search）；
• 启发式搜索（heuristic search）。

例如，在地图中用“当前城市到目标城市的直线距离”判断哪个城市更有希望。

heuristic function：启发函数#

启发函数 $h(n)$ 估计：

从当前结点 $n$ 到目标结点还需要付出多少代价。

记真实最小剩余代价为 $h^*(n)$，则

地图搜索中常用直线距离或按最大速度估计的最短时间作为 $h(n)$。

path-cost function：路径代价函数#

evaluation function：评价函数#

评价函数 $f(n)$ 决定：

OPEN 中哪个结点应当优先扩展。

通常 $f(n)$ 越小，优先级越高。

WARNING

启发函数与评价函数不是同一个概念。

• $h(n)$ 负责估计“未来还要多少”；
• $f(n)$ 负责决定“下一个选谁”。

只有在贪婪最佳优先搜索中，二者恰好相等：$f(n)=h(n)$。

基本流程#

1. 将初始结点加入 OPEN；
2. 从 OPEN 中取出 $h(n)$ 最小的结点；
3. 若通过目标测试，返回路径；
4. 否则扩展该结点，把合法后继加入 OPEN；
5. 重复以上过程。

例：从城市 A 到城市 K#

PPT 中给出城市 A 到 K 的交通图，边上的数字为实际行驶代价，各城市到 K 的直线距离作为启发函数：

配图占位：插入第 3 章 PPT 第 14 页右侧“城市 A 到 K 的交通网络图”与启发函数表。

搜索过程：

1. 扩展 A，生成 B、D、E：

   $$h(B)=10,\quad h(D)=12,\quad h(E)=7$$

   选择 E。

2. 扩展 E，生成 H、G、I：

   $$h(H)=3,\quad h(G)=5,\quad h(I)=6$$

   OPEN 中还保留 B、D。当前最小值为 $h(H)=3$，选择 H。

3. 扩展 H，生成 G、J。因为

   $$h(J)=3$$

   贪婪策略继续选择 J。

4. 扩展 J，生成 K，且

   $$h(K)=0$$

   找到路径

   $$A\rightarrow E\rightarrow H\rightarrow J\rightarrow K$$

这条路径能够到达目标，但总代价为

真正更短的路径为

总代价为

配图占位：插入第 3 章 PPT 第 14—15 页“贪婪最佳优先搜索过程”。建议保留各阶段 OPEN 表和结点下方的 $h(n)$。

为什么会失败#

贪婪最佳优先搜索只关注

没有考虑已经付出的代价

虽然 J 离目标的估计距离很小，$h(J)=3$，但到达 J 时已经付出

继续沿 J 前进不可能得到总代价 14 的最短路径。

性质#

• 在有限状态空间中，若进行环路与重复状态检测，通常能够找到一个解；
• 不保证最优性；
• 最坏时间复杂度和空间复杂度都可能达到

贪婪搜索的优势是直观、常常较快，适合先尽快找到一个可行解；缺点是容易被局部上“看起来更近”的方向误导。

与其他算法的关系#

• 若只看 $h(n)$，得到贪婪最佳优先搜索；
• 若令 $h(n)=0$，A* 退化为只按 $g(n)$ 排序的一致代价搜索；
• 若 $h(n)=h^*(n)$，即准确知道真实剩余最小代价，搜索会高度集中在最优路径附近。

例：城市 A 到 K#

A* 图搜索的更新规则#

对后继结点 $n'$，先计算新的候选路径代价

若 $n'$ 尚未出现，或新路径更优，即

则更新：

并更新其父结点。必要时应把已经进入 CLOSED 的状态重新放回 OPEN。

admissible：可容性#

若对任意结点 $n$ 有

且目标结点满足

则称 $h(n)$ 可容。

直观含义：

启发函数可以低估真实剩余代价，但不能高估。

例如，两地之间的直线距离通常不大于真实道路距离，因此可以作为可容的距离启发。

consistent：一致性#

若对任意结点 $n$、动作 $a$ 及后继结点 $n'$ 有

则称 $h(n)$ 一致。

这相当于三角不等式：

从 $n$ 直接估计到目标的代价，不应超过“先走一步到 $n'$ 的真实代价 + 从 $n'$ 到目标的估计代价”。

一致性蕴含可容性#

设从 $n_1$ 到目标 K 的最优路径为

由一致性：

继续展开：

因为

所以

因此：

一致性要求更严格；可容性不一定推出一致性。

完备性#

若满足以下条件，A* 是完备的：

1. 每个结点的分支数有限；

2. 单步代价存在正下界，即存在 $\varepsilon>0$，使

   $$c(n,a,n')\ge\varepsilon$$

3. 启发函数有下界，通常令 $h(n)\ge0$。

这些条件排除了“单层无限分叉”和“通过无穷多次几乎零代价动作一直拖延”等病态情况。

最优性#

课程中的核心结论是：

若启发函数可容，A* 找到的第一个目标结点对应最优路径。

证明思路：

设最优路径总代价为 $C^*$。在最优目标被找到前，最优路径上总有某个边缘结点 $n$ 留在 OPEN 中。由于可容：

任何非最优目标 G 都满足

A* 总是先扩展最小的 $f$，所以非最优目标不可能抢在最优路径的边缘结点之前被取出。

NOTE

严格区分树搜索与图搜索：

• 树搜索版 A*：可容性足以保证最优性；
• 图搜索版 A*：通常要求启发函数一致，或允许在发现更小的 $g$ 时重新打开 CLOSED 中的结点。

一致性保证沿路径的 $f$ 值非递减，使结点第一次从 OPEN 中取出时，其最优路径代价已经稳定。

复杂度#

即使使用启发函数，A* 在最坏情况下的时间与空间复杂度仍可能是指数级。

• $h(n)$ 越接近 $h^*(n)$，扩展结点通常越少；
• 若 $h(n)\approx0$，A* 接近一致代价搜索，启发作用很弱；
• A* 的主要实际瓶颈往往是 OPEN 占用的内存。

递推公式#

设 $V(s)$ 为双方都采用最优策略时，状态 $s$ 对 MAX 的价值：

若根结点由 MAX 行动，则最优动作是

Minimax 的计算方向为：

1. 先计算叶结点或终局结点的效用；
2. MIN 层向上返回孩子中的最小值；
3. MAX 层向上返回孩子中的最大值；
4. 一直回传到根结点。

例：两层博弈树#

根结点 A 为 MAX，三个孩子 B、C、D 为 MIN。叶结点效用分别为：

MIN 层先取最小值：

根结点 A 为 MAX：

因此 MAX 选择通向 B 的动作，并能在对手理性行动时保证得到 3。

配图占位：插入第 3 章 PPT 第 27—29 页的 Minimax 搜索树，建议保留 MAX / MIN 层标记与叶结点得分。

伪代码#

1
MinimaxValue(s):
2
    if Terminal(s):
3
        return U(s)
4

5
    if Player(s) == MAX:
6
        v ← -∞
7
        for a in Actions(s):
8
            v ← max(v, MinimaxValue(Result(s,a)))
9
        return v
10

11
    if Player(s) == MIN:
12
        v ← +∞
13
        for a in Actions(s):
14
            v ← min(v, MinimaxValue(Result(s,a)))
15
        return v

性质与复杂度#

若博弈树有限，并假设对手始终理性地采取最优策略，Minimax 能得到最优决策。

设平均分支因子为 $b$，最大搜索深度为 $m$：

按深度优先方式实现时：

Minimax 的主要问题是需要搜索大量结点，博弈树稍大就会发生组合爆炸。

$\alpha$ 与 $\beta$ 的含义#

• $\alpha$：沿当前搜索路径，MAX 已经能够保证获得的最好下界；
• $\beta$：沿当前搜索路径，MIN 目前允许 MAX 获得的最好上界。

初始时：

在 MAX 结点，孩子返回价值 $v$ 后：

在 MIN 结点，孩子返回价值 $v$ 后：

若出现

则当前结点剩余尚未访问的孩子可以剪去。

为什么可以剪枝#

• MAX 已经有一个至少为 $\alpha$ 的选择；
• MIN 一旦发现当前分支最多只能返回 $\beta\le\alpha$；
• MAX 不会放弃已有的 $\alpha$ 去选择一个不超过它的分支；
• 所以继续计算该分支的剩余孩子不会改变根结点决策。

例：剪去 $x,y$#

考虑：

先搜索第一棵子树：

因此根结点 MAX 已经有

再搜索第二棵 MIN 子树，看到第一个叶结点为 2：

无论 $x,y$ 是多少，该子树返回值都不会超过 2，而 MAX 已经能得到 3。因此 $x,y$ 对根结点选择没有影响，可以直接剪枝。

最后第三棵子树返回：

根结点仍为：

配图占位：插入第 3 章 PPT 第 29 页“alpha-beta 剪枝算法”，保留 $\min(2,x,y)$ 与被剪去的两个分支。

Alpha-Beta 伪代码#

1
AlphaBeta(s, α, β):
2
    if Terminal(s):
3
        return U(s)
4

5
    if Player(s) == MAX:
6
        v ← -∞
7
        for a in Actions(s):
8
            v ← max(v, AlphaBeta(Result(s,a), α, β))
9
            α ← max(α, v)
10
            if α ≥ β:
11
                break
12
        return v
13

14
    if Player(s) == MIN:
15
        v ← +∞
16
        for a in Actions(s):
17
            v ← min(v, AlphaBeta(Result(s,a), α, β))
18
            β ← min(β, v)
19
            if α ≥ β:
20
                break
21
        return v

性质与复杂度#

• 最终结果与完整 Minimax 相同；

• 只减少搜索结点，不改变理论最优决策；

• 最坏时间复杂度仍为

  $$O(b^m)$$

• 若优先搜索最有希望的动作，理想情况下可接近

  $$O(b^{m/2})$$

这说明剪枝效果高度依赖结点访问顺序：越早找到好动作，$\alpha$、$\beta$ 越快收紧，越容易剪掉后续分支。

配图占位：插入第 3 章 PPT 第 33 页“完整搜索树及 Alpha-Beta 剪枝过程”。建议保留每个结点的 $[\alpha,\beta]$ 区间和叉号。

抛硬币#

理论上公平硬币正反面概率各为 $1/2$。若只抛 10 次，频率可能偏离很大；若抛 1000 次、10000 次，正面频率通常会逐步接近 $1/2$。

掷骰子#

对均匀六面骰子，大量重复试验后，每一面出现的频率趋近于 $1/6$。

其理论基础是大数定律：样本数量足够大时，经验统计量会逐步接近真实期望。

蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）把这种随机采样思想用于搜索树：

• 不完全展开整棵树；
• 对部分分支进行多次模拟；
• 用模拟结果估计结点价值；
• 把更多计算资源分配给更有希望的分支。

经验平均奖励#

设到第 $t$ 轮为止，第 $i$ 个动作被选择 $N_i(t)$ 次，其经验平均奖励为

regret：悔值函数#

设最优动作的期望奖励为

经过 $T$ 次操作，悔值可写为

它表示：

始终选择最优动作本来能获得的期望总收益，与智能体实际收益之间的差距。

算法的目标是让

尽可能小。

exploitation：利用#

选择当前看来收益最高的动作，充分使用已经获得的经验。

exploration：探索#

尝试访问次数较少、真实潜力尚不明确的动作，以获得新信息。

只利用：可能长期困在次优动作。

只探索：无法充分利用已有经验，浪费大量机会。

因此，多臂赌博机和 MCTS 的关键都是：

局限#

1. $\varepsilon$ 应取多大缺少统一答案；
2. 探索时完全随机，没有利用“不确定性大小”；
3. 一个已经探索很多次且表现很差的动作，仍可能被随机选中；
4. 访问极少、最值得获取信息的动作，没有得到更高优先级。

因此需要更有方向的探索策略。

两部分的含义#

Hoeffding 不等式带来的上界#

若奖励位于 $[0,1]$，则经验均值满足 Hoeffding 不等式：

令右侧随时间快速减小，可以得到

因此

可以作为奖励均值的高概率上界。

PPT 给出的理论结论是，UCB1 的期望悔值随测试次数只按对数增长，其量级可写为

其中

表示最优动作与次优动作之间的最小均值差距。

1. selection：选择#

从根结点出发，在已经建立的搜索树中反复选择 UCT 值最大的孩子，直到：

• 到达终局结点；或
• 到达尚未完全展开的结点。

2. expansion：扩展#

若当前结点不是终局，并且仍有合法动作未生成，则选择一个未尝试动作，生成一个新子结点。

扩展的含义是：在当前搜索树边界上打开一个新分支。

3. simulation / rollout：模拟#

从新结点出发，使用较简单的策略继续行动，直到：

• 到达终局；或
• 到达预设截断深度，再用估值函数评价。

基础 MCTS 常使用随机策略。

若终局收益记为 $z$，二人零和博弈中可取：

分别表示胜、平、负。

4. backpropagation：回传#

将模拟得到的 $z$ 沿本轮访问路径向上回传，更新：

NOTE

这里的“反向传播”指把模拟结果沿搜索路径回传并更新统计量，与神经网络训练中的梯度反向传播含义不同。

配图占位：插入第 3 章 PPT 第 45 页“MCTS 的选择—扩展—模拟—反向传播四阶段示意图”。

选择#

父结点访问次数为 2。按 PPT 使用的 UCB 形式：

因此选择左孩子 L。

扩展#

L 仍有未扩展动作，随机生成新孩子 C：

其他尚未扩展的孩子可将 UCB 视为 $+\infty$，确保后续有机会被探索。

模拟#

从 C 出发采用随机策略模拟到终局，得到终局得分：

回传#

PPT 为了让所有层都能统一使用“选择最大 UCB”的规则，采用交替符号的记分约定：

• MIN 层结点累计收益加 $z$；
• MAX 层结点累计收益减 $z$。

于是更新为：

一次迭代结束后，所有经过结点的访问次数和累计收益都被更新，下一轮再重新计算 UCT。

配图占位：插入第 3 章 PPT 第 46—47 页“蒙特卡洛树搜索一次迭代”。需保留四幅子图 (a)—(d) 与 $-15/2,10/1,5/1,-3/1,13/2,-18/3$。

TIP

收益视角有多种等价实现方式：

1. 始终从根玩家视角记录同一个 $z$；
2. 按当前行动方视角记录，并在相邻层之间翻转符号；
3. 像课程 PPT 一样，通过给不同层累计相反符号，使各层都能统一做 argmax。

关键是全程使用同一种约定。

MCTS 的特点#

1. 按预算工作：计算时间越多，采样越多，统计通常越稳定；
2. 不要求完整展开搜索树；
3. 适合分支因子很大的问题；
4. 基础版不强依赖精确启发函数；
5. 有限预算下通常得到近似最优解；
6. 可以与策略模型、价值模型和领域知识结合。

与 Minimax 的区别#

可以用一句话概括：

Minimax 尽量把树“算清楚”；MCTS 通过不断试探把树“估准一些”。

组合爆炸#

PPT 以国际象棋中的香农数说明搜索规模：

• 第一次移动约有 20 种可能；
• 两步组合约有 400 种；
• 搜索到更深层后，可能局面迅速达到上亿；
• 完整博弈树规模可估计到约 $10^{120}$ 量级。

因此不可能把所有可能局面全部展开。

应对思路主要有：

• 剪枝：证明某些分支不可能影响结果，直接放弃，如 Alpha-Beta；
• 采样：只模拟部分分支，用统计结果近似估值，如 MCTS。

horizon problem：地平线问题#

若搜索只能看到有限深度，某个动作的真正后果可能发生在搜索深度之外。

算法在当前“地平线”以内看起来判断合理，却可能忽略更远处的关键变化。

PPT 用 AlphaGo 与李世石第四局的关键落子说明这一现象。这里应把它理解为有限搜索深度和估值能力可能遗漏远期后果的概念示例。

配图占位：插入第 3 章 PPT 第 50 页“组合爆炸与地平线问题”。

1. 状态与结点#

• 状态只描述当前情形；
• 结点还记录到达路径；
• 多个结点可以对应同一个状态。

2. OPEN 与当前结点的孩子#

OPEN 包含全部尚未扩展候选结点，不只包含刚生成的孩子。

3. 目标测试与最优性#

到达目标只说明找到一个解；能否立即停止，要看算法是否保证第一个解最优。

4. $g(n)$、$h(n)$、$f(n)$#

• $g(n)$：已经付出的真实代价；
• $h(n)$：未来剩余代价的估计；
• $f(n)$：决定下一个扩展谁。

5. 可容性与一致性#

一致性更强。

6. Minimax 与 Alpha-Beta#

Alpha-Beta 只减少搜索量，最终结果与 Minimax 相同。

7. 贪心与 $\varepsilon$-贪心#

• 贪心：只利用；
• $\varepsilon$-贪心：大部分利用，小概率随机探索。

8. UCB 的两个部分#

9. MCTS 的回传#

更新的是访问次数、累计收益和平均收益；若使用当前玩家视角，要注意相邻层符号翻转。