人工智能中的搜索算法是什么？

它们是通过探索状态空间来求解问题的通用过程：从初始状态出发，施加动作生成新状态，到达目标状态时停止。广度优先搜索、深度优先搜索、一致代价搜索、A*、极小化极大、Alpha–Beta 剪枝和蒙特卡洛树搜索是标准的例子。

无信息搜索和有信息搜索有什么区别？

无信息（盲目）搜索只使用问题定义，因此按固定顺序探索状态，例如逐层探索或最深优先。有信息（启发式）搜索还使用对到达目标的剩余代价的估计，从而先探索有希望的状态，通常能快得多地找到解。

为什么 A* 是最优的？

A* 按 f(n) = g(n) + h(n) 的顺序扩展节点，即已付代价加上对剩余代价的启发式估计。如果启发函数从不高估真实的剩余代价，那么最优路径上任何节点的 f 值都不会大于最优代价，所以 A* 会在可能选中一个更差的目标之前先扩展它。这个性质叫作可采纳性。

什么是可采纳的启发函数？

可采纳的启发函数从不高估从某个节点到达目标的真实代价。道路地图上的直线距离是经典例子，因为两点之间没有哪条路比直线更短。一致的启发函数还在每条边上满足三角不等式，它总是可采纳的。

Alpha–Beta 剪枝是如何工作的？

Alpha–Beta 剪枝以深度优先方式运行极小化极大，同时记录 alpha（最大化一方已能保证的值）和 beta（最小化一方已能保证的值）。一旦证明某个分支比已有的选项更差，它余下的子节点就被跳过。结果与极小化极大值完全相同，但考察的局面通常少得多。

什么是蒙特卡洛树搜索？

蒙特卡洛树搜索由 Rémi Coulom 于 2006 年命名，它通过进行大量模拟对局来估计着法的价值。它反复执行四个步骤来生长一棵搜索树：用 UCT 等公式进行选择、扩展、模拟推演，以及把结果回传。它不需要手写的评估函数，这使它成为计算机围棋的突破性方法。

A* 搜索算是人工智能吗？

算。A* 于 1968 年在斯坦福研究所作为 Shakey 机器人 AI 研究的一部分而开发，启发式搜索是符号 AI 的奠基技术之一。如今它在路径规划和游戏中用得如此广泛，以致常被简单地看作一个算法，这是行之有效的符号 AI 方法常见的命运。

深蓝使用了机器学习吗？

不是现代意义上的机器学习。1997 年击败加里·卡斯帕罗夫的深蓝是一台大规模并行的 Alpha–Beta 搜索引擎，配有定制的国际象棋芯片，其评估函数由工程师借助特级大师对局设计和调校。后来的 AlphaZero 等系统才通过自我对弈学习评估。

符号 AI 技术 · 搜索

人工智能中的搜索算法

符号 AI 如何通过探索一个状态空间来找到一条路径、一个证明或一步棋：盲目搜索，启发式搜索与 A*，GPS 的手段–目的分析，基于极小化极大与 Alpha–Beta 的博弈树搜索，以及蒙特卡洛树搜索。每种方法由谁发明、如何运作（附完整例子）、今天在哪里使用、在哪里失效。

Perslis Research · 2026-09-26

人工智能搜索算法是一类通用过程：它们通过系统地探索一个状态空间来求解问题——从初始状态出发，施加动作生成后继状态，直到找到目标状态为止。各算法的区别在于探索状态的顺序，而这个顺序决定了能否找到解、找到的解是否最优，以及要付出多大代价。

一段话说清

搜索是符号 AI 最古老的实用工具。一旦把问题写成状态、动作和目标测试，同一个过程就能求解迷宫、谜题、路径规划、定理证明、行动规划和棋类博弈。无信息算法（广度优先、深度优先、一致代价、迭代加深）只使用问题定义本身。启发式算法额外加入对剩余代价的估计；A*（Hart、Nilsson 与 Raphael，1968）在估计值从不高估时可以证明是最优的。对抗算法搜索博弈树：极小化极大定义一个局面的价值，Alpha–Beta 剪枝在计算这个价值时跳过不可能影响结果的分支，蒙特卡洛树搜索（2006）则通过抽样来估计它。它们共同的敌人是组合爆炸：状态数随深度指数增长，本页的每一种技术，都是在不丢失答案的前提下少看一些状态的办法。

