人工智能 — rin.contact

今天「AI」几乎总是指机器学习——但这个领域要古老和广阔得多。经典的、或称符号的 AI，关乎让机器推理：在可能性中搜索、应用逻辑，并规划一连串通向目标的行动。没有训练数据，没有神经网络——只有对问题的显式建模，以及一种巧妙的导航方式。

本页是经典基础，并为基础层收尾。它之所以重要，有两个原因：这些技术至今仍在运行真实系统（路线规划器、调度器、游戏引擎、求解器），而理解它们，能让你看清机器学习在「让机器智能地行动」这幅更大的图景中究竟处在何处。

AI 究竟意味着什么

没有单一的定义，但最有用的框架是理性智能体：一个感知其环境、并为在其目标下取得最佳期望结果而行动的实体。这里的「智能」并不神秘——它就是在你已知的前提下做正确的事。这个领域一直有两条大路：

符号 AI（本页）——把知识显式地表示为符号与规则，并通过搜索和逻辑对其推理。透明且可证明，但当世界变得杂乱时很脆弱。
统计 AI（机器学习）——从数据中学习行为，而非手工编码。对杂乱稳健，但不透明。

本页大部分是符号式的，因为「AI」一词正是建立在那个基础上的——也因为你所欣赏的现代系统通常把两者缝合在一起。

作为搜索的问题求解

经典 AI 的一大片都归结为一个思想：搜索。把一个问题表述为一个你可以在其中移动的状态空间，「解决」它就变成了找到一条从你所在之处到你想去之处的路径。每个搜索问题都有五个部分：

状态——可能的配置（一个棋盘局面、你所在的一座城市）。
初始状态——你的起点。
动作——从某状态出发的合法移动。
目标检验——你如何认出自己已经到达。
路径代价——每一步的花费，让你能偏好更便宜的解。

搜索会构建一棵树：根是起点，分支是动作，你向外扩展节点以寻找目标。全部的艺术在于你扩展的顺序——因为这棵树通常大到无法完全探索。

无信息搜索

无信息（或称「盲目」）策略对目标在哪个方向毫无头绪——它们只是系统地探索。两个支点：

广度优先搜索（BFS）——在更深一层之前先扩展某一深度的所有节点。它找到最浅（步数最少）的解，但其内存开销随深度呈指数爆炸。
深度优先搜索（DFS）——在回溯之前先把一条分支走到底。占用内存少，但它可能在一条又深又错的路上迷失，且不保证找到最优解。

加上路径代价，BFS 就推广为一致代价搜索，它总是扩展目前为止最便宜的节点，并保证找到代价最低的路径。所有这些方法的麻烦在于，它们忽略了对目标朝哪个方向的任何感知——所以它们探索了大片毫无意义的区域。这正是启发式所修复的。

有信息搜索与 A*

有信息搜索使用一个启发函数 $h(n)$ ——对从某节点到目标的剩余代价的一个廉价估计（例如在道路网中导航时的直线距离）。一个好的启发函数把搜索大致指向正确的方向，并剪除大量被浪费的工作。

著名的 A* 算法把已经付出的代价与对剩余部分的估计结合起来，扩展使下式最小的那个节点：

f(n) = \underbrace{g(n)}_{\text{cost so far}} + \underbrace{h(n)}_{\text{estimated cost to goal}}

g(n)：目前为止的代价。h(n)：估计的剩余代价。A* 扩展总和 f(n) 最小的节点。

A* 是可证明最优的——保证找到最便宜的路径——只要启发函数是可采纳的，即它从不高估真实的剩余代价：

h(n) \le h^{*}(n) \quad \text{for every node } n

直觉是：一个乐观的估计永远不会让 A* 错误地跳过真正最好的路径。这一个算法驱动着路线规划器、游戏寻路和无数调度器——它是经典 AI 中使用最广的结果。

A* 的扩展。从起点出发，每个前沿节点按 f = g + h 打分；A* 总是扩展 f 最小的。乐观的启发函数把它引向目标，跳过那些不可能胜过已找到最优路径的分支。

