搜索与优化

古典人工智能的主要研究内容就是用一般性的策略，在巨大的搜索空间里做智能决策。

形式化定义

在计算理论中，如果你能把问题 A 归约为问题 B，那么只要解决了 B，你就解决了 A。我们能否把任何人工智能问题都建模成一类问题，从而让人工智能和NP问题一样可以方便归约呢？人工智能先驱赫伯特·西蒙 (Herbert Simon) 和艾伦·纽厄尔 (Allen Newell) 在 1959 年开发的通用问题求解器GPS (General Problem Solver) 程序。它是历史上第一个试图将“搜索策略”与“领域知识”分离的 AI 程序，旨在模拟人类解决问题的思维方式。

在AIMA中，我们可以看到AI工程实践中将通用问题求解转化为一种受约束的搜索。换句话说，无论你的问题多么复杂，只要你想让计算机帮你解决，那么你最终就必须要把它变成一种搜索语言。换言之，只要建模水平足够高，那么世界上就没有搜索解决不了的通用难题。我们把AIMA中的这种搜索版本的通用问题求解器称为问题求解智能体（problem-solving agent）。

问题求解智能体主要解决状态空间搜索问题，其计算过程被称为搜索（search）。在后面的讨论中，我们说的搜索问题就是指通用问题。

首先，对于任何搜索问题，我们都要明确状态：

状态空间 state space，包含所有可能的环境状态
初始状态 initial state，智能体启动时的状态
目标状态 goal state，一个或者多个

从当前位置或任意位置到目标位置都会产生路径。具体而言：

路径 path，一个动作序列形成一根条路径
解 solution，一条从初始状态到某个目标状态的路径

我们用公式\(g(n)\)来表示从初始状态（Initial State）到达当前状态 \(n\)的路径总长度或总代价。AI 通过比较不同路径的 \(g(n)\) 来寻找最经济的方案。

构建路径代价的基础组件可以表示为单步代价函数：

