状态空间表示法详解：从四要素拆解到搜索算法实战

我最近在帮几个同学看人工智能导论作业的时候，发现很多人卡在了“状态空间表示法”这一节。说实话，这个知识点在整本教材里属于那种“看着简单，做起题来全是坑”的内容。考试要考，大作业要用的搜索算法也建立在它之上，甚至后面学强化学习、规划算法，回头看的还是这一套东西。所以这篇文章我打算把它彻底讲透——从定义到四要素拆解，从手把手建模型到经典案例实操，最后再聊聊那些教材上不会写的容易出错的地方。

这篇文章适合正在学人工智能基础、准备人工智能大作业或者考研复习的同学阅读。我会用尽量直白的语言把“状态空间表示法”这件事讲明白，保证你看完不仅能应付作业和考试，还能建立一套真正可用的建模思维方式。

1. 状态空间表示法到底解决什么问题

1.1 从走迷宫说起：问题求解的第一性原理

我们先抛开各种定义不谈，想一个最简单的情景：你在一个迷宫里，从入口走到出口。不管这个迷宫是纸上的、现实中的还是游戏里的，你解决这个问题的过程其实都可以抽象成三个要素——你在哪里（位置信息）、你能怎么走（动作规则）、哪里是终点（目标判定）。

你脑子里想的“下一步往哪走”，就是在不停地做一件事：根据当前位置选一个动作，得到一个新位置，再看看新位置是不是终点，不是的话继续重复。这个过程放到人工智能里，就叫“状态空间搜索”。

我个人的理解是：状态空间表示法的本质，就是把一个实际问题翻译成计算机能理解和操作的形式化描述。你有一个初始状态，有一组可以执行的动作，有明确的目标条件，然后机器通过尝试各种动作组合，在“状态空间”里找到一条从起点到终点的路径。整个过程的核心就是三个问题：我现在在哪、我能做什么、怎么算成功。

1.2 形式化定义：状态、算符、状态空间与目标

教材上通常会把状态空间表示法定义成一个四元组或者类似的数学结构。当年我也觉得这些符号看得人头大，但后来发现，如果把它理解成三个卡槽，难度就直线下降。

状态空间表示法一般由四部分构成：

（1）状态：描述问题在某一时刻的状况，用一组变量或数据结构来表示。

（2）算符（也叫操作符或动作）：让状态发生改变的操作，有“可用条件”和“执行结果”。

（3）状态空间：从初始状态出发，所有可以通过算符到达的状态组成的集合，加上状态之间的转移关系，构成一个有向图。

（4）目标状态：判定问题是否解决的条件。

这里最关键的认知转变在于：“状态空间”不是事先列好的清单，而是由“初始状态”和“算符”共同生成的。就像给你一副扑克牌和一个洗牌动作，你不断执行这个动作，可能产生的所有牌序就是状态空间。你不需要把所有的牌序都提前写出来，只要知道起点和规则，就能在需要的时候逐步展开。

有了这四个要素，任何问题都可以统一到同一个求解框架下：“给定初始状态和算符集合，搜索一条到达目标状态的路径。”这就是为什么叫“表示法”——它本身不直接给出答案，但提供了一套建模的语法和思维范式。

2. 核心四要素逐个拆解：从抽象定义到具体例子

2.1 状态（State）：怎么描述一个问题在“某一时刻的样子”

状态的选取是整个表示法中最需要经验的一步。同样一个实际问题，状态选得好不好，直接影响后面搜索的效率甚至可行性。

举个最常见的例子——八数码问题（华容道的数字版），3乘3的九宫格里有8个数字滑块和一个空格，目标是把数字摆成指定顺序。这个问题的状态怎么表示？最直接的办法是把整个九宫格看成一个三元组结构，每一行是一个向量，三行拼在一起就是当前局面。例如初始状态可以记为[[2,8,3],[1,6,4],[7,0,5]]，其中0代表空格。

