搜索与规划

搜索与规划是符号主义 AI 的第一个分支：把问题表示为状态空间（State Space，一个问题所有可能取值的集合）或动作序列，通过显式搜索而非数据学习来求解。这类方法的核心信念是——智能的本质就是在巨大的可能性空间里高效地找到正确的那条路。

从 1968 年 A* 算法为 Shakey 机器人寻路而诞生，到 1997 年 Deep Blue 用对抗搜索击败国际象棋世界冠军，再到 2024 年 AlphaProof 用 MCTS + 形式语言解决国际数学奥林匹克（IMO）题目，搜索与规划始终是 AI 最经久不衰的范式之一。即便在大模型时代，“搜索”依然是推理时计算（inference-time scaling）的核心机制——OpenAI o1、DeepSeek R1 等”推理模型”在内部反复探索思维链的可能分叉，本质仍是搜索。

核心直觉

搜索算法的本质是在一张”状态图”上找路——图中的节点（node）表示某个状态（棋局、机器人位置、问题中间态），边（edge）表示一个动作或状态转移。算法从初始状态出发，沿着边不断扩展，直到抵达目标状态（满足终止条件的状态）。不同策略的区别在于”先探索哪条路”，这决定了它是否完备（解存在时能否找到）、是否最优（找到的解是否代价最小）、以及时间空间开销：

BFS（广度优先，Breadth-First Search）= 像水波一样一圈圈向外扩展——保证找到步数最少的路径（完备且最优），但需要把整层节点都存进内存，开销随层数指数增长。
DFS（深度优先，Depth-First Search）= 一条路走到黑，碰壁了再回退——内存只需存当前路径（空间复杂度 $O(\text{深度})$ ），但不保证最优，在无限深的状态空间里甚至可能不收敛。
Dijkstra= BFS 的加权版本——按”累计代价”从小到大扩展，能找到加权图上的最短路径，是路由、网络最短路径的基石。
A*= 带”GPS 预估”的 Dijkstra——既考虑已走代价 $g(n)$ ，又用启发函数 $h(n)$ 预估到终点还剩多远，效率最高；当 $h(n) = 0$ 时就退化成 Dijkstra。
Minimax= 下棋时的”我最优，对手最劣”博弈——轮流假设对方会选对你最差的一步，在博弈树（game tree）上向下交替取最大值/最小值。

原理图解

A* 寻路：网格上的最短路径

A* 的评价函数 $f(n) = g(n) + h(n)$ ，其中：

$g(n)$ ——从起点到节点 $n$ 的实际已走代价（精确值，随搜索推进不断更新）。
$h(n)$ ——从 $n$ 到终点的启发式估计（如曼哈顿距离、欧几里得距离），是”乐观猜测”。
$f(n)$ ——经过 $n$ 这条路”可能的总代价”的下界，算法始终优先扩展 $f$ 最小的节点。

A* 的正确性关键在一个性质： $h(n)$ 必须是”可采纳的”（admissible，即绝不高估真实代价）。直觉是——只要估计值不报喜不报忧（偏低），算法就不会过早放弃真正最短的那条路。如果 $h$ 进一步满足”三角不等式”（即一致性/单调性，consistent），那么每个节点最多被扩展一次，效率更高。

A* 每次从”待探索”列表（称为 open set / frontier）中选 $f$ 值最小的节点扩展——这就是**优先队列（最小堆，min-heap）**的经典应用场景。理论上，没有任何”同等信息量”的算法能在最坏情况下扩展更少的节点（这是 Dechter & Pearl 1985 关于 A* 渐近最优性的结论）。

Minimax 博弈树

下棋时，你要选对自己最好的走法，同时假设对手会选对你最差的走法——这就是 Minimax（极小极大）。算法在博弈树上递归求值：你的回合（MAX 层）取子节点的最大值，对手的回合（MIN 层）取子节点的最小值，一直向下直到叶子节点用评估函数打分。

上面这棵树的根节点值是 8（而不是 12）——因为对手会阻止你走到评分 12 的分支，所以你能保底拿到的其实是中间那条路上的 8。这就是 Minimax 的精髓：在对手不犯错的前提下，求自己能保住的最优结果。

Alpha-Beta 剪枝是 Minimax 的核心优化：在搜索过程中维护一个窗口 $[\alpha, \beta]$ （ $\alpha$ 是 MAX 层当前能保证的下界， $\beta$ 是 MIN 层当前能保证的上界），一旦发现某条分支的结果不可能落在这个窗口内，就直接剪掉不再搜索。理想情况下能把搜索节点数从 $O(b^d)$ 降到 $O(b^{d/2})$ ——同样的算力下搜索深度翻倍。剪枝效率高度依赖走法排序：先搜好的走法能更早触发剪枝。

动手实践：A* 寻路算法

用 numpy 网格 + 优先队列实现 A*。核心数据结构有两个：g 字典记录每个节点的”当前已知最小代价”，came 字典记录每个节点的”前驱”用于最后回溯路径。主循环每次弹出 f 值最小的节点，若已是终点则回溯返回；否则对四方向邻居做”松弛（relaxation）“——如果经过当前节点到邻居更便宜，就更新代价并压回队列。

import heapq
import numpy as np

