02 搜索探寻与问题求解

搜索：依据已有信息来寻找满足约束条件的待求解问题答案

无信息搜索
- 广度优先搜索
- 深度优先搜索
有信息搜索：启发式搜索
- 贪心最佳优先搜索
- A*搜索
对抗搜索：博弈搜索
- 最小最大搜索
- Alpha-Beta 剪枝搜索
- 蒙特卡洛树搜索

01 搜索算法基础

形式化描述

状态、动作、状态转移、路径/代价、目标测试

状态：对智能体和环境当前情形的描述
- 在最短路径问题中，每个城市即为一个状态
- 刚开始所在状态(图中为 A )称为初始状态
- 完成任务时所在的状态 (图中为 K ) 称为终止状态
动作：从当前时刻所处状态转移到下一时刻所处状态所进行操作
状态转移：智能体选择了一个动作之后，其所处状态的相应变化
- 有边的两点之间才能转移
路径/代价：一个状态序列
- 状态序列被一系列操作所连接，如从 A 到 K 所形成的路径
目标测试：评估当前状态是否为所求解的目标状态

我们用一棵树来记录算法探索过的路径

在搜索树中，同一个标号一定表示相同的状态
但是一个标号可能有多个的结点与之对应，即不同的节点对应了从初始状态出发的不同路径

搜索算法可以被看成是一个构建搜索树的过程，从根结点（初始状态）开始，不断展开每个结点的后继结点，直到某个结点通过了目标测试

搜索算法具备如下的评价指标：

完备性和最优性：解的质量
时间复杂度和空间复杂度：算法的资源消耗

评价指标
完备性	当问题存在解时，算法是否能保证找到一个解。
最优性	搜索算法是否能保证找到的第一个解是最优解。
时间复杂度	找到一个解所需时间。
空间复杂度	在算法的运行过程中需要消耗的内存量。

而在搜索树中，我们通常使用如下变量，估计复杂度：

符号	含义
$b$	分支因子，即搜索树中每个节点最大的分支数目
$d$	根节点到最浅的目标结点的路径长度
$m$	搜索树中路径的最大可能长度
$n$	状态空间中状态的数量

搜索算法框架

树搜索

边缘 (fringe) 集合: 集合ℱ用于保存搜索树中可用于下一步探索的所有候选结点，也叫做开表 (openlist)

TreeSearch

输入：节点选择函数 pick_from，后继节点计算函数 successor_nodes
输出：从初始状态到终止状态的路径

算法流程
- $F \leftarrow {根节点}$
- $while F \neq \emptyset do$
  - $n \leftarrow pick_from (F)$
  - $F \leftarrow F - {n}$
  - $if goal_test (n) then$
    - $return n . path$
  - $end$
  - $F \leftarrow F \cup successor_nodes (n)$
- $end$

剪枝搜索

树搜索算法存在问题：并不是其所有的后继节点都值得被探索

在某些情况下，主动放弃一些后继结点能够提高搜索效率而不会影响最终搜索结果，甚至能解决无限循环（即算法不停机）问题

图搜索

在图搜索策略下，在边缘集合中所有产生环路的节点都要被剪枝，但不会排除所有潜在的可行解。因此在状态数量有限情况下，采用图搜索策略的算法也是完备的

GraphSearch

输入：节点选择函数 pick_from，后继节点计算函数 successor_nodes
输出：从初始状态到终止状态的路径

算法流程
- $F \leftarrow 根节点$
- $C \leftarrow \emptyset$ C 用于标记已经访问过的节点
- while F ≠ $\emptyset$ do
  - n ← pick_from (F)
  - F ← F =
  - if goal_test (n) then
    - return n.path
  - end
  - if n.state $\notin$ C then
    - C ← C $\cup$
    - F ← F $\cup$ successor_nodes (n)
  - end
- end

广度优先搜索算法

Is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on

时间复杂度: $O (b^{d})$
空间复杂度: $O (b^{d})$
完备性: Yes
最优性: Depends on the cost (Yes, if cost = 1 per step; not optimal in general)
- 如果每一步的 cost 不一致，就可能找到总代价非最小的路径