再比如经典的传教士与野人问题：三个传教士和三个野人要过河，小船一次最多坐两人，任何时候在任意岸边野人数量不能超过传教士数量。这个问题的状态可以这样定：用一个二元组(m, c)表示左岸传教士人数和野人人数，再加上一个布尔变量表示船在左岸还是右岸，合起来(m, c, b)就是一个完整的状态。为什么不用记录右岸的人数？因为总人数是固定的，右岸的人数可以用总数减左岸人数算出来，没必要重复存储。

这里有两条实操中我反复跟人强调的经验：

• 状态不是越详细越好，要“够用且最小”。只要能从状态中恢复出整个问题的全部信息就行，多余的信息都是浪费计算资源。
• 状态需要满足“马尔可夫性”——从当前状态出发能否继续推导，不依赖于历史信息。也就是说，同一个状态下，不管之前走过什么路径，未来可选的动作都应该是一样的。如果做不到这一点，说明你的状态设计有遗漏。

2.2 算符（Operator）：动作规则是状态转移的唯一驱动力

有了状态，还需要定义动作。算符通常写成前置条件和效果两个部分：什么条件下可以用这个动作，用了之后状态怎么变。

以八数码为例，跟空格相关的动作有四个：空格上移、下移、左移、右移（等价于把某个数字滑块移入空格）。每个算符都有适用条件：空格在第一行时不能上移，在最后一行时不能下移，在最左边时不能左移，在最右边时不能右移。这些边界条件必须写清楚，否则搜索过程会产生非法状态。

传教士与野人问题的算符就要复杂一点了。船上的组合可以是1个传教士、1个野人、2个传教士、2个野人或者1传1野这五种合法情况。每个算符也要考虑船的当前位置——船在左岸时，算符的效果是从左岸划到右岸；船在右岸时则相反。执行算符之后还要立刻判断两岸是否满足“野人不过多”的约束，不满足就直接丢弃这个操作。

我在给同学辅导时经常打这样一个比方：状态是游戏存档，算符是操作按钮，游戏规则决定哪些按钮在哪些情况可用、按了之后存档变成什么样。你不需要把整个游戏的结局背下来，只需要从初始存档出发，不断按合法的按钮，找一条通向通关存档的路就行。

2.3 状态空间：从起点开始“生长”出来的有向图

状态空间可以看作一张有向图，节点是状态，边是算符。从初始状态出发，每应用一次算符就产生一个新节点，不断重复这个过程，整棵搜索树就长出来了。

这里要区分两个概念：搜索树和状态空间图。搜索树会包含重复节点，因为同一个状态可能通过不同的路径到达（比如八数码中先左移再右移会回到原始状态）；状态空间图则把所有位置相同的节点合并成一个。写代码时通常会维护一个“已访问集合”来避免重复扩展，相当于从这个图中剪掉重复的枝丫。

构建状态空间的时候，大多数人会忽略一个关键问题：状态空间的规模到底有多大？还是用八数码举例，9个格子放8个数字加1个空格，排列总数是9的阶乘，也就是362880种状态，这个规模用BFS直接搜完全没问题。但如果你把规模往上提一点，变成4乘4的十五数码，状态数就到了16!，约2.09乘以10的13次方，这时候裸搜就完全行不通了，必须引入启发式搜索。所以每次建模前先估算一下状态空间的量级，是决定后续搜索策略的重要依据。

2.4 目标状态：怎么写判定条件才不出错

目标的定义看起来最简单——把初始状态和目标状态放一起比较就完事了。但实际做题时，目标状态的定义有一个常见的坑：有些目标条件是约束性的，而不是一个具体的状态。

比如八数码的目标是某个具体的排列，这很好判断。但传教士与野人问题的目标就写“所有人到达右岸”，换算成状态就是(0, 0, 0)——左岸没人，船在右岸。再比如一些约束满足问题，目标可能是“任意相邻节点颜色不同”，这种就不能用简单的等于某个状态来判断了，必须写一个布尔判定函数。

我推荐在动手写搜索代码之前，把目标判定单独抽象成一个函数isGoal(state)，这样以后扩展问题或者换搜索算法时，不需要动其它代码。这也是一个很好的工程习惯——表示、搜索、判定三层解耦，一层一层的修改成本最低。