1. 作为问题求解的搜索：状态空间

状态空间搜索

是什么。状态空间搜索把问题变成一张图。节点是状态（一个棋局、一座城市、一个部分完成的证明），边是动作，任务是找到一条从初始状态通往某个通过目标测试的状态的路径。Newell 与 Simon 的启发式搜索假说使它成为早期 AI 的核心，Russell 与 Norvig 的教科书至今仍围绕它来组织整个学科 [1]。

定义（搜索问题）。一个搜索问题是一个元组

⟨ S, s_{0}, A, T, c, G ⟩

：状态集合

S

，初始状态

s_{0} \in S

，每个状态下可用的动作

A (s)

，转移函数

T (s, a)

，单步代价

c (s, a) > 0

，以及目标集合

G \subseteq S

。一个解是一串动作，其经过的状态从

s_{0}

通往

G

；若其总代价最小，则称为最优解。

如何运作。下面每个算法都是同一个循环，只是选择下一个扩展节点的规则不同：维护一个由已生成但尚未扩展的节点构成的前沿（frontier），取出一个，检验它，生成它的后继，再放回前沿。先进先出队列得到广度优先搜索，栈得到深度优先搜索，按路径代价排序的优先队列得到一致代价搜索，按路径代价加启发值排序的优先队列得到 A*。比较算法看四个性质：完备性（有解时一定找到）、最优性、时间与空间，用分支因子 $b$ 、最浅解的深度 $d$ 和最大深度 $m$ 来度量。

局限。这张图几乎从不事先写出，而是按需生成，其规模通常大得惊人。分支因子为 $b$ 的树在深度 $d$ 处有 $b^{d}$ 个节点。这一个事实——组合爆炸——驱动着后面的一切。

2. 无信息搜索：BFS、DFS、迭代加深、一致代价

无信息（或称盲目）算法对目标在哪里一无所知，它们只在探索顺序上有所不同。

广度优先搜索（BFS）

由谁、何时。Konrad Zuse 在 1945 年那篇关于 Plankalkül 语言、被拒的博士论文中描述了广度优先搜索，直到 1972 年才发表；Edward F. Moore 于 1959 年在《The shortest path through a maze》（穿越迷宫的最短路径）中发表了它 [2]。C. Y. Lee 在 1961 年为电路板布线再次独立发现了它。

如何运作。BFS 先扩展深度为 1 的全部节点，再扩展深度为 2 的全部节点，依此类推，使用先进先出队列。当 $b$ 有限时它是完备的，并且找到最浅的目标；当每个动作代价相同时，这个解就是最优的。它的弱点是内存：必须保存整个前沿，即 $O (b^{d})$ 个节点。今天的用途：无权图中的最短路径、社交网络中的距离、网页爬取，以及网络流算法中的基本构件。

深度优先搜索（DFS）

由谁、何时。以深度优先方式探索迷宫可以追溯到 19 世纪的 Charles Pierre Trémaux；Robert Tarjan 1972 年的论文使它成为线性时间图算法的基础 [3]。Prolog 和约束求解器中的回溯就是深度优先搜索。

如何运作。DFS 总是扩展前沿中最深的节点，使用栈，一个分支走到尽头就回溯。它只需要 $O (b m)$ 的内存，但不是最优的；在无限或带环、又不记录已访问状态的空间中，它也不完备：目标可能就在离根一步之遥，它却沿着一条无尽的分支一直走下去。

迭代加深深度优先搜索

由谁、何时。它早已用于国际象棋程序，1985 年由 Richard Korf 加以分析，他证明在蛮力树搜索中，它在时间、空间和解的代价上都是渐近最优的 [4]。

如何运作。依次以深度上限 0、1、2……运行受限深度的 DFS，直到出现目标。重复浅层看似浪费，其实不然：指数树的大多数节点都在最深一层，因此总工作量为

\sum_{i = 1}^{d} (d - i + 1) b^{i} = O (b^{d}), 内存 O (b d)

当 $b = 10$ 时，额外开销约为 11%。迭代加深兼具 BFS 的完备性与“找到最浅解”的保证，以及 DFS 的线性内存；在不知道解有多深时，它是首选的盲目搜索。

