状态空间搜索（state-space search）
/ STAYT-spays surch /
状态空间搜索，是AI解决问题的一种根基性方式：把问题看成在一座巨大的「可能性迷宫」里寻找一条路径。你可能身处的每一种局面都是一个「状态」；你能采取的每一步移动，都把你从一个状态带到另一个；而解决问题，就是找出一串从「起点」到「你想去之处」的移动。想想数字华容道：每一种拼块的摆法都是一个状态，每一次滑动都是一步移动，而搜索就是去寻觅那串能拼出目标图案的移动。
把它摊开来说，一个搜索问题有四个部件：一个起始状态、一组在状态之间移动的动作、一个告诉你「到没到」的目标测试，以及（常有的）每一步移动的代价，好让你能偏好更省的路径。所有可达状态构成的那整张网，就是「状态空间」。一个搜索算法会系统地探索这个空间——从起点向外铺开，记下自己去过哪里，一步步朝目标推进。不同策略以不同次序探索：有的求广，有的求深，有的则顺着一个启发式，优先奔向最有希望的状态。
它的重要性有两重。从历史看，把智能框定为搜索，是AI最早的几个大想法之一——下棋、寻路、规划、解谜，全都套得进这个模子，它也在符号时代支撑了一批经典系统。从实用看，它至今仍在路线规划器、物流排程器和游戏AI底下运转。它的硬性极限在于规模：状态的数目往往会组合式地爆炸（一盘棋的局面，比可观测宇宙中的原子还多），所以在大问题上，纯粹的蛮力搜索毫无指望。正是这种爆炸，让启发式——关于「该优先探索哪些状态」的聪明猜测——成了必需，而非可有可无。
把解魔方当作搜索：魔方的每一种打乱状态都是一个状态；每一次转动一面都是一个动作；目标测试是「每一面都是同一种颜色」。从任何一个状态出发，都有18种可能的转法，于是可达状态会膨胀到天文数字。盲目的搜索永远做不完——这正是求解器为何要倚仗启发式与结构，才能锁定解法。
状态、动作与目标测试——以及那场让启发式成为必需的组合爆炸。
状态空间搜索的致命敌人是组合爆炸：现实问题的状态数多到天文级，穷举搜索因而不可能。这正是启发式——把搜索朝有希望的状态修剪——并非奢侈品的原因：正是它，才让搜索压根儿能用起来。