3. 从表示到求解：搜索就是在这个空间里找路

3.1 深度优先与广度优先：何时选哪种

表示法搭好之后，求解就交给搜索算法了。AI导论课程里最先接触的两种无信息搜索策略是深度优先搜索（DFS）和广度优先搜索（BFS）。

BFS的核心思想是一层一层往外扩展，先扩展初始节点的所有邻居，再扩展到邻居的邻居。实现上用队列，先进先出。优点是只要解存在，一定能找到且找到的是步数最少的解；缺点是内存消耗大，因为每一层的节点都要被存下来。八数码用BFS没问题，但碰到状态空间很大的问题就会内存爆炸。

DFS则是沿着一条分支一直往下走，走不通了再回头换一条路。实现上用栈，后进先出。优点是内存占用小，只要保存当前路径上的节点；缺点是不保证找到最短路径，甚至可能一头扎进很深的死胡同里浪费大量时间。为了缓解这个问题，实际项目中常用“迭代加深”（Iterative Deepening DFS）——反复用DFS，但每次限制一个最大深度，一层层加深直到找到解。

我的建议是：初学阶段拿八数码练手时，两种都写一遍，对比一下它们扩展的节点数和内存占用，你就能直观感受到“算法策略对搜索开销的影响”这件事有多明显。

3.2 启发式搜索：用好“方向感”帮你抄近路

无信息搜索在状态空间大的时候几乎是寸步难行的。这时候就要请出A*算法为代表的启发式搜索。

A在BFS的框架基础上加了一个评价函数：f(n) = g(n) + h(n)。其中g(n)是从起点到当前节点n已经花费的实际代价，h(n)是从节点n到目标节点的估计代价（也叫启发函数）。A每次从优先队列里取出f(n)最小的节点进行扩展。

关键就在h(n)怎么设计。以八数码为例，一个常用的启发函数是“曼哈顿距离之和”——每个数字当前的位置到目标位置需要横着走几步加竖着走几步，把所有数字的这个值加起来。这个启发函数满足可采纳性（不会高估实际代价），所以A*用它能保证找到最优解，而且比BFS快得多。

我来手算一个简单例子。假定某个数字3在位置(0, 1)，它在目标状态中的位置是(2, 0)，那它的曼哈顿距离就是|0-2| + |1-0| = 3。把所有数字的曼哈顿距离求和，就得到了当前状态的h(n)值。这个计算非常轻量，但信息量很大——它度量了当前局面“离目标还有多远”的直观感觉。

很多同学问：为什么不用“位置不同的数字个数”当启发函数？当然可以，它也是可采纳的，但它的信息量比较小。可以想一下，两个状态分别有4个和5个数字位置不对，它们之间的距离差别可能很大，但“错位数”这个指标区分不出来。相比之下，曼哈顿距离能提供更细腻的估计，搜索效率会高很多。

3.3 搜索框架的工程细节：OPEN表、CLOSED表和访问标记

纸上谈兵了这么多，我把一个通用搜索框架的伪代码写在这里，方便大家用来做作业或者复现实验。以A*为例：

• 初始化OPEN表（优先队列），把初始状态放进去，g = 0，计算h，得到f。
• 初始化CLOSED表或visited集合，用来记录已经扩展过的状态。
• 循环：如果OPEN表为空，搜索失败返回无解；取出f值最小的节点；如果是目标节点，沿着父指针回溯输出路径；否则生成该节点的所有后继状态，逐个检查是否在CLOSED中，不在的就计算g/h/f后放入OPEN表。
• 如果后继状态已经在OPEN表里，但新的g值更小，就更新它的g/f值和父指针。

有几个工程细节值得多说一句：

关于状态编码。不管你的状态内部结构是什么样，放进visited集合的时候最好转成一个可哈希的字符串或元组。比如八数码可以把整个九宫格扁平化成一个元组(2,8,3,1,6,4,7,0,5)，这样查重的时间复杂度是O(1)。