深度优先搜索算法

Always expands the deepest node in the current frontier of the search tree. The search proceeds immediately to the deepest level of the search tree, where the nodes have no
Successors.

时间复杂度: $O (b^{m})$
空间复杂度: $O (b m)$
完备性: No
最优性: No

02 启发式搜索 (有信息搜索)

辅助信息	所求解问题之外、与所求解问题相关的特定信息或知识。
评价函数（evaluation function）f (n)	从当前节点 n 出发，根据评价函数来选择后续结点。	下一个结点是谁?
启发函数（heuristic function）h (n)	计算从结点 n 到目标结点之间所形成路径的最小代价值，这里将两点之间的直线距离作为启发函数。	完成任务还需要多少代价?

贪婪最佳优先搜索

评价函数 f (n)=启发函数 h (n)

A* 算法

\underset{评价函数}{\underset{⏟}{f (n)}} = \underset{起始结点到结点 n 代价 (当 前 最 小 代 价)}{\underset{⏟}{g (n)}} + \underset{结点 n 到目标结点代价 (后 续 估 计 最 小 代 价)}{\underset{⏟}{h (n)}}

性能分析

符号	含义
$h (n)$	节点 $n$ 的启发函数取值
$g (n)$	从起始节点到节点 $n$ 所对应路径的实际代价
$f (n)$	节点 $n$ 的评价函数取值
$c (n, a, n^{'})$	从节点 $n$ 执行动作 $a$ 到达节点 $n^{'}$ 的单步代价
$h^{*} (n)$	从节点 $n$ 出发到达终止节点的最小代价
一个良好的启发函数需要满足如下两种性质：

可容性 (admissible): 对于任意结点 $n$ , 有 $h (n) \leq h^{*} (n)$ , 如果 $n$ 是目标结点，则有 $h (n) = 0$
- $h^{*} (n)$ 是从结点 $n$ 出发到达终止结点所付出的（实际）最小代价
- 即估计代价 ≤ 实际代价
一致性 (consistency): 启发函数的一致性指满足条件 $h (n) \leq c (n, a, n^{'}) + h (n^{'})$
- 三角不等式原则

满足一致性条件的启发函数一定满足可容性条件

$\begin{aligned} h (n_{1}) & \leq h (n_{2}) + c (n_{1}, a_{1}, n_{2}) \\ \leq h (n_{3}) + c (n_{2}, a_{2}, n_{3}) + c (n_{1}, a_{1}, n_{2}) \\ \leq \dots \\ \leq c (n_{1}, a_{1}, n_{2}) + c (n_{2}, a_{2}, n_{3}) + \dots + c (n_{t}, a_{t}, K) \\ = h^{*} (n_{1}) \end{aligned}$

完备性：如果在起始点和目标点间有路径解存在，那么一定可以得到解，如果得不到解那么一定说明没有解存在

在一些常见的搜索问题中，状态数量是有限的，此时图搜索 A*算法和排除环路的树搜索 A*均是完备的，即一定能够找到一个解
在更普遍的情况下，如果所求解问题和启发函数满足以下条件，则 A*算法是完备的
- 搜索树中分支数量是有限的，即每个节点的后继结点数量是有限的
- 单步代价的下界是一个正数
- 启发函数有下界

如果启发函数是可容的，那么树搜索的 A*算法满足最优性

启发函数满足可容性时，假设树搜索的 A*算法找到的第一个终止结点为 $n$

对于此时边缘集合中任意结点 $n^{'}$ , 根据算法每次扩展时的策略，即选择评价函数取值最小的边缘节点，有 $f (n) \leq f (n^{'})$

