搜索策略

现实中的许多智能问题——下棋、路径规划、定理证明、魔方复原——都没有直接套用的公式，而需要在大量可能的选择中试探。这种为了达到目标，不断从可用操作中选择并执行、直到找到解答的过程，就是搜索（Search）。搜索是问题求解的主要手段，也是推理过程的内在机制。

状态空间表示法

状态空间法把问题形式化为三元组 (S, F, G)：

• 状态（State）：描述问题在某一时刻所处格局的数据结构，记为状态变量的有序集合 Q = (q1, q2, …, qn)。S 是所有可能状态的集合；
• 算符（Operator）：使问题从一种状态变为另一种状态的操作（走法、规则、动作），F 是算符集合；
• 目标（Goal）：G ⊆ S 是满足终止条件的目标状态集合。

状态空间可直观地表示为一张有向图：节点是状态，边是算符。问题求解就是在图中寻找一条从初始状态 S₀ 到某个目标状态的路径。以 15 数码（4×4 滑块）为例：一种盘面排列是一个状态，"空格上/下/左/右移动"是四个算符，目标是还原成有序盘面。

问题归约表示法

另一种思路是"分而治之"：把复杂问题分解为若干较简单的子问题，子问题再继续分解，直到成为无需再分、可直接求解的"本原问题"。子问题间存在"与"（全部要解出）和"或"（任选其一）关系，整体结构表示为与或图（与或树）。例如证明几何题时，可把"证明两三角形全等"归约为"证明三边相等 或 两边及夹角相等 或 两角及一边相等"，而每个条件本身又是一个需要证明的子问题。

无论哪种搜索，算法通常维护两张表：OPEN 表存放已生成但尚未考察的节点，CLOSED 表存放已考察过的节点；搜索策略的差异本质上就是"OPEN 表按什么顺序取出下一个节点"的差异。

广度优先搜索（BFS）

从初始节点开始，先扩展同一层的所有节点，再扩展下一层。实现上把新节点放在 OPEN 表末端（队列 FIFO）。

• 特点：逐层推进，像水波一样扩散；
• 性质：在每步代价相同的情况下，一定能找到最短路径（最优解），是完备的；
• 代价：节点数随深度指数增长，空间占用大，是典型的"时间换完备"。

深度优先搜索（DFS）

每次都向最新生成、最深的节点方向探索，走到尽头再回溯。实现上把新节点放在 OPEN 表前端（栈 LIFO）。

• 特点：一条路走到黑，存储只需保存当前路径上的节点，空间开销小；
• 性质：若图中存在无限深支路，可能陷入其中而找不到解——不完备；找到的解也不一定最短；
• 改进：有界深度优先设定深度界限 d_m，超限即强制回溯，兼顾二者。

代价一致搜索（Dijkstra 思想）

当各算符代价不同（路程、费用不等）时，每次从 OPEN 表中取出从起点累计代价 g(n) 最小的节点扩展。它是广度优先在加权图上的推广，能找到总代价最小的最优解。

盲目搜索的共同问题是不利用任何问题知识：八数码中"哪个盘面更接近目标"这样显而易见的信息被完全浪费，搜索树迅速膨胀。启发式搜索正是为解决这一问题而生。

启发式（Heuristic）即"凭经验发现"的方法。启发式搜索把与问题有关的经验性知识编码为估价函数，让搜索优先朝"最有希望"的方向推进，从而大幅减少被考察的节点数。

估价函数

估价函数 f(n) 用于估计从起点经过节点 n 到达目标的"希望程度"，经典形式为：

每次从 OPEN 表中选 f(n) 最小的节点扩展。g(n) 与 h(n) 的权重决定了搜索风格：

• 只看 g(n)（h=0）→ 退化为代价一致搜索，稳但慢；
• 只看 h(n)（g=0）→ 贪心最佳优先搜索，朝着目标直线俯冲，快但可能被障碍误导而不最优、不完备；
• 二者兼顾 → A 算法；当 h(n) 满足可采纳条件时，即为 A* 算法。