\[ c(s, a, s') \]

其中：

\(s\)：当前所处的状态。
\(a\)：在该状态下采取的动作（Action）。
\(s'\)：采取动作后转移到的新状态。

我们用路径代价 (Path Cost)指从 初始状态开始 ，到达当前节点所经历的所有单步代价的总和。

在搜索问题中，AI 的目标通常是找到一条从初始状态到目标状态的路径，使得 总路径代价 \(g(n)\) 最小化 。在伪代码中，路径代价被记录为 node.PATH-COST。它的计算方式是累加的：child.PATH-COST = node.PATH-COST + action-cost。最佳优先搜索 （包括 UCS 和 A）在 reached 表中记录和比较的正是这个 累积的路径代价* ，以此来判断是否发现了一条更优的路线。

此外，动作和动作代价函数为：

行动 action，给定一个状态s，action(s) 将返回可执行动作集合
转移模型 transition model，RESULT(s, a) 返回在状态s下执行动作a所产生的状态
动作代价函数 action cost function，ACTION-COST(s, a, s')，给出了在状态s中执行动作a，进而转移到状态s'的数值代价。

我们假设动作代价是可累加的，也就是说，一条路径的总代价是各个动作代价的总和。最优解（optimal solution） 是所有解中路径代价最小的解。我们暂时假设所有动作代价都为正数，来减少复杂性。

状态空间可以用图来表示。图中的顶点表示状态，顶点之间的有向边表示动作。

1769214670133

在强化学习中，这种表达方式被保留了下来。这种形式化搜索的思路从未在AI发展中消失过，Alpha Go通过蒙特卡洛树搜索来看远一点，并通过神经网络评估当前状态的胜算，从而指导搜索往更有希望的方向走；OpenAI ChatGPT o1的思维链（CoT）本质上就是在予以空间里寻找解的路径，并通过搜索来尝试多种推理路径，在失败时回溯并尝试其他路径。

无信息搜索

在算法学习中我们一般都会学习BFS和DFS，这两种算法都属于无信息搜索（Uninformed Search）。

无信息搜索只知道：

起始点
合法的动作
目标

无信息搜索的局限性在于效率低下，由于不做剪枝，也没有任何策略，一旦状态空间很大，需要记录和搜索的状态数量就会非常大。因此，无信息搜索可以被视为一种暴力解法，其特点是只要时间和空间足够，一定能找到答案。

这里要注意，记录访问点（Explored Set） 仅仅是一种 优化手段 ，用来把“树搜索”变成“图搜索”。

树搜索的意思就是算法把搜索空间想象成一棵不断向下生长的“树”，它不关心某个状态（比如拼图的一个特定摆法）之前是否出现过。因此，如果你从 A 走到 B，再从 B 走回 A，树搜索会把第二个 A 当作一个全新的节点继续扩展。

图搜索在树搜索的基础上增加了一个“记事本”，也就是 Explored Set（已探索集合） 。每当算法彻底处理完一个节点，就会把它丢进 Explored Set。在生成新节点时，算法会先查阅账本。如果这个状态已经在 Explored Set（或者还在等待处理的 Frontier）里了，就直接扔掉，不再重复探索。这保证了算法不会在同一个坑里摔两次，极大地提升了效率，并解决了死循环问题。

BFS与Dijkstra

详见算法笔记。

双向搜索（Bidirectional Search） 同样是基于 BFS（广度优先搜索） 的思想，但它通过“两头堵”的方式极大地提升了搜索效率。

一致代价搜索

广度优先搜索假设每一步的代价都是相等的（比如都是 1）。在现实世界中，不同动作的代价往往不同（例如：走高速路快但贵，走小路慢但免费）。UCS 能够处理这种非等代价的情况，确保找到的是总成本最低的最优路径。

UCS的核心思路就是：总是优先expanding the cheapest path.

DFS与内存问题

回溯搜索是DFS的一种变体，使用的内存更少。

为了避免DFS陷入无限路径，可以使用深度受限搜索（depth-limited search）。

迭代加深搜索（iterative deepening search）也是类似的道理。

启发式搜索

启发式搜索（Heuristic Search） 在无信息搜索的基础上增加了启发函数（heuristic function）。

启发函数

在算法与AI语境下，如果我们只说Heuristic，那么一般都是指启发函数（heuristic function），写作h(n)。这个词起源于希腊语 heuriskein （发现）。

我们用g(n)来表示实际代价，h(n)来表示从当前节点n到目标节点的估计代价。启发式搜索的评价函数中至少需要有h(n)。

这里要注意，启发式函数是可以看到“棋盘布局”的，但是这种布局并非实际的布局，而是一个先天设定的固定布局。比如说，对于地图导航来说，启发式搜索可以把a到b的直线距离作为启发函数。

如果一个启发式函数 \(h(n)\) 被称为是 可容许的(Admissible)，它必须满足一个核心条件：永远不会高估（Never Overestimate）到达目标的实际最小代价，即：

\[ 0 \leq h(n) \le h^*(n) \]

对于任何节点 \(n\)， \(h^*(n)\) 是到达目标的真实最低成本。这是一个“乐观”的估计，认为路程最多还有这么远，甚至可能更近，但绝不会比实际更远。可采纳的启发式函数可以保证找到通往目标的最优解（即路径成本最低的解）。

如果一个启发式函数是一致的（Consistent），其必须满足：对于任意节点 \(n\) 及其后继节点 \(n'\)，从 \(n\) 到目标的预估代价，不大于“从 \(n\) 到 \(n'\) 的实际代价”与“从 \(n'\) 到目标的预估代价”之和，即：

\[ h(n) \le cost(n, a, n') + h(n') \]

这类似于几何学中的 三角不等式 。随着路径的推进，估计代价的下降速度不会超过实际消耗的代价。它是 A 算法在图搜索（Graph Search）中不需要重复访问已关闭节点（Closed Set）就能找到最优解的 充分条件* 。

对于树搜索，启发式函数必须满足Admissibility；对于图搜索，启发式函数必须满足Consistency。

最佳优先搜索

最佳优先搜索 (Best-First Search)的核心逻辑是：永远从待选区域中挑一个“看起来最好”的节点来处理。

算法通过两个关键容器来协同工作：

Frontier（边界） ：一个以 评价函数 \(f\) 排序的优先队列 。它保证每次弹出的节点都是当前 \(f(n)\) 值最小（即被认为“最佳”）的。
Reached（已到达） ：一个查找表（Hash Table），记录状态到节点的映射。它不仅用于去重，还存储了到达每个状态的最低路径代价。

其伪代码如下：

BEST-FIRST-SEARCH 最佳优先搜索
起始点s
frontier 优先队列，初始化加入起始点s，记录现在正在搜索的点集合，按评价函数f排序
reached 查找表，记录起始点s到其他点的距离，起始点s也放入其中（后续可能回到起始点）

当frontier不为空的时候：
    从frontier中弹出元素node
    如果node是目标点，结束搜索，return node.
    如果node不是目标点：
        看一下node这里能做什么动作
        对于每个能做的动作：
            子状态 s' = RESULT(s, action)
            计算s到s'的花费（路径代价）
            如果s'不在reached中，或者这个花费比已经记录的更小：
                更新reached[s']为这个新节点
                将s'作为一个新节点加入frontier队列

搜索结束后，如果还没有找到goal，则说明搜索失败，return Failure.

最佳优先搜索（Best-First Search）的意义在于它提供了一个 通用的算法框架 。通过简单地更换 评价函数 \(f(n)\)**** ，它就能在不同的搜索策略之间切换，从而应对不同类型的复杂问题。

它的核心价值是： 不再盲目地按固定顺序搜索，而是根据某种“标准”优先处理最有希望的节点 。

你可以通过调整 \(f(n)\) 的定义，让这个通用的“框架”变成你熟悉的具体算法：

f(n) = 节点深度 → BFS
f(n) = g(n) → 一致代价搜索UCS
f(n) = g(n) + h(n) → A-Star

贪心最佳优先搜索因为用到了h(n)，所以也算是启发式搜索。

A-Star

A*算法是complete且optimal的。

\[ \large \underbrace{f(n)}_{\text{Total cost of node}} = \underbrace{g(n)}_{\substack{\text{Path cost} \\ \text{(the true value)}}} + \underbrace{h(n)}_{\substack{\text{Heuristic} \\ \text{(estimate to goal)}}} \]

最经典的应用是8-Puzzle问题：8 数码问题 (8-Puzzle) 是一个经典的路径搜索难题，通常由一个 \(3 \times 3\) 的网格组成，其中包含 8 个带有数字（1-8）的方块和一个空位。

游戏的目标是通过滑动方块，将乱序的初始状态调整为特定的目标状态（通常是数字按 1 到 8 顺序排列，空位在最后）。你只能将与空位相邻的方块移动到空位中，这在视觉上等同于“移动空位”到上、下、左、右四个方向。

为了让 A* 运行得更快且保证找到最少步数（最优解），通常使用以下两种一致的启发函数：

错位棋子数 (Misplaced Tiles) ：计算当前棋盘上有多少个数字没有处在正确的目标位置上。
曼哈顿距离 (Manhattan Distance) ：计算每个棋子当前位置与目标位置之间的 水平和垂直距离之和 。这是最常用的启发函数，比错位棋子数更“精准”，能显著减少搜索的节点数量。

一般认为具有一直启发式函数的A搜索是效率最优（optimally efficient） 的，因为任何从初始状态扩展搜索路径并使用相同启发式信息的算法都必须扩展A的所有必然扩展节点。这种高效也来自于对寻找最优解没有帮助的搜索树节点进行剪枝（pruning）。

我们来看下面这个例子：

1769656921093

\(h\) 值（启发式值）只代表“当前节点到终点”的预估距离，它不具有累加性。因此在计算每个节点的\(f\)值（总评价分数）时：

\[ f(n) = g(n) + h(n) \]

A 算法的核心是维护一个优先队列，每次选择 \(f(n) = g(n) + h(n)\) 最小的节点进行 扩展（Expand）* 。

\(g(n)\)：从起点 A 到当前节点的实际代价。
\(h(n)\)：当前节点到目标节点的启发式估计值（图中圆圈内的值）。
Tie-breaking（破局规则） ：如果 \(f\) 值相同，按照从左到右的顺序访问。
终止条件 ：当目标节点被扩展时，算法停止并返回路径。

我们需要逐步跟踪优先队列（Open List/Frontier）的状态：

扩展 A : \(g(A)=0, h(A)=1 \Rightarrow f(A)=1\)。

生成子节点：B 和 C。
\(f(B) = g(B) + h(B) = 2 + 1 = 3\)
\(f(C) = g(C) + h(C) = 1 + 4 = 5\)
队列 : \([(B, f=3), (C, f=5)]\)

扩展 B :（因为 \(f=3\) 最小）

生成子节点：D, E, F。
\(f(D) = (2+13) + 2 = 17\)
\(f(E) = (2+2) + 5 = 9\)
\(f(F) = (2+8) + 0 = 10\)
队列 : \([(C, f=5), (E, f=9), (F, f=10), (D, f=17)]\)

扩展 C :（因为 \(f=5\) 最小）

生成子节点：G, H, I。
\(f(G) = (1+2) + 4 = 7\)
\(f(H) = (1+4) + 3 = 8\)
\(f(I) = (1+5) + 2 = 8\)
队列 : \([(G, f=7), (H, f=8), (I, f=8), (E, f=9), (F, f=10), (D, f=17)]\)

扩展 G :（因为 \(f=7\) 最小）

生成子节点：L。
\(f(L) = (1+2+10) + \infty = \infty\)
队列 : \([(H, f=8), (I, f=8), (E, f=9), (F, f=10), (D, f=17), (L, f=\infty)]\)

扩展 H :（\(H\) 和 \(I\) 的 \(f=8\) 相同，按左到右顺序先扩 \(H\)）

生成子节点：M。
\(f(M) = (1+4+10) + \infty = \infty\)
队列 : \([(I, f=8), (E, f=9), (F, f=10), (D, f=17), (L, f=\infty), (M, f=\infty)]\)

扩展 I :（因为 \(f=8\) 最小）

生成子节点：N。
\(f(N) = (1+5+3) + 0 = 9\)
队列 : \([(E, f=9), (N, f=9), (F, f=10), (D, f=17), \dots]\)

扩展 E :（\(E\) 和 \(N\) 的 \(f=9\) 相同，按左到右顺序先扩 \(E\)）

生成子节点：K。
\(f(K) = (2+2+5) + \infty = \infty\)
队列 : \([(N, f=9), (F, f=10), (D, f=17), \dots]\)

扩展 N :（\(f=9\) 最小。由于 N 是目标节点且被扩展，搜索终止）

被扩展的节点顺序为：A, B, C, G, H, I, E, N

算法返回的最终路径是从起点到被扩展的目标节点 N 的回溯：

N 的父节点是 I
I 的父节点是 C
C 的父节点是 A

最终路径：A \(\rightarrow\) C \(\rightarrow\) I \(\rightarrow\) N

最终路径的总成本即为 \(g(N)\)：

\(Cost(A, C) = 1\)
\(Cost(C, I) = 5\)
\(Cost(I, N) = 3\)
总成本 \(1 + 5 + 3 = 9\)****

局部搜索

局部搜索 （Local Search）是一种用于解决组合优化问题的 启发式算法 （Heuristic Algorithm）。简单来说，它的核心思想是“ 走一步看一步，只选更好的 ”。算法从一个初始解开始，通过不断地在当前解的“邻居”中寻找更优解来逐步改进，直到达到一个局部最优状态或满足停止条件。

虽然从原理上来看，局部搜索并不能找到全局最优解，而会被困在局部最优上，但是由于局部搜索已经足够好，足够用于解决许多无法使用全局最优解的情况。同时，局部搜索通常是很多高级算法的“内核”。大家会利用它极快的搜索速度，配合一些“跳出陷阱”的机制。

爬山搜索

参见如下State Space Landscape：

1769655420744

爬山算法（Hill Climbing） 是一种 贪心算法 。它的逻辑极其简单：

随机上山 ：随机选一个点作为初始位置。
环顾四周 ：检查当前位置附近的相邻点（邻域）。
向上移动 ：如果有比现在更高（更好）的点，就迈过去。
止步巅峰 ：如果四周所有的点都比现在低，就认为到达了山顶，停止搜索。

由于爬山算法只看眼前、不走回头路，它经常会遇到以下三个尴尬的处境：

局部最大值（Local Maxima） ：正如你所说的，它爬上了一个小土丘，虽然不是整座山的最高峰，但由于四周都在下坡，它会误以为自己已经登顶。
高原/平原（Plateau） ：周围一片平坦。算法发现往哪走都一样，于是失去了方向，只能在平地上乱逛（随机游走）。
山脊（Ridge） ：这是一个很有趣的现象。山脊窄且陡峭，如果你只能沿东西或南北方向走，每一步都可能在下坡，导致算法在山脊两侧反复横跳，却很难顺着脊线向上。

爬山算法本身并不是一个很好的算法，但是我们可以以此为基础，扩展出实用的算法方案。

随机爬山法引入了随机（Stochastic） 概念：在所有向上的路中，随机选一条，而不是选最陡的。有一定概率避开那些窄小的局部巅峰。这里出现了Exploration vs. Exploitation的tradeoff，这一点在后来的强化学习中尤为重要。

基于随机性的随机重启爬山法 (Random-restart)是爬山算法中最实用的方案 。爬到一个山顶后，直接把自己传送到另一个随机起点重新爬。只要重启次数够多，找到最高峰的概率极大。

8皇后问题

八皇后问题 （8-Queens Problem）中，一个“状态”就是棋盘上 8 个皇后的完整布局。我们可以很容易地定义 邻域（Neighbors） ：即移动其中一个皇后到同一列的其他行。八皇后问题有一个非常直观的 评价函数 \(h\)* ： *当前棋盘上互相攻击的皇后对数。我们的目标是最小化这个 \(h\)（在算法中可以理解为爬向海拔最低点，即“下山”）。

随机重启动爬山法在概率上是完备的。只要你重新启动的次数足够多，它几乎 100% 能找到八皇后的解（因为状态空间是有限的）。它的效率取决于“找到解的状态”在所有状态中的密度。对于八皇后（8x8），它很快；但对于八千皇后，随机重启的盲目性就会显现出来。

在八皇后（以及所有的 N 皇后）问题领域，最小冲突启发式（Min-Conflicts）通常被认为比任何形式的爬山法都更接近“最优局部搜索解”：

随机重启爬山法： 每次可能要评估所有皇后的所有移动位置，选一个最好的（计算量大）。
Min-Conflicts： 只随机选一个有冲突的皇后，然后只为它寻找冲突最少的位置。
实测数据： 对于 1,000,000 皇后问题，随机重启动爬山法可能还在不断重置棋盘时，Min-Conflicts 通常在 50 步以内就能收敛到解。

元启发式算法

元启发式算法的核心在于处理探索（Exploration）与开发（Exploitation） 的矛盾：

全局搜索（Exploration）
局部寻优（Exploitation）

元启发通过某种机制（如模拟退火的温度、遗传算法的变异）动态地调节这两者的比例，从而让算法得以脱离局部最优，而向全局最优迈进。

常见的元启发算法包括：

模拟退火（Simulated Annealing） ：允许以一定的概率接受“变差”的解，从而有机会跳出小坑。
禁忌搜索（Tabu Search） ：通过建立一个“禁忌表”，防止算法在近期搜索过的地方反复徘徊。
变邻域搜索（Variable Neighborhood Search） ：当在一个邻域找不到更好解时，扩大搜索范围，改变邻域的定义。
进化算法
粒子群算法
蚁群算法

模拟退火

模拟退火算法（Simulated Annealing, SA） 是一种受物理学启发而产生的概率型全局寻优算法。它的核心直觉来源于金属冶炼中的 退火过程 ：将固体加热至高温后慢慢冷却，粒子会随着温度降低逐渐趋于稳定的低能态，最终形成完美的晶体（即全局最优解）。模拟退火的核心在于解决“局部最优解”陷阱。传统的爬山法（Greedy Search）只往好的方向走，容易困在山腰。而 SA 允许在一定概率下往坏的方向走，从而跳出局部坑洞。

模拟退火的核心数学逻辑是玻尔兹曼分布（Boltzmann distribution） 与 Metropolis 准则。

假设当前解为 \(x_{current}\)，产生了一个新解 \(x_{next}\)，能量（目标函数值）之差为 \(\Delta E = f(x_{next}) - f(x_{current})\)：

如果 \(\Delta E < 0\)（解变好了）： 100% 接受新解。
如果 \(\Delta E > 0\)（解变差了）： 以一定的概率 \(P\) 接受新解。

这个概率 \(P\) 的计算公式为：

\[ P = \exp\left(-\frac{\Delta E}{T}\right) \]

其中 \(T\) 是当前的“温度”：

高温阶段： \(P\) 接近 1。算法几乎以随机游走的方式在搜索空间横冲直撞，目的是 遍历全局 。
低温阶段： \(P\) 趋向 0。算法变得非常“保守”，只接受更好的解，目的是 精细收敛 。

Metropolis 准则是模拟退火算法的判定大脑，它决定了算法是否接受一个“变差了”的解。假设当前能量为 \(E_{curr}\)，新生成的能量为 \(E_{next}\)，变化量 \(\Delta E = E_{next} - E_{curr}\)。

接受新解的概率 \(P\) 为：

\[ P = \begin{cases} 1, & \text{if } \Delta E < 0 \text{ (解变好了)} \\ \exp\left(-\frac{\Delta E}{k T}\right), & \text{if } \Delta E \ge 0 \text{ (解变差了)} \end{cases} \]

注：在算法实践中，波尔兹曼常数 \(k\) 通常取 1 以简化计算。

这个准则源于统计力学。在一个恒温系统中，粒子处于能量为 \(E\) 的状态的概率符合玻尔兹曼分布。Metropolis 准则模拟了这种自然界的平衡过程：即使系统倾向于低能态，但在一定温度下，粒子仍然有概率跳到高能态。

对抗搜索和博弈

本笔记主要讨论对抗搜索和博弈，通过本笔记的内容，我们可以掌握解决井字棋、国际象棋、围棋的算法。

博弈论

囚徒困境

MiniMax

MiniMax算法可以解决井字棋等状态空间不够大的双人零和博弈问题。

双人零和博弈就是两个人进行一场游戏，该游戏的结果要么是某一个人获胜、要么是平局，而不存在两个人都获胜的情况。在我的笔记算法>>动态规划中已经解决过Coin Game和井字棋游戏并介绍了Minimax思想。

AIMA将两个参与者分别称为MAX和MIN。这个很好理解，假设我们自己是参与者，那么我们自己就是MAX，对手就是MIN——这个MIN本身是从我们自己的角度来看的，对手为了最大化自己的利益，从而导致我们的利益在对方的轮次被最小化了。

井字棋

Alpha-Beta

对于国际象棋等状态空间巨大而不能使用朴素的Minimax方法的情况，我们使用Alpha-Beta剪枝。

国际象棋

蒙特卡洛树搜索

对于围棋这样的超过宇宙原子数的状态空间的游戏，我们使用蒙特卡洛搜索树（Monte Carlo Tree Search，MCTS）。

围棋

这里主要介绍朴素MCTS方法下的早期围棋程序。AlphaGo在MCTS的核心基础上，增加了深度强化学习，从而解决了传统Rollout+手工规则卡死在新手水平的问题。