一致代价搜索

由谁、何时。一致代价搜索就是 Edsger Dijkstra 1959 年的最短路径算法 [5]，只不过它从起始状态出发、一旦目标被移出队列就停止，而不是在事先给定的整张图上运行。

如何运作。扩展前沿中路径代价 $g (n)$ 最小的节点。当单步代价严格为正时，第一个出队的目标就是最优的，因为所有更便宜的路径都已被扩展过。它就是 $h = 0$ 时的 A*。今天的用途：路由软件和网络协议（Dijkstra 算法是 OSPF 等链路状态路由的核心）。

无信息搜索比较。b = 分支因子，d = 最浅解的深度，m = 最大深度，C* = 最优代价，ε = 最小单步代价。均为标准结论，见 Russell 与 Norvig [1]。
算法	完备？	最优？	时间	空间
广度优先	是（b 有限）	是，若代价相同	O(b^d)	O(b^d)
深度优先	否（深度无限时）	否	O(b^m)	O(bm)
迭代加深	是	是，若代价相同	O(b^d)	O(bd)
一致代价	是（代价 ≥ ε > 0）	是	O(b^(1+⌊C*/ε⌋))	O(b^(1+⌊C*/ε⌋))

3. 启发式搜索：最佳优先、A、IDA、手段–目的分析、局部搜索

启发函数 $h (n)$ 估计从节点 $n$ 到目标的最便宜路径的代价：地图上的直线距离、滑块拼图中放错位置的方块数。领域知识正是从这里进入通用算法的。

贪婪最佳优先搜索

扩展看起来离目标最近的节点，只按 $h (n)$ 给前沿排序。它往往很快，但忽略了已经付出的代价，所以不是最优的；不记录已访问状态时还可能陷入循环。

A* 搜索

由谁、何时。斯坦福研究所（SRI）的 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年发表了 A*，这项工作与 Shakey 机器人项目相关 [6]。同一篇论文证明了下面的最优性结论。

如何运作。A* 按经过 $n$ 的最优解总代价的估计值给前沿排序：

f (n) = g (n) + h (n)

其中 $g (n)$ 是目前找到的从起点到 $n$ 的路径代价， $h (n)$ 是对剩余部分的启发式估计。记 $h^{*} (n)$ 为真实的剩余代价。有两个条件至关重要：