关于解路径的恢复。扩展过程中每个节点都要记录“父节点是谁”以及“用了哪个算符到达这里”，找到目标后从终点一直回溯到起点，再反转，就得到了完整路径。这个环节漏掉父指针的话，找到目标也拿不出路径来，作业里这种问题很常见。

4. 经典案例实操：三个问题看懂状态空间建模全流程

4.1 八数码问题：从状态定义到A*求解全流程

我第一次觉得状态空间表示法真正“通了”，就是把八数码从建模到求解一口气写完的时候。我来完整演示一遍流程。

第一步，状态表示。用三元组表示九宫格，0代表空格。例如：

• 初始状态：s0 = (2, 8, 3, 1, 6, 4, 7, 0, 5)
• 目标状态：goal = (1, 2, 3, 8, 0, 4, 7, 6, 5)

第二步，算符定义。根据空格位置生成可行动作。空格在位置index，对应的行是index // 3，列是index % 3。如果行大于0，空格可以和上方的数字交换；如果行小于2，可以向下；列大于0可以向左；列小于2可以向右。

第三步，启发函数。我用曼哈顿距离，对每个非0数字算一遍当前位置和目标位置的曼哈顿距离，求和作为h(n)。

第四步，搜索。用优先队列作为OPEN表，以f = g + h排序。每次取出最小f节点展开，直到目标。

这一步走下来，你会看到A扩展的节点数比BFS少了不止一个数量级。我实际算过一个比较难的初始局面，BFS可能扩展几万个节点，A几千个甚至几百个就出结果了。这种对比我建议你亲自动手跑一遍，那种“知识变成工具”的感觉就出来了。

4.2 传教士与野人问题：约束条件下状态表示的技巧

传教士与野人问题在AI导论里出镜率极高，因为它比八数码多了一层约束逻辑。

状态表示：(m, c, b)，分别代表左岸传教士人数、左岸野人人数、船的位置（1表示左岸，0表示右岸）。初始状态是(3, 3, 1)，目标状态是(0, 0, 0)。

算符设计就五种摆渡组合：1个传教士过去、1个野人过去、2个传教士过去、2个野人过去、1传1野过去。每一种动作都要根据船的位置做方向判断——船在左岸时人数减少，船在右岸时人数增加。

每次执行完算符后，要立刻检查约束条件：

• 任何一边的人数都不能是负数，也不能超过总数。
• 如果左岸传教士人数在1到2之间（即传教士不完全在左岸也不完全在右岸），左岸传教士人数必须不少于野人人数。
• 右岸同理。

这个问题的搜索空间比较小，用BFS几分钟就能找到最短路，路径长度我记得是11步。做好状态判定之后，整个搜索过程其实非常快，很适合用来验证你对“状态”、“算符”、“约束”三者的理解是否到位。

4.3 旅行商问题（TSP）：状态空间表示法的现实重要应用

TSP属于组合优化的经典问题，也大量用到状态空间表示法。城市集合{A, B, C, D}，一个状态可以记为“当前所在城市”加上“已经访问过的城市集合”。

比如(C, {A, B, C})表示现在人在C城，已经走过A、B、C三个城市。算符就是在未访问过的城市中选一个作为下一站，代价是两地之间的距离。目标状态是访问完全部城市并返回起点。

TSP的状态空间有多大？把已访问集合看成位掩码，n个城市的状态总数是n * 2^n量级。这就是状态压缩动态规划的经典方程：

dp[mask][i] = min(dp[mask without i][j] + dist[j][i])

第一次看到这个式子时可能觉得抽象，但如果先从“状态”这个角度去理解：(mask, i)就是一种状态表示，dp就是在状态空间里做最短路径搜索。你会发现原来数据结构和算法课上学的东西，跟人工智能导论里的状态空间表示法完全是同一套思维。

5. 常见问题与避坑速查：这些坑我替你们踩过了

5.1 状态爆炸与搜索效率：为什么我的程序跑不出来

状态爆炸是搜索问题中最常见的困境。处理方法有下面几个方向：