A* 算法及其可采纳性

设 h*(n) 为从 n 到目标的真实最小代价。若启发函数满足：

则称 h 是可采纳的（Admissible），相应的 A 算法称为 A* 算法。在树搜索/配合 CLOSED 表的图搜索中，A* 保证一定找到最优解，并且只要解存在就能找到（完备）。直观理解：h 从不夸大剩余代价，因此真正最优路径上的节点不会被错误地排到队尾。

进一步，若两个启发函数满足 ha(n) ≤ hb(n) ≤ h*(n)，则称 h_b 比 h_a 更有信息量（占优）——用 h_b 搜索扩展的节点不会更多。曼哈顿距离对不在位将牌数就是占优的。常见可采纳启发函数还有网格寻路中的曼哈顿距离（四方向移动）、欧几里得直线距离（可任意方向移动）。

A* 的思想广泛用于游戏寻路（NavMesh、Waypoint）、机器人路径规划、GPS 导航等。其主要代价是 OPEN 表通常需要优先队列维护，且大规模地图上空间开销可观；IDA*（迭代加深 A*）、加权 A*、Jump Point Search 等是常见改进。

对于问题归约得到的与或树，"找到一个节点"不再等同于"问题得解"：一个或节点只要有一个子节点可解即可；而一个与节点的所有子节点都必须可解。由此需要在与或树上寻找解树（解图），并用代价评估各解树的优劣。

解树的代价常用两种定义（设 c(n, n_i) 为边代价，叶节点代价为 0 或给定 h 值）：

• 和代价：与节点 h(n) = Σ[ c(n, n_i) + h(n_i) ]；或节点取使总代价最小的一支；
• 最大代价：与节点 h(n) = max_i[ c(n, n_i) + h(n_i) ]；或节点同样取最优分支。

与或树的有序搜索（AO* 算法）每次选择当前最有希望的局部解图扩展，并自下而上反复修正节点代价与"最佳子节点"指针，直到选出完整解图。AO* 与 A* 的关键差异在于：与节点要求多支并行求解，代价信息必须沿解图整体回传，故不能简单套用单路径的 A*。

下棋是典型的对抗性搜索：对手会千方百计破坏你的计划。在双人零和、信息完全、轮流行动的博弈（如象棋、围棋、井字棋）中，可以把对弈过程组织成一棵博弈树：我方节点（MAX 节点）选择使评估值最大的走法，对方节点（MIN 节点）选择使评估值最小的走法。

极大极小分析法（Minimax）

α-β 剪枝

完整 Minimax 树的节点数随深度呈指数增长。α-β 剪枝在不改变结果的前提下跳过那些绝不可能影响最终决策的分支：

• α 值：MAX 节点目前能够保证获得的最高分值（下界）；
• β 值：MIN 节点目前能够保证压到的最低分值（上界）；
• α 剪枝：在 MIN 节点中，若其当前值 ≤ 祖先 MAX 的 α，则该分支再小也不会被选中，剪掉；
• β 剪枝：在 MAX 节点中，若其当前值 ≥ 祖先 MIN 的 β，则该分支再大也无意义，剪掉。

着法生成顺序越合理（好棋优先），剪枝效率越高，理想情况下同样时间内可搜索深度约增加一倍。深蓝、象棋引擎主要依赖"α-β 剪枝 + 高效评估函数 + 开局库/残局库"；而围棋状态空间过大、难以构造静态评估，AlphaGo 改用蒙特卡洛树搜索（MCTS）结合深度神经网络来选择落子。

下面的演示把本章四种搜索算法放进同一张网格地图：绿色 S 为起点，红色 G 为终点，深灰方块为不可通行的障碍。淡金色方块表示进入 OPEN 表（待考察）的节点，青绿色方块表示已进入 CLOSED 表（已扩展）的节点，金色折线为最终路径。你可以亲手绘制障碍、移动起止点，并对比四种算法的扩展节点数与路径长度。