\begin{array}{l} 可采纳： & h (n) \leq h^{*} (n) 对每个节点 n \\ 一致： & h (n) \leq c (n, n^{'}) + h (n^{'}) 对 n 的每个后继 n^{'}, h (目标) = 0 \end{array}

每个一致的启发函数都是可采纳的。直线距离对道路路径规划是可采纳的，因为没有哪条路比直线更短。

完整例子。四个状态：起点 $S$ 、目标 $G$ ，以及 $A$ 、 $B$ 。边 $S \to A$ 代价 1， $S \to B$ 代价 4， $A \to B$ 代价 2， $A \to G$ 代价 6， $B \to G$ 代价 3。启发函数为 $h (S) = 5$ ， $h (A) = 4$ ， $h (B) = 2$ ， $h (G) = 0$ 。真实剩余代价分别是 6、5、3、0，所以 $h$ 是可采纳的；逐条边检查可知它也是一致的。

在四节点图上运行 A*。前沿列出（节点, g, f = g + h）。通过更便宜路径到达的节点会替换旧条目。
步	扩展	新增或改进的条目	该步之后的前沿
0	—	S：g = 0，f = 0 + 5 = 5	(S, 0, 5)
1	S	A：g = 1，f = 5；B：g = 4，f = 6	(A, 1, 5), (B, 4, 6)
2	A	经 A 到 B：g = 3，f = 5（优于 6）；G：g = 7，f = 7	(B, 3, 5), (G, 7, 7)
3	B	经 B 到 G：g = 6，f = 6（优于 7）	(G, 6, 6)
4	G	目标被移出前沿：停止	路径 S → A → B → G，代价 6

贪婪最佳优先搜索会走 S → B → G（代价 7），因为 B 的 $h$ 最小。A* 在 G 第一次以代价 7 被生成时并不停止；它在 G 被选中时才停止，而那时更便宜的路线已经找到了。

定理（A* 的最优性，Hart、Nilsson 与 Raphael，1968）。若单步代价至少为某个

ε > 0

，分支因子有限，且

h

可采纳，则树搜索版的 A* 返回最优解。若

h

一致，则对从不重新打开已关闭节点的图搜索，同样的结论成立 [6] [1]。

证明概要（可采纳情形）。设

C^{*}

为最优代价，并假设 A* 即将返回一个目标

G_{2}

，且

g (G_{2}) > C^{*}

。在一条最优路径被走完之前，它上面总有某个节点

n

位于前沿，且其路径代价就是最优值

g (n) = g^{*} (n)

。于是

f (n) = g^{*} (n) + h (n) \leq g^{*} (n) + h^{*} (n) = C^{*} < g (G_{2}) = f (G_{2})

其中不等号来自可采纳性，最后一步用到

h (G_{2}) = 0

。A* 总是扩展前沿中

f

最小的节点，所以它会在

G_{2}

之前扩展

n

，矛盾。又因为代价至少为

ε

且

b

有限，满足

f \leq C^{*}

的节点只有有限多个，所以最优目标终将被选中。∎

还有一个更强的结论：使用一致启发函数时，在所有使用同一启发函数且保证最优的算法中，除去平局情形，没有哪个算法扩展的节点比 A* 更少。今天的用途：路径规划、机器人运动规划、电子游戏寻路，以及——配合从问题描述中自动计算的启发函数——自动化 AI 规划。局限：A* 把每个生成的节点都留在内存中，这通常才是它的瓶颈；它的速度完全取决于 $h$ 与 $h^{*}$ 有多接近。启发函数很弱时，它会退化为一致代价搜索。

IDA（迭代加深 A）

由谁、何时。Richard Korf，1985 年，与迭代加深的分析出自同一篇论文 [4]。

如何运作。运行深度优先搜索，剪掉 $f = g + h$ 超过阈值的任何分支。第一个阈值是 $h (s_{0})$ ；每一轮新迭代把阈值提高到上一轮中超出阈值的最小 $f$ 值。启发函数可采纳时，找到的第一个目标就是最优的，而内存只与解的深度成线性关系。Korf 报告说，它是当时已知唯一能在实际资源限制内为随机十五数码问题找到最优解的算法；1997 年他又将它与模式数据库启发函数结合，为随机的魔方状态找到了最优解 [7]。局限：由于不保存记忆，它会多次重复扩展相同节点；当不同的 $f$ 值很多时，这个问题尤为严重。

手段–目的分析（GPS）

由谁、何时。Allen Newell、J. C. Shaw 和 Herbert Simon，出自通用问题求解器（General Problem Solver, GPS），该程序创建于 1957 年，1959 年发表报告 [8]。它在这一领域中的位置，见符号 AI 的历史。

如何运作。比较当前状态与目标，找出最重要的差异。查找一个已知能减小该差异的算子（由一张“差异–算子”表提供领域知识）。如果该算子暂时无法施加，就把满足它的前提条件作为子目标并递归；然后施加它，再对剩下的差异重复这一过程。例如：家与远方会议地点之间的差异是距离，飞机能减小它；乘飞机的前提——身在机场——是一个更小的差异，出租车能减小它。

遗产与局限。GPS 把通用推理引擎与它所运行的领域知识分开，这一设计后来在 STRIPS 以及此后每个规划器的目标导向搜索中重现。它只解决了规模小、形式化良好的问题；差异表必须手写，而且处理一个差异可能破坏另一个——后来的规划器称之为目标交互问题。

局部搜索：爬山法与模拟退火

当只关心最终状态而不关心路径时（摆放八皇后、芯片布局、排课表），局部搜索只保留一个当前状态，并移动到某个邻居。爬山法总是移动到最好的邻居，在峰顶停下，而这个峰顶可能只是局部最优。模拟退火由 Kirkpatrick、Gelatt 和 Vecchi 于 1983 年借用金属冷却的类比引入组合优化 [9]：它有时会接受更差的邻居，在温度 $T$ 下对损失 $Δ$ 以概率 $e^{- Δ / T}$ 接受，并随时间降低 $T$ ，从而在早期跳出局部最优、在后期稳定下来。局部搜索几乎不占内存，可扩展到极大的问题；但它不完备，无法证明问题无解。用于可满足性的随机局部搜索（如 WalkSAT）见约束满足、SAT 与 SMT页面。

4. 博弈树搜索：极小化极大、Alpha–Beta、深蓝、MCTS、AlphaGo

在完全信息的双人零和博弈中，一半的着法由对手选择。状态空间变成一棵博弈树，各层在 MAX（程序一方）与 MIN（对手）之间交替。

极小化极大

由谁、何时。John von Neumann 于 1928 年证明了双人零和博弈的极小化极大定理。Claude Shannon 1950 年的论文《Programming a Computer for Playing Chess》（为计算机编程下国际象棋）提出用极小化极大把棋局树搜索到有限深度，并用评估函数给边界局面打分 [10]。此后的每个国际象棋程序都沿用了这一框架。

如何运作。一个状态的极小化极大值按递归定义：

V (s) = {\begin{cases} U (s) & 若 s 为终局（或到达深度上限时，用评估值 E (s) ） \\ {max}_{a \in A (s)} V (T (s, a)) & 若轮到 MAX 走 \\ {min}_{a \in A (s)} V (T (s, a)) & 若轮到 MIN 走 \end{cases}

MAX 选择价值最高的着法，前提是假设 MIN 会以对 MAX 最不利的着法应对。用深度优先搜索精确计算 $V$ 的代价是 $O (b^{d})$ 。国际象棋每个局面大约有 35 种合法着法，所以程序只能搜索到固定深度，再往下就依赖评估函数。

Alpha–Beta 剪枝

由谁、何时。Alpha–Beta 被多次独立发现。John McCarthy 在 1956 年达特茅斯会议前后提出了这一思想；另有多人在 20 世纪 50 年代末和 60 年代初独立得到它，其中 Alexander Brudno 于 1963 年发表了结果。Donald Knuth 与 Ronald Moore 在 1975 年给出了权威的分析和正确性证明 [11]。

如何运作。在深度优先搜索的同时携带两个界： $α$ 是 MAX 在这条路径上别处已经能够保证的最好值， $β$ 是 MIN 已经能够保证的最好值。一旦得知某个节点的值落在 $(α, β)$ 之外，它余下的子节点就不可能改变根节点的决策，于是被跳过。根节点返回的值与极小化极大值完全相同：剪枝改变的是代价，从不改变答案。

完整例子。MAX 在通向 MIN 节点 B、C、D 的三步着法中选择，每个 MIN 节点有三个叶子（图 1）。

B：叶子为 5、9、6。MIN 取最小值，故 $V (B) = 5$ ，此时根节点处 $α = 5$ ：MAX 至少能得到 5。
C：第一个叶子是 3，所以 $V (C) \leq 3 < α$ 。无论另外两个叶子是多少，MAX 都不会选 C。两者都被剪掉。
D：叶子 10 给出 $V (D) \leq 10$ ，尚不能定论；叶子 4 给出 $V (D) \leq 4 < α$ ，于是第三个叶子被剪掉。

V (根) = max (min (5, 9, 6), min (3, ?, ?), min (10, 4, ?)) = max (5, \leq 3, \leq 4) = 5

图 1. 两层树上的 Alpha–Beta。九个叶子中有三个（剪刀标记）从未被评估，而根节点的值 5 与完整的极小化极大相同。

剪枝的效果取决于着法顺序。Knuth 与 Moore 证明，如果总是先搜索最好的着法，Alpha–Beta 考察的叶子局面数为

b^{⌈ d / 2 ⌉} + b^{⌊ d / 2 ⌋} - 1

而不是 $b^{d}$ ：在同样的时间里大约能搜索两倍的深度 [11]。着法顺序最差时，它什么也剪不掉。因此国际象棋程序把大量精力花在排好着法顺序上，使用迭代加深、置换表和各种启发式。局限：评估函数仍需手写或学习，而搜索视野之外的一切都不可见（地平线效应）。

深蓝（1997）

IBM 的深蓝由 Murray Campbell、A. Joseph Hoane Jr. 和许峰雄（Feng-hsiung Hsu）打造，在 1996 年 2 月的首次对抗中以 2–4 落败后，于 1997 年 5 月以 3½–2½ 击败世界冠军加里·卡斯帕罗夫 [12]。它是一台大规模并行的 Alpha–Beta 搜索机，配有定制的国际象棋芯片，每秒约能评估 2 亿个局面，拥有大量搜索延伸，其评估函数的参数由工程师借助特级大师对局数据库调校而成。它并没有通过自我对弈学习下棋。领先的开源引擎 Stockfish 至今仍用 Alpha–Beta 搜索；自 2020 年起，它用一个小型神经网络（NNUE）评估局面，这使它成为神经符号 AI 页面所描述的那种混合系统。

蒙特卡洛树搜索（MCTS）

由谁、何时。Rémi Coulom 在 2006 年于都灵举行的 Computers and Games 会议上发表论文，为蒙特卡洛树搜索命名，并将其用于他的围棋程序 Crazy Stone [13]。同年，Levente Kocsis 与 Csaba Szepesvári 发表了 UCT（“应用于树的上置信界”），它用一个多臂老虎机公式在树中选择着法，并附有收敛性保证 [14]。Browne 等人 2012 年的综述涵盖了最初几年的各种变体 [15]。

如何运作。MCTS 每次模拟一局，逐步构建一棵部分博弈树，分四步：

选择：从根开始，反复选取使下面的 UCT 分数最大的子节点，直到到达一个还有未探索着法的节点。
扩展：添加一个新的子节点。
模拟：从那里用随机或廉价的策略着法把棋下完（称为“推演”或 rollout）。
回传：更新路径上每个节点的获胜次数和访问次数。

UCT (j) = \frac{w_{j}}{n_{j}} + c \sqrt{\frac{\ln N}{n_{j}}}

其中 $w_{j}$ 是经过子节点 $j$ 的获胜次数， $n_{j}$ 是它的访问次数， $N$ 是父节点的访问次数， $c$ 是探索常数（在 Auer、Cesa-Bianchi 与 Fischer 的 UCB1 规则中为 $\sqrt{2}$ [16]）。第一项利用已经赢过的着法；第二项探索很少尝试的着法。时间预算用完后，程序走访问次数最多的那步棋。

为什么重要。Alpha–Beta 需要评估函数，而在围棋中没有人能写出好的评估函数。MCTS 只需要规则：大量推演的平均结果就是评估。从 2006 年起，最强的围棋程序都建立在它之上。今天的用途：围棋等游戏引擎、通用博弈，以及部分不确定条件下的规划。局限：在只有一条精确变化才重要的局面（如国际象棋的战术局面）中，随机推演可能严重误判；而且这种方法是统计性的：它估计一个值，而不是证明一个值。

AlphaGo 与 AlphaZero：搜索加上学习得到的评估

DeepMind 的 AlphaGo 于 2016 年 3 月以 4–1 击败李世石。其《自然》论文描述的是由两个深度网络引导的 MCTS：一个策略网络提出有希望的着法，一个价值网络评判局面，并与推演结合使用 [17]。AlphaZero（《科学》，2018）去掉了推演和人类棋谱，通过自我对弈学习这两个网络，用同一个算法在国际象棋、将棋和围棋上达到超越人类的水平 [18]。在国际象棋中，它每秒搜索的局面远少于 Alpha–Beta 引擎，依靠网络来做选择。这些系统都是混合系统：树搜索是对合法着法的精确记账，负责说明哪些着法存在、它们会导致什么；网络则提供没人能写下来的判断。

5. 时间线

人工智能搜索算法：本页技术的时间线。来源见参考文献。
年份	技术	人物	仍在使用？
1928	极小化极大定理	John von Neumann	是，博弈价值的定义
1945 / 1959	广度优先搜索	Konrad Zuse（1972 年才发表）；Edward F. Moore	是
1950	带评估函数的限深极小化极大，用于国际象棋	Claude Shannon	是
1956–1963	Alpha–Beta 剪枝	John McCarthy；另有多人独立发现，包括 Alexander Brudno（1963）	是，用于国际象棋引擎
1957–1959	手段–目的分析（通用问题求解器）	Newell、Shaw、Simon	作为思想，存在于规划器中
1959	最短路径（一致代价搜索）	Edsger Dijkstra	是，用于路由
1968	A* 搜索	Hart、Nilsson、Raphael（SRI）	是，无处不在
1972	以深度优先搜索为基础的线性时间图算法	Robert Tarjan	是
1975	Alpha–Beta 的分析	Donald Knuth、Ronald Moore	—
1983	模拟退火	Kirkpatrick、Gelatt、Vecchi	是，用于优化
1985	迭代加深的分析；IDA*	Richard Korf	是，用于谜题与规划
1997	深蓝击败卡斯帕罗夫	IBM（Campbell、Hoane、许峰雄）	已退役
2006	蒙特卡洛树搜索；UCT	Rémi Coulom；Kocsis 与 Szepesvári	是
2016	AlphaGo 击败李世石	DeepMind	由 AlphaZero 继承
2018	AlphaZero（《科学》）	DeepMind	方法仍在使用

6. 搜索在哪里失效

组合爆炸。这里的每种技术都在与指数增长搏斗，但没有一种能在一般情况下战胜它。为推广的滑块拼图寻找最优解是 NP 难的，而规划作为一种搜索，在一般情况下是 PSPACE 完全的（见 STRIPS）。1973 年的 Lighthill 报告把组合爆炸列为 AI 的核心障碍，符号 AI 的历史对此有所讲述。
启发函数就是知识，总得有人提供。A* 的速度取决于 $h$ 提供了多少信息。从问题描述中自动推导的启发函数，以及学习得到的启发函数，是现代的答案。
模型必须正确。搜索相对于它的模型是精确的：状态、动作、代价、博弈规则。如果模型遗漏了什么，模型中的最优路径在现实中可能是错的。搜索对它所搜索的模型是否忠实不作任何保证。
不确定性。经典搜索假设动作是确定的、状态完全可观测；隐藏信息和有噪声的传感器需要概率扩展。

7. 搜索与失效安全模型

失效安全模型是这样一种 AI 模型：它在失效时会走向一个受控的安全状态，而不是给出一个自信的错误。正面的一课是可采纳性。A* 定理是一种无论启发函数质量如何都成立的保证，只要启发函数永远不被允许高估：一个糟糕的启发函数只会让 A* 变慢，永远不会让它出错。这正是失效安全性质的形状：提供判断的那个部件可以很弱，而对它施加的一个结构性约束就能保证答案正确。AlphaGo 从另一面展示了同样的分工：网络提出着法，而由树搜索精确执行的博弈规则决定哪些着法存在。

警示的一课是：搜索的好坏取决于它的模型；在预算内返回“未找到解”的搜索，并没有证明解不存在。一个诚实的系统会把这两种结果区分开来报告。我们对知识采用同样的纪律：模型可以提议；只有底层（floor）才能接纳一个事实。Perslis Research 的 Peel 就是这样构建的：在做决定的回路中没有神经网络，知识是带类型、有来源的卡片，学习是可读的计数。据我们所知，它是第一个失效安全模型；确切的主张以及最接近的先前工作，见什么是失效安全模型？ Peel 是一个研究原型。关于搜索如何与其他方法配合，见符号 AI 技术指南与什么是符号 AI？

8. 常见问题

人工智能中的搜索算法是什么？: 它们是通过探索状态空间来求解问题的通用过程：从初始状态出发，施加动作生成新状态，到达目标状态时停止。广度优先搜索、深度优先搜索、一致代价搜索、A*、极小化极大、Alpha–Beta 剪枝和蒙特卡洛树搜索是标准的例子。
无信息搜索和有信息搜索有什么区别？: 无信息（盲目）搜索只使用问题定义，因此按固定顺序探索状态，例如逐层探索或最深优先。有信息（启发式）搜索还使用对到达目标的剩余代价的估计，从而先探索有希望的状态，通常能快得多地找到解。
为什么 A* 是最优的？: A* 按 f(n) = g(n) + h(n) 的顺序扩展节点，即已付代价加上对剩余代价的启发式估计。如果启发函数从不高估真实的剩余代价，那么最优路径上任何节点的 f 值都不会大于最优代价，所以 A* 会在可能选中一个更差的目标之前先扩展它。这个性质叫作可采纳性。
什么是可采纳的启发函数？: 可采纳的启发函数从不高估从某个节点到达目标的真实代价。道路地图上的直线距离是经典例子，因为两点之间没有哪条路比直线更短。一致的启发函数还在每条边上满足三角不等式，它总是可采纳的。
Alpha–Beta 剪枝是如何工作的？: Alpha–Beta 剪枝以深度优先方式运行极小化极大，同时记录 alpha（最大化一方已能保证的值）和 beta（最小化一方已能保证的值）。一旦证明某个分支比已有的选项更差，它余下的子节点就被跳过。结果与极小化极大值完全相同，但考察的局面通常少得多。
什么是蒙特卡洛树搜索？: 蒙特卡洛树搜索由 Rémi Coulom 于 2006 年命名，它通过进行大量模拟对局来估计着法的价值。它反复执行四个步骤来生长一棵搜索树：用 UCT 等公式进行选择、扩展、模拟推演，以及把结果回传。它不需要手写的评估函数，这使它成为计算机围棋的突破性方法。
A* 搜索算是人工智能吗？: 算。A* 于 1968 年在斯坦福研究所作为 Shakey 机器人 AI 研究的一部分而开发，启发式搜索是符号 AI 的奠基技术之一。如今它在路径规划和游戏中用得如此广泛，以致常被简单地看作一个算法，这是行之有效的符号 AI 方法常见的命运。
深蓝使用了机器学习吗？: 不是现代意义上的机器学习。1997 年击败加里·卡斯帕罗夫的深蓝是一台大规模并行的 Alpha–Beta 搜索引擎，配有定制的国际象棋芯片，其评估函数由工程师借助特级大师对局设计和调校。后来的 AlphaZero 等系统才通过自我对弈学习评估。

9. 参考文献

S. Russell, P. Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2020.
E. F. Moore. The Shortest Path Through a Maze. Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959.
R. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing 1(2):146–160, 1972. doi:10.1137/0201010
R. E. Korf. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. Artificial Intelligence 27(1):97–109, 1985. doi:10.1016/0004-3702(85)90084-0
E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1:269–271, 1959. doi:10.1007/BF01386390
P. E. Hart, N. J. Nilsson, B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 4(2):100–107, 1968. doi:10.1109/TSSC.1968.300136
R. E. Korf. Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. Proceedings of AAAI-97, 1997.
A. Newell, J. C. Shaw, H. A. Simon. Report on a General Problem-Solving Program. Proceedings of the International Conference on Information Processing (Paris), pp. 256–264, UNESCO, 1959.
S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by Simulated Annealing. Science 220(4598):671–680, 1983. doi:10.1126/science.220.4598.671
C. E. Shannon. Programming a Computer for Playing Chess. Philosophical Magazine 41(314):256–275, 1950. doi:10.1080/14786445008521796
D. E. Knuth, R. W. Moore. An Analysis of Alpha-Beta Pruning. Artificial Intelligence 6(4):293–326, 1975. doi:10.1016/0004-3702(75)90019-3
M. Campbell, A. J. Hoane Jr., F.-h. Hsu. Deep Blue. Artificial Intelligence 134(1–2):57–83, 2002. doi:10.1016/S0004-3702(01)00129-1
R. Coulom. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games (CG 2006, Turin), LNCS 4630, pp. 72–83. Springer, 2007. doi:10.1007/978-3-540-75538-8_7
L. Kocsis, C. Szepesvári. Bandit Based Monte-Carlo Planning. Machine Learning: ECML 2006, LNCS 4212, pp. 282–293. Springer, 2006. doi:10.1007/11871842_29
C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, S. Colton. A Survey of Monte Carlo Tree Search Methods. IEEE Transactions on Computational Intelligence and AI in Games 4(1):1–43, 2012. doi:10.1109/TCIAIG.2012.2186810
P. Auer, N. Cesa-Bianchi, P. Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47(2–3):235–256, 2002. doi:10.1023/A:1013689704352
D. Silver, A. Huang, C. J. Maddison, A. Guez, et al. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 529(7587):484–489, 2016.
D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, et al. A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play. Science 362(6419):1140–1144, 2018. doi:10.1126/science.aar6404