博弈：极小化极大

博弈引入了一个与你作对的对手，所以你不能只是找一条路径——你必须针对一个理性的对手来规划。经典答案是极小化极大：假设双方都下得完美，然后在「对手会最小化你的结果」的前提下，选择使你的结果最大化的着法。你把博弈树探索到某个深度，给叶子局面打分，再把值向上传播——在你的回合取最大、在对手的回合取最小：

\text{minimax}(s) = \begin{cases} \text{utility}(s) & \text{if } s \text{ is terminal} \\ \max_{a}\ \text{minimax}(\text{child}) & \text{if it's our move} \\ \min_{a}\ \text{minimax}(\text{child}) & \text{if it's their move} \end{cases}

博弈树大得天文，所以极小化极大要搭配 alpha-beta 剪枝：在搜索时，你追踪每位玩家已经能保证的最佳分数，而一旦某条分支不可能胜过它，你就停止探索它。它返回与朴素极小化极大完全相同的答案，却跳过了树的一大片——这正是经典博弈 AI（深度学习之前的国际象棋引擎）能向前看许多步的原因。

约束满足

许多真实问题不是关于找一条路径，而是关于找到一个满足一组规则的赋值——安排考试使其互不冲突、给地图着色使相邻两块不同色、解一道数独。这些是约束满足问题（CSP）：一组变量，每个都有一个可能取值的论域，外加说明哪些组合被允许的约束。

你用聪明的回溯来解它们——赋一个变量、检查约束，一碰到死路就立刻退回—— 并由约束传播加速，它在你尝试之前就把其他变量论域里不可能的取值剪掉。 CSP 是一把优雅而通用的锤子：数量惊人的真实规划与分配问题，只是披着外衣的 CSP。

逻辑与知识

符号 AI 的另一根支柱，是把知识表示成机器能用来推理的形式。命题逻辑处理由连接词（与、或、非、蕴含）连接的真/假事实；给定一些事实和规则，推理机械地导出同样必然为真的新事实。「正在下雨」加上「若下雨则地面湿」蕴含「地面湿」——而机器能一步步证明这一点。

命题逻辑是有限的——它无法泛泛地谈论对象与关系。一阶逻辑加入了变量、量词（「对所有」「存在」）和谓词，于是你可以把「每个人都有一位母亲」陈述一次，而不必为每个人逐一列举。这是知识表示、专家系统，以及至今仍支撑搜索引擎与结构化推理的知识图谱的基础。

规划与智能体

规划把搜索和逻辑系在一起：给定一个起始状态、一个目标，以及一组动作（每个都有前提条件和效果），找到通向目标的动作序列。它是在世界状态空间中的搜索，由对每个动作所做之事的逻辑描述来引导——比如一个机器人如何决定堆积木的顺序，或一个物流系统如何排定配送次序。

整个领域的统一框架是智能体循环：感知环境、决定一个动作（用搜索、逻辑、规划或一个学习到的模型中的任意一种）、行动，并随着世界的回应而重复。

智能体循环。一个智能体感知环境、推理以选择一个动作、对世界施加行动，并感知结果——这个循环框定了每一种 AI 技术，无论经典还是学习而来。

它在我工作中的体现

60 秒回顾

经典（符号）AI = 通过搜索、逻辑与规划进行推理；理性智能体（感知 → 决定 → 行动）框定了这一切。
许多问题 = 在状态上搜索。无信息：BFS（最浅、占内存）、DFS（轻、不最优）、UCS（最便宜路径）。
有信息搜索使用启发函数。A* 扩展最小的 $f(n)=g(n)+h(n)$ ；当 $h$ 可采纳（从不高估）时最优。
博弈：极小化极大（你的回合取最大，对手的回合取最小）+ alpha-beta 剪枝，同样的答案，工作量小得多。
CSP（在约束下赋值）→ 回溯 + 约束传播。逻辑（命题 → 一阶）表示知识并推出新事实。
现代 AI 保留智能体循环，并把「决定」盒子换成一个学习到的模型——最好的系统把搜索与机器学习结合起来。