由于 A*算法对评价函数定义为 $f (n) = g (n) + h (n)$ , 且 $h (n) = 0$ , 有 $f (n) = g (n)$ + $h (n) = g (n)$ , $f (n^{'}) = g (n^{'}) + h (n^{'})$ , 综合可得 $g (n) \leq$ $g (n^{'}) + h (n^{'})$ $\leq$ $g (n^{'})$ + $h^{*} (n^{'})$ 。(可容性： $h (n^{'}) \leq h^{*} (n^{'});$ $g (n)$ 表示到终止节点的代价)

此时扩展其他任何一个边缘结点都不可能找到比结点 $n$ 所对应路径代价更小的路径, 因此结点 $n$ 对应的是一条最短路径，即算法满足最优性

如果 A*算法采用的是图搜索策略，那么即使启发函数满足可容性条件，也不能保证算法最优性

最优性，对于任意一个状态𝑡，它第一次被加入搜索树时的路径必然是最短路径

因为存在环路：如果有多个结点对应同一个状态 (即存在多条到达同一个城市的路径), 图搜索算法只会扩展其中的一个结点，而剪枝其余的结点

解决方案

方法 1：当算法从不同路径扩展同一结点时，不保留最先探索的那条路径，而是保留代价最小的那条路径
方法 2：要求启发函数满足一致性
- 由于图中存在环路，所以 $f (n) <= f (n^{'})$ 并不总是成立
- 当启发函数满足一致性时，若结点𝑛′是结点𝑛的后继节点，则有 $f (n) <= f (n^{'})$ 成立
- 假设状态𝑡加入搜索树时对应的结点为𝑛，在结点𝑛被加入搜索树后，若对应状态𝑡的任何结点𝑛′出现在边缘集合中，那么必然有𝑔(𝑛)≤𝑔(𝑛′)

03 对抗搜索

对抗搜索 (Adversarial Search) 也称为博弈搜索 (Game Search)

智能体 (agents) 之间通过竞争实现相反的利益，一方最大化这个利益，另外一方最小化这个利益：

两人对决游戏 (MAX and MIN, MAX 先走) 可如下形式化描述：

状态	状态 s 包括当前的游戏局面和当前行动的智能体。函数 player (s) 给出状态 s 下行动的智能体。
动作	给定状态 s，动作指的是 player (s) 在当前局面下可以采取的操作 a，记动作集合为 actions (s)。
状态转移	给定状态 s 和动作 a∈actions (s)，状态转移函数 result (s, a) 决定了在 s 状态采取 a 动作后所得后继状态。
终局状态检测	终止状态检测函数 terminal_test (s) 用于测试游戏是否在状态 s 结束。
终局得分	终局得分 utility (s, p) 表示在终局状态 s 时玩家 p 的得分。

本次讨论中，主要讨论在**确定的、全局可观察的、竞争对手轮流行动、零和游戏（zero-sum）**下的对抗搜索

最小最大搜索 (Minimax Search)

看 Alpha-Beat 剪枝的例子理解即可

给定一个游戏搜索树，minimax 算法通过每个节点的 minimax 值来决定最优策略

MAX 希望最大化 minimax 值，
MIN 则相反

m i n i m a x (s) = {\begin{cases} utility (s), if terminal_test(s) \\ max_{a \in actions (s)} minimax (result (s, a)), if player(s)=MAX \\ min_{a \in actions (s)} minimax (result (s, a)), if player(s)=MIN \end{cases}

性能分析

完备性: Yes (if the tree is finite)
最优性: Yes (against an optimal opponent)
时间复杂度: $O (b^{m})$
- Depth-first exploration
空间复杂度: $O (b m)$
- Depth-first exploration

Alpha-Beta 剪枝搜索 (Pruning Search)

Alpha-Beta 剪枝搜索算法在 Minimax 算法中可减少被搜索的结点数，即在保证得到与原 Minimax 算法同样的搜索结果时，剪去了不影响最终结果的搜索分枝

Alpha 剪枝

假设有一个位于 MIN 层的结点 $m$ , 已知该结点能够向其上 MAX 结点反馈的收益为 $α$
$n$ 是与结点 $m$ 位于同一层的某个兄弟 (sibling) 结点的后代结点
如果在结点 $n$ 的后代结点被访问一部分后，知道结点 $n$ 能够向其上一层 MAX 结点反馈收益小于 $α$ , 则结点 $n$ 的未被访问孩子结点将被剪枝

Beta 剪枝

考虑位于 MAX 层的结点 $m$ , 已知结果点 $m$ 能够从其下 MIN 层结点收到的收益为 $β$
结点 $n$ 是结点 $m$ 上层结点 $m^{'}$ 的位于 MAX 层的后代结果点
如果目前已知结点 $n$ 能够收到的收益大于 $β$ , 则不再扩展结点 $n$ 的未被访问后继结点，因为位于 MIN 层的结点 $m^{'}$ 只会选择收益小于或等于 $β$ 的结点来采取行动

算法流程

Pseudo Code

根结点（MAX 结点）的𝛼值和𝛽值分别被初始化为−∞和+∞
子节点继承父节点的𝛼值和𝛽值，再按照以下规则进行更新
对于 MAX 节点，如果其孩子结点（MIN 结点）的收益大于当前的𝛼值（极大层的下界），则将𝛼值更新为该收益
对于 MIN 结点，如果其孩子结点（MAX 结点）的收益小于当前的𝛽值（极小层的上界），则将𝛽值更新为该收益
如果一个结点的𝛼值和𝛽值满足𝛼>𝛽的条件，则该结点尚未被访问的后续结点就可以被剪枝

搞懂例子就可以了

原本 Minimax 搜索树中有 26 个结点，经过 alpha-beta 剪枝后只扩展（访问）了其中 15 个结点，可见 alpha-beta 剪枝技术能够有效地减少搜索树中结点的数目
Pasted image 20250605132604.png
Pasted image 20250605132613.png
Pasted image 20250605132620.png
Pasted image 20250605132624.png

性能分析

如果某个结点导致了其右侧兄弟结点被剪枝，那么该节点的所有孩子结点必然已被全部扩展

使用反证法即可

Pasted image 20250605134640.png|262

根据上述结论，可以得出最优效率拓展下的情形：

每层最左端结点的孩子结点必然全部被扩展
其他结点的孩子结点被扩展情况分为如下两类
- 只扩展其最左端孩子结点
  - 例如 k 1 节点和 k 2 节点
- 它是其父亲结点唯一被扩展的孩子结点，且它的所有孩子结点（如果存在）一定被扩展
  - 例如 k 11 和 k 21 节点

在最优效率下扩展的结点数量为 $O (b^{\frac{m + 1}{2}})$ 或 $O (b^{\frac{m}{2}})$

比起原本最小最大搜索的 $O (b^{\hat{m}})$ 有显著提升。

04 蒙特卡洛搜索

引入：多臂赌博机问题

问题描述：

假设智能体面前有𝑲个赌博机，每个赌博机有一个臂膀
每次转动一个赌博机臂膀，随机吐出一些硬币或不吐出硬币，将所吐出的硬币的币值用收益分数来表示
现在假设给智能体 𝝉 (𝛕 > 𝐊) 次转动臂膀的机会
智能体如何选择赌博机、转动 𝝉 次赌博机臂膀，能够获得更多的收益分数

形式化分析

状态：每个被摇动的臂膀即为一个状态，记 $K$ 个状态分别为 ${s_{1}, s_{2}, \cdot \cdot \cdot, s_{K}}$ , 没有摇动任何臂膀的初始状态记为 $s_{0}$
动作: 动作对应着摇动一个赌博机的臂膀，在多臂赌博机问题中，任意状态下的动作集合都为 ${a_{1}, a_{2}$ ..., $a_{K}}$
状态转移：选择动作 $a_{i} (1 \leq i \leq K)$ 后，将相应的改变为 $s_{i}$
奖励 (reward)
- 假设从第 $i$ 个赌博机获得收益分数的分布为 $D_{i}$ , 其均值为 $μ_{i}$
- 如果智能体在第 $t$ 次行动中选择转动了第 $l_{t}$ 个赌博机臂膀，那么智能体在第 $t$ 次行动中所得收益分数 ${\hat{r}}_{t}$ 服从分布 $D_{l_{t}}, {\hat{r}}_{t}$ 被称为第 $t$ 次行动的奖励
- 一般假定奖励是有界的，进一步可假设奖励的取值范围为[0,1]
悔值 (regret) 函数。根据智能体前 $T$ 次动作，可以如下定义悔值函数： $ρ_{T} = T μ^{*} - \sum_{t = 1}^{T} {\hat{r}}_{t} (3.4 .1)$ 其中 $μ^{*} = max_{i \equiv 1. . . . K} μ_{i}$ 。

因此，问题求解的目标为最小化悔值函数的期望，该悔值函数的取值取决于智能体所采取的策略

贪心算法策略

贪心算法策略如下：

给定第 $i (1 \leq i \leq K)$ 个赌博机，记在过去 $t - 1$ 次摇动赌博机臂膀的行动中，一共摇动第 $i$ 个赌博机臂膀的次数为第 $T_{(i, t - 1)}$
第 $i$ 个赌博机在过去 $T_{(i, t - 1)}$ 次被摇动过程中的收益分数平均值 ${\bar{x}}_{i, T_{(i, t - 1)}}$
在第 $t$ 步，只要选择 ${\bar{x}}_{i, T_{(i, t - 1)}}$ 值最大的赌博机臂膀进行摇动

不足：忽略了其他从未摇动或很少摇动的赌博机，而失去了可能的机会 👇

𝝐-贪心算法

l_{t} = {\begin{cases} {argmax}_{i} {\bar{x}}_{i, T_{(i, t - 1)}}, 以 1 - ϵ 的 概 率 \\ 随机的 i \in {1, 2, \dots, K}, 以 ϵ 的 概 率 \end{cases}

不足：与被探索的次数无关 👉 需要对那些探索次数少或几乎没有被探索过的动作赋予更高的优先级

上限置信区间算法（Upper Confidence Bounds, UCB 1）

在第 $t$ 次时选择使得如下式子取值最大的动作 $a_{l_{t}}$ ：

l_{t} = {argmax}_{i} {\bar{x}}_{i, T_{(i, t - 1)}} + C \sqrt{\frac{2 \ln t}{T_{(i, t - 1)}}}

算法流程

Pseudo Code

选择 (selection)
- 算法从搜索树的根节点开始，向下递归选择子节点，直至到达叶子节点或者到达具有还未被扩展过的子节点的节点 L
- 这个向下递归选择过程可由 UCB 1 算法来实现，在递归选择过程中记录下每个节点被选择次数和每个节点得到的奖励均值
扩展 (expansion)
- 如果节点 L 不是一个终止节点 (或对抗搜索的终局节点), 则随机扩展它的一个未被扩展过的后继边缘节点 M
模拟 (simulation)
- 从节点 M 出发，模拟扩展搜索树，直到找到一个终止节点
- 模拟过程使用的策略和采用 UCB 1 算法实现的选择过程并不相同
  - 模拟过程通常会使用比较简单的策略，例如使用随机策略
反向传播 (Back Propagation)
- 用模拟所得结果 (终止节点的代价或游戏终局分数) 回溯更新模拟路径中 M 以上 (含 M) 节点的奖励均值和被访问次数

能看懂例子就可以了

Pasted image 20250605142632.png|450

选择阶段

计算第二层节点的 UCB 值：左侧结点为 $\frac{10}{1} + \sqrt{\frac{2 \ln 2}{1}} = 11.18$ , 右侧结点为 $\frac{5}{1} +$ $\sqrt{\frac{2 \ln 2}{1}} = 6.18$
因此算法选择第二层左侧的结点 L，由于该节点有尚未扩展的子结点，因此选择阶段结束

拓展阶段

在图 3.25 (b) 中，算法随机扩展了 L 的子结点 C，将其总分数和被访问次数均初始化为 0
图 3.25 (b) 画出了 L 的其他未被扩展的子结点，并标记其 UCB 值为正无穷
- 表示算法下次访问到 L 时必然扩展这些未被扩展的结点

模拟阶段

采用随机策略模拟游戏直至完成游戏。当游戏完成时，终局得分为 3

反向传播阶段

更新策略为：MIN 层结点现有总分加上终局得分分数，MAX 层结点现有总分减去终局得分分数
在图 (d) 中
- C 结点的总分被更新为-3，被访问次数被更新为 1
- L 结点的总分被更新为 13，被访问次数被更新为 2
- 根结点的总分被更新为-18，被访问次数被更新为 3