def astar(grid, start, goal):
    """A* 寻路：grid 中 0=可通行，1=障碍，返回最短路径坐标列表"""
    pq = [(0, start)]               # 优先队列：(f=g+h, 坐标)，最小堆
    g = {start: 0}                  # g[score]：起点到该点的实际最小代价
    came = {}                       # 前驱表，记录"从哪个节点走到这里"
    while pq:
        _, cur = heapq.heappop(pq)  # 取出 f 值最小的节点（best-first）
        if cur == goal:             # 到终点，沿前驱链回溯完整路径
            path = [cur]
            while cur in came:
                cur = came[cur]; path.append(cur)
            return path[::-1]       # 反转成"起点→终点"顺序
        # 对上/下/左/右四个方向的邻居做"松弛"
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nb = (cur[0]+dx, cur[1]+dy)
            ok = 0 <= nb[0] < grid.shape[0] and 0 <= nb[1] < grid.shape[1]
            if not ok or grid[nb] == 1:   # 越界或撞墙，跳过
                continue
            ng = g[cur] + 1                # 走一步代价为 1（四方向等价）
            if nb not in g or ng < g[nb]:  # 发现更短的路径
                g[nb] = ng
                h = abs(nb[0]-goal[0]) + abs(nb[1]-goal[1])  # 曼哈顿距离（可采纳）
                heapq.heappush(pq, (ng + h, nb))             # f = g + h 入队
                came[nb] = cur

# 测试：5×5 网格，中间有 L 形墙
grid = np.array([[0,0,0,0,0],[0,0,1,1,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0]])
print(astar(grid, (0,0), (4,4)))
# 输出形如 [(0,0),(0,1),(1,1),(2,1),(3,1),...,(4,4)]：绕过障碍墙的最短路径

为什么这里用曼哈顿距离作为 h？ 因为网格只允许四方向移动，“忽略障碍后的最少步数”恰好就是曼哈顿距离，它永远不超过真实步数，满足可采纳性。若改成八方向移动，应换成切比雪夫距离（Chebyshev distance）；若可在连续空间任意方向移动，则用欧几里得距离。

可采纳性的反例

如果把上面的 $h$ 改成”曼哈顿距离 $\times 5$ “（人为放大），A* 仍然会返回一条路径，但很可能不是最短的——它会过度偏向往终点方向”直冲”的那条路，被高估值误导而错过真正更优的迂回路径。这正是”启发函数必须可采纳”这一约束的实际意义：估计可以悲观（偏低），但不能乐观（偏高）。

搜索算法速查

类型	算法	核心思想	典型应用
无信息搜索	BFS / DFS / Dijkstra	按固定策略展开，不用领域知识	最短路 / 连通性
启发式搜索	A* / IDA* / D*	用 $h(n)$ 引导搜索方向	游戏寻路 / 机器人导航
对抗搜索	Minimax / Alpha-Beta	假设对手最优，最大化己方收益	棋类博弈
约束求解	CSP / SAT（DPLL、CDCL）	满足一组约束条件	排程 / 形式验证

实践要点

A* 的启发函数 $h(n)$ 必须是”可采纳的”（绝不高估真实代价），否则不保证最优。曼哈顿距离适合四方向网格，欧几里得距离适合自由移动场景。
Alpha-Beta 剪枝的效率取决于走法排序：先搜好的走法能剪掉更多分支。
大规模搜索用蒙特卡洛树搜索（MCTS）：当状态空间太大（如围棋），Minimax 不可行，AlphaGo 用 MCTS + 神经网络解决——这是神经符号混合的经典案例。

典型应用

游戏与博弈

游戏引擎寻路：Unity、Unreal Engine 内置的 NavMesh 寻路系统底层使用 A* 算法，让 NPC 和玩家角色在复杂地形中自动绕障行走到目标点，几乎所有 3D 游戏中的角色移动都依赖它。
棋类博弈引擎：Stockfish（国际象棋引擎，长期位居 Elo 榜首）使用 Alpha-Beta 剪枝搜索 + 精心设计的评估函数，每秒搜索数千万个局面；各类象棋、将棋开源引擎同样基于对抗搜索框架。

物流与机器人

物流路径规划：美团、京东等平台用 A* 及其变体在配送区域的路网图上为骑手和车辆规划最短或最快路径，同时叠加订单时效、交通拥堵等约束做实时优化。
自动驾驶与机器人导航：波士顿动力 Spot 机器人在未知地形上用 D* Lite 算法做增量式路径规划，遇到新障碍物时只重新搜索受影响的局部区域，实现高效的自主探索与避障。

典型类库与工具

类库	语言	说明
Z3	C++/Python	微软研究院的 SMT 求解器，可用于 SAT/约束满足问题求解与形式验证
OR-Tools	C++/Python/Java	Google 开源的组合优化工具包，内置路径规划、排程、CSP 与图算法求解器
python-constraint	Python	轻量级约束满足问题（CSP）求解库，适合教学和原型验证
networkx	Python	图算法库，提供 BFS、DFS、Dijkstra、A* 等图搜索与最短路径算法
MiniZinc	建模语言	声明式约束建模语言，搭配各类 CP/SAT 求解后端求解组合优化问题
PDDL 规划器（如 Fast Downward）	C++	自动任务规划领域的标准求解器，输入 PDDL 描述自动生成动作序列

术语表

术语	英文	解释
状态空间	State Space	所有可能状态的集合，搜索算法在其中寻找从初始状态到目标的路径
启发函数	Heuristic Function	对当前状态到目标剩余代价的估计函数，用于引导搜索方向（记为 $h(n)$ ）
可采纳性	Admissibility	启发函数绝不高估真实代价的性质，是 A* 保证最优解的前提
完备性	Completeness	如果解存在，算法保证能找到解的性质
最优性	Optimality	算法找到的解保证是代价最小的最优解的性质
对抗搜索	Adversarial Search	在博弈场景中假设对手最优、最大化己方收益的搜索策略（如 Minimax）
约束满足问题	Constraint Satisfaction Problem (CSP)	为一组变量赋值使其满足给定约束的问题，如排课、数独
规划领域定义语言	Planning Domain Definition Language (PDDL)	描述规划问题（动作的前提与效果）的标准语言，自动规划领域的通用接口