• 优化状态表示，压缩冗余信息。比如上面说的右岸人数不用记录就能算出来，这属于状态编码层面的压缩。
• 避免重复扩展，visited集合一定不能省。没有查重的话，搜索树里大量重复节点会让时间呈指数增长。
• 更换搜索策略，由BFS换成启发式搜索。同样的八数码问题，启发函数选得好不好，速度差距可能是上百倍。
• 对状态做对称性剪枝。有些问题的对称状态其后续搜索结果完全一致，只保留一个即可。

5.2 建模时最容易忽略的四个细节

我总结了几个新手特别容易踩的坑，整理成了表格，方便大家对照自查：

5.3 无解的判定策略：处理不可达状态和环路

还有一个实操上经常遇到的问题是：如果问题本身无解，程序怎么停下来？比如八数码的某个初始局面就是无论怎么移动都无法到达目标，因为八数码的可达状态空间只有一半的排列。

这时候如果程序不做终止判定，BFS会一直扩展直到状态穷尽，然后OPEN表为空退出。这个机制本身就保证了无解情况下的正常终止，但要注意：如果状态空间很大且无解，内存会先撑不住。

所以我的建议是：在搜索之前如果能通过理论分析判断解的可行性（比如八数码可以预先计算逆序数奇偶性），就直接在前期拦截掉，省得浪费时间。

此外，环路问题也不容忽视。不查重的话，A算法可能在两个状态之间来回横跳，永远到达不了目标。对搜索树或者图来说，这是一个细节但很重要的实现点——在执行算符后立即检查新状态是否已经在CLOSED表或当前路径中。

6. 状态空间表示法之外：与其它知识表示方法的横向对比

6.1 为什么有了状态空间还要学谓词逻辑、产生式系统

看到这里你可能会想：状态空间表示法这么万能，为什么《人工智能导论》还要花大篇幅讲谓词逻辑、产生式规则、框架表示、语义网络这些东西？

原因是不同的问题适合不同的表示方法。状态空间擅长表达“一步步操作”的过程性知识，但表达“人类知道的事实”类知识就很别扭。比如“所有的鸟都有翅膀”这种一般性知识，用谓词逻辑一句话就写清楚了；但用状态空间去表达这种知识，你得构造状态和算符，非常不自然。

产生式系统擅长表示“如果-那么”形式的规则，适合专家系统；框架表示适合表达对象的属性层级关系；语义网络强调概念之间的语义联系。每一种表示法都有自己的适用面。它们的底层逻辑其实相通，都是“选择合适的结构化方式，把现实问题的关键信息编码成计算机可操作的形式”。

6.2 学完这一节之后的路：从课程作业到前沿AI

状态空间表示法是整个人工智能体系的地基。往近了说，强化学习里的马尔可夫决策过程（MDP）本质上就是状态空间表示法加上奖励函数和转移概率；机器人路径规划里的配置空间（Configuration Space）也是状态空间思想的直接延伸；现在热门的具身智能里，机器人要学会在真实物理环境中做动作决策，底层同样需要对“当前状况-动作-下一状况”做建模。

所以如果你在学这一节时觉得知识很抽象，我的建议是：不要急，先老老实实把八数码和传教士野人问题每个细节都搞明白，动手写一遍代码，然后再回去看那些复杂的概念，会发现它们其实都长着差不多的骨架。

结语碎碎念：怎么判断自己真的学会了

写到这里，这篇关于状态空间表示法的内容也就差不多结束了。最后分享一个我自己检验“是否真学会”的小方法：找一个新的、没做过的搜索问题（比如倒水问题、农夫过河问题），不看任何参考，独立完成状态建模、算符设计和搜索实现。如果你能顺利走完这个过程，说明这一节的知识已经不再是书本上的概念，而是长在你脑子里的工具了。

另外一个建议是，平时看别人代码或论文时，拿到一个算法先别急着直接看代码，先问自己三个问题：它的状态是什么？算符有哪些？目标怎么判定？把这三件事想清楚后，再去看实现，整个逻辑会变得非常清晰。

希望这些内容能对你的学习有帮助。如果你在状态空间建模的过程中还有其它搞不明白的地方，或者发现了更有意思的建模思路，欢迎在评论区一起交流探讨。