1. 状态空间图到底在描述什么状态空间图State Space Graph这个名字听起来唬人本质上就是一张把所有可能局面连起来的地图。你在解八数码、玩过河游戏、给扫地机器人规划路线、调 A* 走迷宫的时候脑子里其实都在画这张图。它把问题拆成两样东西一是局面长什么样二是从一个局面能走到哪些局面。前者叫状态后者叫算子两者加起来再加上初始状态和目标状态就构成了状态空间图的全部骨架。我第一次接触这个概念的时候最大的困惑不是定义而是为什么非要画成图。后来做多了才明白图只是形式真正有用的是它把一个看起来无从下手的智力题变成了一个可以机械执行、可以写代码、可以评估效率的标准流程。你不需要灵光一闪你只需要老老实实把状态列出来、把算子写清楚然后交给搜索算法。这就是人工智能里问题求解这一支的底层逻辑也是很多人学完人工智能导论之后唯一真正能带到工程里的东西。1.1 四个基本要素少一个图就建不起来一个规范的状态空间图问题必须同时说清四件事缺一件后面就会卡住。状态表示也就是局面用什么数据结构存。八数码可以存成 9 个字符的字符串123456780传教士与野人可以存成(左岸传教士数, 左岸野人数, 船的位置)这样的三元组倒水问题可以存成(壶A水量, 壶B水量)。表示方法选得好不好直接决定后面写代码是享受还是受罪。算子集合也就是从当前状态出发允许做哪些动作。八数码里是空格上下左右移动过河问题里是船载一两个人划到对岸倒水问题里是倒满、倒空、互相倒。算子必须写全漏一个就可能把唯一解给漏掉但也必须写准把不合法动作放进去会产生大量死状态。初始状态与目标测试。初始状态就是起点只有一个目标测试是一个函数输入状态返回真或假而不是只给一个固定目标——这一点在倒水问题里特别明显壶里正好有 4 升是一类状态不是唯一状态。路径耗散可选。如果每一步代价都是 1那就是 BFS 的主场如果每步代价不同比如不同路段长度不一样那就得用一致代价搜索或者 A*。1.2 状态空间图和搜索树不是一回事这是新手最容易混的地方我见过不止一个人把两者画成一张图然后整道题就崩了。状态空间图是问题的客观结构它不依赖你用什么算法也不依赖你怎么搜。同一个八数码问题谁来看这张图都是同一张节点不会重复A 状态到 B 状态那条边永远在那儿。搜索树是算法跑起来之后动态生成的东西。同一个状态可能在树里出现好几次因为你可以通过不同路径到达它。树是搜索过程的快照图是问题本身的地图。对比项状态空间图搜索树本质问题的完整结构算法展开的轨迹节点是否重复每个状态只出现一次同一状态可能多次出现规模固定由问题决定随算法和剪枝策略变化谁负责建模阶段搜索阶段典型问题状态爆炸重复展开、内存溢出搞清这个区别的现实意义在于状态空间图的规模是你建模时就决定了的改不了但搜索树的规模你可以通过去重、启发式、剪枝来压。很多人抱怨八数码太慢其实不是图太大是树被重复展开了。1.3 为什么一定要画成图直接暴力枚举不行吗可以但代价不一样。暴力枚举意味着你要生成所有状态再一个个检查复杂度是 O(|S|)其中 |S| 是状态总数。八数码的状态总数是 9! 362880去掉不可达的一半还有 181440暴力枚举勉强能忍。但换成 15 数码16! 大约是 2×10^13这已经不是慢的问题是这辈子算不完。图的意义在于它让你只需要沿着连通路径走而不是扫描整个空间。BFS 找到解只需要访问解路径附近的节点A* 加上好的启发式甚至能把访问量压到几千个。这就是把问题表示成图和把问题当成集合的根本区别。提示状态空间规模是所有搜索算法绕不过去的天花板。建模阶段就要估算 |S| 的量级如果已经超过 10^7就别指望无信息搜索了直接上启发式或者换建模方式。2. 建图之前状态表示和算子设计建模这一步做得好后面写代码就是体力活做得不好代码写完了还得推翻重来。我在课程作业和比赛里踩过的坑九成都能追溯到建模阶段。2.1 状态表示的三种常见形态第一种是元组或定长字符串适合分量个数固定、取值范围明确的问题。倒水问题用(x, y)传教士用(m, c, b)八数码用 9 位字符串。好处是天生可哈希直接丢进 Python 的set或dict就能去重不用写额外的哈希函数。第二种是集合或位掩码适合选没选过这类状态。旅行商问题里visited用 20 位整数表示 20 个城市的访问情况比元组省内存得多。汉诺塔也可以用三个整数表示三根柱子上的盘子分布。第三种是嵌套列表或对象可读性最好但有个致命问题不可哈希而且容易被浅拷贝坑。我见过有人用二维列表表示八数码棋盘然后写visited.add(board)报TypeError: unhashable type: list改成 tuple 才行。我的建议很直接能转成不可变类型就转。字符串和元组是首选位掩码是进阶选项对象和列表只在最后需要输出人类可读结果时临时转换。2.2 状态编码与哈希去重的第一道防线去重这件事听起来简单做起来能玩出花。三种常见做法用set存已访问状态查询 O(1)但只回答是否访问过用dict存状态 - 父节点顺便解决路径还原用dict存状态 - 最小代价 g这是 A* 和 Dijkstra 必须的三个可以合并成一个parent字典加一个g字典。别嫌内存去重省下来的节点数远比字典开销大。数据结构用途典型场景set只判重纯 BFS 只要步数dict父指针判重 还原路径需要输出移动序列dict代价判重 松弛A*、一致代价搜索双向 dict双向搜索状态数极大但解路径短2.3 算子设计的两条铁律第一算子必须对称可逆如果问题本身可逆。八数码里空格向左移反过来就是向右移两个算子必然成对出现。如果你只写了一半图就变成了有向图搜索方向也被钉死了。第二合法性校验要在算子内部完成而不是丢给搜索算法。空格在左上角时向上移和向左移这两个算子根本不存在正确的做法是在neighbors()函数里就过滤掉而不是生成一个越界状态再让搜索算法去处理。后者不仅浪费内存还可能引入难以排查的错误。我在实现传教士与野人时犯过一次典型错误算子里只检查了船上人数不超过 2忘了检查出发岸人数够不够。结果生成了一个左岸只有 1 个传教士却有 2 个野人上船的非法状态搜索跑出来的解在第三步就把人送没了。这个 bug 花了半小时才定位到因为非法状态本身不报错只是让答案变得莫名其妙。注意写算子的时候把每个动作的约束条件单独列一张纸逐条对应到代码里的 if 判断不要凭记忆写。3. 五道经典例题逐步拆解下面这五道题是状态空间图这条线上的必修课考试、作业、面试基本跑不出这个范围。我会把每道题的状态定义、算子、状态规模和解法思路完整列出来。3.1 例题一八数码问题问题3×3 棋盘上放着 1 到 8 八个数字和一个空格每次只能把空格上下左右移动一格问能否从初始布局变到目标布局。状态表示长度为 9 的字符串0代表空格。目标状态是123456780。算子空格与上下左右相邻格交换越界不生成。状态规模9! 362880 个排列其中一半不可达。可达状态数是 181440。这个数字很重要它意味着 BFS 在这道题上完全可行最多访问 18 万个节点。可解性判定把状态里除了空格之外的 8 个数字按行读成一个序列统计逆序对数量后面的数比前面小的次数。逆序数为偶数则可解奇数则不可解。这条规律对奇数宽度3×3成立对于 4×4 的 15 数码需要再加上空格从下往上数的行号判断逆序数 空格行号的奇偶性。我第一次看到逆序数规则的时候觉得莫名其妙的巧合后来理解了每次空格水平移动不改变数字序列垂直移动相当于把某个数字跨越两个位置改变逆序数 2所以奇偶性始终不变。而目标状态逆序数为 0 是偶数所以初始状态必须也是偶数才可达。这个判定在工程里非常实用。你不做判定直接上 BFS遇到不可解输入就会跑遍全部 181440 个可达状态然后返回无解白白浪费几秒钟。3.2 例题二传教士与野人过河问题3 个传教士和 3 个野人在左岸要全部到右岸。有一条船最多坐 2 人且任何一岸只要野人数多于传教士数传教士就会被吃掉。船至少要有 1 个人划。状态表示(左岸传教士数, 左岸野人数, 船的位置)船用 0 表示左岸、1 表示右岸。状态规模理论上 4×4×2 32 种组合去掉传教士被吃的非法状态和不可能的奇偶状态实际可用状态也就二十来个。算子从船所在的一岸选 (1,0)、(2,0)、(0,1)、(0,2)、(1,1) 五种组合送到对岸且出发岸的人数要够。合法性条件任意一岸如果传教士数大于 0则传教士数必须大于等于野人数。解的长度最短 11 步含往返。这道题的价值在于它演示了约束导致状态空间大幅缩小。原始组合 32 个加上合法性过滤只剩二十几个画在纸上都能手推。很多人做作业时直接写个 DFS 加 visited几行代码就出结果。我踩过的坑是初始状态和目标的对称性。左岸是(3,3,0)目标是(0,0,1)注意船必须在右岸。如果你的目标测试只写(0,0,x)会得到一个船停在左岸的假解。3.3 例题三农夫、狼、羊、菜过河问题农夫带着狼、羊、菜过河船一次只能带一样东西。农夫不在时狼会吃羊羊会吃菜。状态表示(农夫位置, 狼位置, 羊位置, 菜位置)每个分量 0 或 1共 16 种组合。状态规模16 个状态很小。但去掉非法状态狼羊同岸且农夫不在、羊菜同岸且农夫不在之后只剩 10 个。解最短 7 次渡河。这道题有个很反直觉的点最短解里需要把羊带回去一次也就是走回头路。很多人手推的时候卡在这里因为直觉认为任何重复动作都是浪费。但在状态空间图里回头路对应的是另一条边图上是允许的只要不重复访问节点就行。这也是我常拿它来说明搜索算法为什么需要判重——没有判重DFS 会在带羊过去、带羊回来之间无限循环。3.4 例题四倒水问题问题有两个水壶容量分别是 3 升和 5 升没有刻度。允许的操作是装满某个壶、倒空某个壶、把一个壶倒进另一个直到倒空或倒满。问怎么得到正好 4 升水。状态表示(壶A水量, 壶B水量)取值范围分别是 0 到 3 和 0 到 5。状态规模4 × 6 24 种组合所有组合都合法这是很少见的状态空间就是笛卡尔积的情况。算子装满 A(3, y)装满 B(x, 5)倒空 A(0, y)倒空 B(x, 0)A 倒进 B(x - t, y t)其中t min(x, 5 - y)B 倒进 A(x t, y - t)其中t min(y, 3 - x)目标测试任意一个壶里恰好 4 升也就是x 4 or y 4。注意是或不是且。这里的倒水量t min(源壶水量, 目标壶剩余容量)是整道题最容易写错的地方。我第一次写的时候直接写成min(x, 5 - y)但把符号弄反了导致水量变成负数搜索跑出来的路径完全不对。建议在算子里加一句断言或者在调试阶段打印每步水量肉眼检查。最短解是 6 步装满 5 升壶、倒入 3 升壶5 升壶剩 2、倒空 3 升壶、把 5 升壶剩的 2 升倒入 3 升壶、装满 5 升壶、用 5 升壶倒满 3 升壶5 升壶剩 4。这套操作手推一遍会发现每一步都有明确意图不是瞎试。3.5 例题五汉诺塔的状态空间长什么样汉诺塔是本科教材里的常客但很少有人认真算过它的状态空间有多大。n 个盘子、3 根柱子每个盘子可以放在任意一根柱子上而且盘子大小顺序自动保证大盘不能压小盘所以状态总数正好是 3^n。n3 时 27 个状态n10 时 59049 个n20 时接近 35 亿。规模看起来还行但最优解的步数是指数级的 2^n - 1n20 需要一百万步以上。这就引出一个重要认识状态空间规模和解路径长度是两个独立的量。空间小不代表路径短反过来也一样。倒水问题空间只有 24 个状态解也只有 6 步汉诺塔空间是指数级的路径也是指数级的。汉诺塔最优解之所以不靠搜索是因为它有明确的递归结构可以直接算出来。这也提示我们搜索是通用手段不是唯一手段。当问题有结构可以利用的时候别硬搜。4. 代码实操从建图到搜索的完整实现理论说完了下面是可以直接抄作业的代码。我用八数码作为载体因为它状态规模适中18 万能同时演示 BFS 和 A* 的差异而且验证方便。4.1 BFS 版本先把能跑通的写出来先写状态生成和基本工具函数。from collections import deque GOAL 123456780 def neighbors(state): 生成所有合法后继状态 idx state.index(0) r, c divmod(idx, 3) result [] for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: ni nr * 3 nc lst list(state) lst[idx], lst[ni] lst[ni], lst[idx] result.append(.join(lst)) return result def inversions(state): 忽略空格后的逆序数 seq [int(ch) for ch in state if ch ! 0] cnt 0 for i in range(len(seq)): for j in range(i 1, len(seq)): if seq[i] seq[j]: cnt 1 return cnt def solvable(state): return inversions(state) % 2 0然后是 BFS 主体。这里有个细节值得单独说visited 标记要在入队时打不能在出队时打。如果你在出队时才把节点加入 visited同一个状态会被多个父节点重复入队队列长度可能膨胀好几倍。这个坑我在第一次写多源 BFS 时踩得很实。def bfs(start, max_expandNone): if not solvable(start): return None, -1 if start GOAL: return [start], 0 queue deque([start]) parent {start: None} expanded 0 while queue: cur queue.popleft() expanded 1 if max_expand and expanded max_expand: return None, expanded for nxt in neighbors(cur): if nxt in parent: continue parent[nxt] cur if nxt GOAL: path [] node nxt while node is not None: path.append(node) node parent[node] return path[::-1], expanded queue.append(nxt) return None, expanded我在自己机器上测过一个中等难度的初始状态724506831逆序数 12可解BFS 大约展开 4 万个节点左右才找到解耗时不到一秒。但如果换成867254301这种难度更高的展开数会逼近 15 万耗时会涨到三四秒。这个差异就是启发式登场的原因。4.2 A* 版本启发式函数怎么写才可采纳A* 的核心是评估函数f(n) g(n) h(n)其中 g 是已经走过的步数h 是估计的剩余步数。h 必须满足可采纳性对任何状态h 都不能高估真实剩余代价。低估没关系最多多搜几个节点高估就完蛋了找到的解可能不是最优的。八数码有两个经典启发式h1错位棋子数。统计有多少个数字不在目标位置上不算空格。显然每个错位棋子至少要移动一次所以 h1 是可采纳的。h2曼哈顿距离。每个数字当前位置到目标位置的横纵距离之和。每次移动只能让一个数字的曼哈顿距离变化 1所以总距离至少要移动这么多次可采纳。两个都合格但 h2 明显更强因为它信息量更大。有定理保证如果 h2 在任何状态都不小于 h1就说 h2 支配 h1用 h2 的 A* 展开节点数不会比 h1 多。import heapq def manhattan(state): total 0 for i, ch in enumerate(state): if ch 0: continue v int(ch) - 1 gr, gc divmod(v, 3) r, c divmod(i, 3) total abs(r - gr) abs(c - gc) return total def astar(start): if not solvable(start): return None, -1 g {start: 0} parent {start: None} heap [(manhattan(start), 0, start)] closed set() expanded 0 while heap: f, cost, cur heapq.heappop(heap) if cur in closed: continue closed.add(cur) expanded 1 if cur GOAL: path [] node cur while node is not None: path.append(node) node parent[node] return path[::-1], expanded for nxt in neighbors(cur): ng cost 1 if nxt not in g or ng g[nxt]: g[nxt] ng parent[nxt] cur heapq.heappush(heap, (ng manhattan(nxt), ng, nxt)) return None, expanded同样跑867254301A* 展开的节点数大概只有 BFS 的十分之一左右。差距就从这里来。有个小陷阱堆里存的元组是(f, g, state)第三项是字符串。Python 在 f 和 g 都相同时会去比较字符串字符串是可以比较的所以不会报错。但如果你把状态换成一个自定义对象就必须加计数器打破平局否则TypeError: not supported。4.3 结果验证别只相信搜索说你找到了解搜索算法跑出结果不等于结果正确。我在批改作业时见过太多路径长度是 9 步但最后一步到不了目标的答案。三个验证步骤每次都要做第一逐步检查路径上相邻两个状态是否真的只差一次合法移动。写个函数is_valid_move(a, b)确认两者只差一个空格和相邻格子的交换。第二确认路径最后一个元素等于目标状态。第三确认路径中没有重复状态长度等于步数加一。def validate(path): if not path or path[-1] ! GOAL: return False if len(set(path)) ! len(path): return False for a, b in zip(path, path[1:]): if b not in neighbors(a): return False return True这三步检查成本极低但能在几秒钟内拦住绝大多数逻辑错误。养成习惯之后你会发现自己调试的时间大幅缩短。5. 常见问题与排查技巧实录这一节是我这些年攒下来的事故记录每一条都对应一个真实翻过的车。5.1 状态爆炸跑不起来不是代码慢是图太大症状很统一程序不报错但内存一路涨到几个 G然后被系统杀掉或者跑到天荒地老也不出结果。排查顺序是这样的。先算清楚理论上界八数码是 18 万15 数码是 10 万亿15 数码还用 BFS 就是你自己的问题。再检查 visited 是不是漏了如果没漏看neighbors()是不是生成了非法状态。我见过一个实现把空格不动也当成一个算子结果每个状态自我循环搜索树无限深。如果状态规模确实很大但问题有结构考虑换算法双向 BFS 能把指数降一半IDA* 能把内存压到 O(深度)或者换个更好的启发式。5.2 循环与重复为什么我的 DFS 停不下来DFS 不判重必然会绕圈这一点没有例外。八数码里空格左移再右移就是一个 2 步循环不判重的话 DFS 会沿着这条路一直走到栈溢出。但判重也不是随便加。有个细节很多人忽略在有代价的图里简单判重会导致次优解。如果同一个状态可以通过更低代价到达你必须允许重新访问。正确做法是判断新代价 已记录代价才更新也就是上面 A* 代码里if nxt not in g or ng g[nxt]那一句。算法判重策略原因BFS入队即标记不再访问每步代价相同先到一定最优DFS入栈沿途标记回溯时撤销避免环但不影响其他分支A*只在发现更小 g 时更新允许更优路径覆盖旧记录一致代价同 A*无 h保证最优5.3 几个高频报错和对应解法现象可能原因处理方式TypeError: unhashable type list用列表当字典键转成 tuple 或字符串结果路径长度不对算子漏写或写反逐条对照约束清单内存持续涨到被杀状态爆炸或未判重估算上界检查 visited找到解但不是最短用了 DFS 或启发式不可采纳换 BFS/一致代价检查 h搜索瞬间结束但无解初始状态不可达先跑可解性判定路径断链、父指针指向空路径还原时循环条件写错用 while node is not None5.4 做题和考试里的几条实战经验第一条先手推再写码。拿过河问题来说你在纸上把状态图画出来通常十几分钟就能找到解而这个解能帮你验证代码输出对不对。我见过太多人直接写代码跑出来一个 15 步的答案就交上去了也不知道那是不是最短的。第二条状态定义要能一眼看出合法性。传教士野人用(左岸传教士, 左岸野人, 船位置)比用(右岸传教士, 左岸野人, 船位置)好因为限制条件任意一岸传教士不能少于野人在两边的表达是对称的不容易写错。第三条把每个状态看作一个独立的完整快照。很多人的算子是就地修改状态对象结果父节点被子节点改脏了路径还原出来全是乱的。Python 里生成新列表再转换是最省心的写法。第四条规模估算的直觉要练出来。n 个元素的排列是 n!n 个二值变量是 2^n两个容量 a、b 的水壶是 (a1)(b1)三根柱子 n 个盘子是 3^n。这几个数记住拿到题先估一下能省掉大量白干的时间。第五条解路径长度和状态规模没有必然关系。汉诺塔空间是 3^n路径也是 2^n倒水问题空间只有几十路径也就几步。题目的难度取决于两者中更大的那个而不是只看其中一个。6. 状态空间图能延伸到哪些真实场景学完这套东西之后很多人会有个疑问除了做题这玩意儿真的用得上吗用得上而且用得很广只是它通常藏在别的名字底下。路径规划里地图的栅格就是一个状态空间图每个格子是状态上下左右移动是算子代价是格子间的距离或者通行难度。A* 是这里最常用的算法启发式通常用欧氏距离或者曼哈顿距离正是可采纳性的直接应用。任务调度和规划里每个状态是哪些任务已完成算子是开始一个满足前置条件的任务。这类问题的状态数是任务数的指数级所以通常配合剪枝或者启发式不能硬搜。游戏 AI 和谜题求解里数独、推箱子、华容道都是典型的状态空间问题。数独的状态是每个空格的可能取值集合算子是赋值加约束传播推箱子更接近八数码A* 加曼哈顿距离改良版能解中等难度的关卡。编译器和程序分析里控制流图本质上就是一种状态空间图每个基本块是节点跳转是边。数据流分析做的事情就是在这个图上做不动点迭代。这些场景的共同点是问题可以被切成离散的状态和明确的状态转移。凡是满足这两条的状态空间图这套方法论都能直接套上去。反过来如果状态是连续的、转移是模糊的那就要换别的工具了比如数值优化或者强化学习。我个人在实际项目里的体会是状态空间图最大的价值不在于让你写出一个搜索程序而在于它改变你分析问题的方式。遇到一个看起来复杂的问题你会自然地去问状态是什么动作是什么目标怎么判断规模有多大。把这四个问题回答清楚方案基本就浮出来了。这个习惯我用了很多年从课堂作业一路用到生产环境的调度器设计没失过手。最后分享一个我一直在用的小技巧拿不准状态定义的时候先用纸画五六个状态的图手动连边然后问自己这个状态是不是把后续所有可能性都包含进去了。如果两个不同的历史轨迹会导向同一个状态说明这个定义是无记忆的可以安全地用 visited 判重。如果导向不同状态说明你把历史混进了状态里要么补全信息要么就得放弃判重。这一步检查花不了五分钟但能省掉一整天返工。