带过几届人工智能导论的助教之后我摸出一个规律凡是状态空间图没画明白的同学后面的 A*、启发式搜索、甚至强化学习里的马尔可夫决策过程基本都会跟着塌方。原因很简单——人工智能里所谓的求解问题绝大多数时候就是在一张图上找一条从起点到终点的路图都没画对路自然找不到。这篇文章不讲虚的我拿四道最经典的例题八数码、传教士与野人过河、水壶问题、农夫带狼羊菜过河从头到尾把状态空间图的画法、约束条件、坑点和代码实现拆一遍你看完可以直接拿去对付课程作业和考试里的大题。适合刚入门人工智能的同学也适合当年学的时候囫囵吞枣、现在想补回来的朋友。预备知识只要一点点会写循环知道 Python 里的字典和集合怎么用就够了。至于为什么要有状态空间图、它和状态空间树有什么区别、BFS 和 DFS 在这张图上跑起来为什么结果差这么多这些我会在文中逐个说清楚。1. 状态空间图这张图到底画的是什么1.1 把解题翻译成在图上走路在人工智能里一个问题的状态空间图由两部分组成节点和边。节点代表问题在某一时刻的完整快照我们叫它状态边代表一个动作把系统从一个状态推到另一个状态这个动作我们叫算符。你手上有了这样一张图求解这个动作就退化成了一件事从初始状态节点出发找一条通往目标状态节点的路径。听起来像是把简单问题复杂化了但它带来的好处非常实在。现实问题五花八门下棋、倒水、机器人搬箱子、安排课程表表面上毫无关系可一旦都变成状态空间图我们就能用同一套搜索算法去处理。这就是人工智能导论里花大量篇幅讲状态空间图的真正原因——它是后续所有搜索算法的公共地基。我把这个转换过程总结成四个必答的问题你在做任何一道题之前先问自己状态是什么用一组变量完整描述当前局面。注意完整两个字缺一个变量图就是错的。初始状态是什么也就是起点通常题目会直接给。算符有哪些每一步允许做什么做了之后状态怎么变。目标状态怎么判断是完全确定的一个状态还是满足某个条件的一类状态。这四个问题答不上来别急着画图画了也是白画。我见过太多人一上来就开始连箭头连到一半发现状态里忘了记录船在哪边整张图作废重来。1.2 状态空间图的形式化定义学术一点的说法一个状态空间问题可以用四元组表示S, S₀, O, G。S 是所有可能状态的集合S₀ 是初始状态O 是算符集合G 是目标状态的判定条件。如果每条边的代价不一样还要再加一个代价函数 c。这里有个细节很多人忽略S 到底包不包含不合法的状态严格的写法是先定义所有变量取值组合的笛卡尔积得到形式上可达的状态全集然后再用约束条件把不合法的状态剔除掉。传教士与野人问题就是最好的例子形式上 4×4×2 共 32 种组合但满足任何一岸的野人数不能超过传教士数这个约束的只有 20 种。这一点我在第 4 章会详细展开。1.3 图和树别混为一谈教材里经常同时出现状态空间图和状态空间树很多同学以为是一回事其实差别很大。状态空间树是把搜索过程展开成树形结构同一个状态可能出现多次只要你从不同路径走到它它就在树里出现多个副本。状态空间图则要求相同的状态必须合并成同一个节点同一个状态在图里只能有一个节点但可以有多个入边。举个直观的数字。八数码问题里棋盘一共 9 个格看起来有 9! 362880 种排列但真正从某个初始状态出发能走到的状态只有 9!/2 181440 个因为有一半排列在奇偶性上根本不可达。如果你按树的方式搜索节点数会以指数级别爆炸按图的方式搜索节点数被死死限制在 18 万这个量级。提示考试里画状态空间图一定要合并重复状态。如果你画出来一棵树哪怕逻辑没错也会被扣分因为这恰恰暴露了你没理解图和树的区别。2. 动手画图之前先把状态编码定下来2.1 三种常见的状态编码方式状态怎么存直接决定了你后面代码写得顺不顺。我常用的有这么三种编码方式示例八数码优点缺点元组(1,2,3,4,5,6,7,8,0)天然可哈希能直接丢进集合拷贝时要注意不可变特性字符串123456780打印好看调试直观要频繁做 int/str 转换整数位压缩把每个格塞进 4 bit极致省内存可读性差容易写错我个人的建议是做题和写作业用元组性能敏感的场景再考虑位压缩。元组是不可变对象可以直接当字典的键也可以放进 set 做去重这两件事在搜索里用到的地方太多了。用列表的同学经常栽一个坑——列表是可变对象不能哈希往 set 里一放就报TypeError: unhashable type: list。2.2 算符的定义和合法性判定算符的定义要注意两个层面语义层说清楚这个动作干什么实现层写清楚边界怎么判断。还是拿八数码举例。空格可以往上下左右四个方向移动但边界上的空格只有两三个方向可走。写代码时如果忘了判断数组下标越界Python 会给你抛 IndexError而 C 语言里则会偷偷跑到相邻内存上产生一个你在图上永远找不到的幽灵状态。这种情况在考试手写代码时倒是不至于但检查图的时候会犯有人把左上角空格的向上移也画了一条边然后自己绕不出来。判断逻辑我习惯写成先算目标格坐标再判断是否在范围内比在四个方向上各写一遍 if 更清晰r, c divmod(index_of_blank, 3) 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: # 合法生成新状态 ...2.3 初始状态和目标条件的形式化目标条件的写法有两个流派一种是给一个确定的目标状态比如八数码就是(1,2,3,4,5,6,7,8,0)另一种是给一个判定函数只要状态满足条件就算到达目标比如水壶问题某一壶里恰好有 2 升水这就有无数个目标状态。第二种写法在作业里特别容易被判错因为很多同学默认目标就是一个点。你可以想象一下如果把水壶问题的目标写成(2, 0)那所有其他壶里有 2 升水的状态都被当成非目标搜索可能会绕很大一圈甚至找不到解。注意目标判定函数要写得足够松只要满足题意就算数但也不能太松把不含目标的状态也算进去。这一松一紧之间靠的是把题目原文再读一遍。3. 例题一八数码问题里的状态空间图3.1 从棋盘到子节点空格的四种走法八数码也叫重排九宫是状态空间图最经典的入门例题。3×3 的棋盘上放 1 到 8 八个数字和一个空格每次只能把空格与相邻的数字交换。初始状态随便给一个排列目标状态通常是123456780。以(1,2,3,4,0,5,7,8,6)为例空格在下标 4 的位置也就是正中间。它的四个方向都合法能生成四个子状态。这一步一定要手算一遍把所有子状态写出来然后在纸上画箭头。为什么强调手算因为你会在这一步第一次真切地感受到节点数增长得有多快——中间位置展开 4 个边上展开 3 个角上只展开 2 个平均分支因子大概是 3。8 步之内到达的搜索空间就已经上万了。展开一层之后你会立刻遇到一个问题子状态里有一个和父状态长得一模一样。比如空格向上再向下就回到了原点。这就是有环图处理不当会让搜索算法原地打转永远出不来。3.2 逆序数三分钟判断这道题有没有解八数码有个非常漂亮的结论不是所有初始状态都能到达目标状态。判断方法叫逆序数。把棋盘按行展开成一个序列去掉空格然后数一数有多少对数字满足前面的比后面的大。这个数量叫逆序数。如果逆序数是偶数那么这个状态和目标状态标准的12345678逆序数为 0属于同一个连通分量有解如果逆序数是奇数无解搜索跑再久也找不到答案。这个结论只对奇数宽度3×3、5×5成立。如果是 4×4 的十五数码还得把空格所在行数的影响算进去规则变成逆序数 空格所在行号从下往上数的奇偶性。我在作业里批过太多次这种情况程序写得完全正确BFS 跑了十分钟没出结果学生来问是不是算法写错了。一看初始状态逆序数是奇数本身就无解。所以在写搜索代码之前先花三分钟算一下逆序数能省掉大量无谓的调试。def solvable(state, goal(1, 2, 3, 4, 5, 6, 7, 8, 0)): seq [x for x in state if x ! 0] goal_seq [x for x in goal if x ! 0] # 简化版目标为 12345678 时逆序数为偶即可解 inv sum(1 for i in range(len(seq)) for j in range(i 1, len(seq)) if seq[i] seq[j]) return inv % 2 03.3 亲手展开两层理解图的合并动作我建议每个初学的人都做一次这样的练习拿一个初始状态手动展开两层把生成的每个状态编号重复出现的画虚线指向已有节点。做完之后你会得到一张比想象中小得多的图。这个练习的价值在于它让你直观理解为什么合并重复状态这么重要。假设不合并展开第 d 层时有大约 3^d 个节点合并之后因为状态总数只有 18 万深度到 20 层左右时节点数就被封顶了。这个差距就是你写的搜索程序能不能在几秒内跑完的关键。还有一个经常被忽略的细节合并动作应该发生在生成节点时还是扩展节点时这两种写法对应的算法正确性不一样。生成时就查重能保证 frontier 里没有重复扩展时才查重同一个状态可能先以较差路径进入 frontier后面又被更好的路径覆盖。对于 BFS 这种每条边代价相同的算法两种写法结果一样对于代价不同的搜索就得用后面第 6 章讲的致性检查。4. 例题二传教士与野人过河的完整状态空间4.1 状态三元组 (M, C, B)三对传教士和三个野人要过河船上最多坐两人任何一岸只要野人数超过传教士数传教士就会被吃掉。船必须有人划不会自己开。这个题的第一个难点是你能不能想到把船的位置也塞进状态里。状态定义为M左岸传教士人数取值 0 到 3C左岸野人数取值 0 到 3B船的位置1 表示在左岸0 表示在右岸。写成三元组就是(M, C, B)。少写一个 B你就永远不知道下一步该从哪边开船整张图是错的。这是这道题最高频的失分点没有之一。4.2 20 个合法状态是怎么筛出来的先看形式上的状态总数M 有 4 种取值C 有 4 种取值B 有 2 种取值一共 4×4×2 32 种组合。接下来加约束。设右岸的传教士人数为 3−M野人数为 3−C那么在左岸要求M 0 或者 M C在右岸要求(3−M) 0 或者 (3−M) (3−C)。两个条件同时满足才算合法。我一个一个筛给你看(M, C)左岸合法右岸 (3−M, 3−C)右岸合法结论(0, 0)是M0(3, 3)是保留(0, 1)是(3, 2)是保留(0, 2)是(3, 1)是保留(0, 3)是(3, 0)是保留(1, 1)是(2, 2)是保留(1, 2)否1 2——剔除(1, 3)否——剔除(2, 2)是(1, 1)是保留(3, 0)是(0, 3)是保留(3, 1)是(0, 2)是保留(3, 2)是(0, 1)是保留(3, 3)是(0, 0)是保留(1, 0)是(2, 3)否2 3剔除(2, 0)是(1, 3)否剔除(2, 1)是(1, 2)否剔除(2, 3)否2 3——剔除筛下来是 10 组合法的 (M, C)乘上 B 的两种取值合法状态一共 20 个。其中(0,0,左)和(3,3,右)是可达但无法继续推进的死状态实际参与搜索的节点更少。记住这个 20考试里如果老师让你手画状态空间图画完数一数节点数对不上就说明筛错了。4.3 解路径与回退陷阱从初始状态(3, 3, 1)到目标状态(0, 0, 0)经典解是 11 步。手画图的时候你会发现一个现象搜索过程中经常出现走两步看起来回到了类似局面的情况比如把人送过去又立刻送回来。这不是算法错了而是状态空间图里本来就存在环。处理环的标准做法是维护一个已访问集合。图上每扩展一个节点就把它标记为已访问之后如果某个算符生成的子状态已经在集合里直接丢弃。这样做的代价是我们可能漏掉某些路径但对于只要求找到一条解路径的题目来说完全够用。提示传教士与野人有个变体是船的容量为 3这时候解会变成 9 步。如果你按照容量 2 的图去算容量 3 的题会出现明明画了图却怎么都走不到的诡异情况。做题前先把题目里的每个数字圈出来这不是啰嗦是保命。5. 例题三、四水壶问题与狼羊菜过河5.1 水壶问题的六个算符题目有两个壶容量分别是 4 升和 3 升没有刻度线允许的操作是装满、倒空、互相倒水问怎么得到恰好 2 升水。状态定义为(a, b)a 是 4 升壶里当前的水量b 是 3 升壶里的水量。a 取值 0 到 4b 取值 0 到 3形式上共 5×4 20 个状态全部合法。算符一共六个每一个都要写清楚状态转移规则算符转移规则说明装满 4 升壶(4, b)无条件装满 3 升壶(a, 3)无条件倒空 4 升壶(0, b)无条件倒空 3 升壶(a, 0)无条件4 升倒入 3 升(a - t, b t)t min(a, 3 - b)倒到对方满或自己空为止3 升倒入 4 升(a t, b - t)t min(b, 4 - a)同上第六个算符是这道题的精髓。很多同学写成(a b, 0)那是错的因为 4 升壶装不下 3 升壶里的全部水。正确的写法是先算出能倒多少t min(b, 4 - a)再把t从源壶减去、加到目标壶上。这个min的细节是这道题在作业里最容易被扣分的地方。从(0, 0)出发BFS 找到的解是 6 步装满 3 升壶 → 倒入 4 升壶 → 装满 3 升壶 → 倒入 4 升壶至满 → 倒空 4 升壶 → 把 3 升壶里剩下的 2 升倒入 4 升壶。走到这里(2, 0)目标达成。5.2 狼羊菜过河用位掩码把状态压到 4 位农夫要带狼、羊、白菜过河船每次只能带一样东西或者不带。人不在的一岸狼会吃羊羊会吃白菜。状态用一个 4 位的二进制数表示物品在左岸的集合再加一位表示农夫的位置。狼、羊、菜各占一位比如0b0111表示狼、羊、菜都在左岸。这样状态总数是 16 种实际可达的更少。合法性检查的逻辑是对每一岸如果农夫不在这一岸那么这一岸不能同时出现狼和羊也不能同时出现羊和菜。写成代码就是def legal(left_mask, farmer_left): for bank in (left_mask, (~left_mask) 0b111): # 如果农夫不在这岸 if bank ... : wolf, goat, cabbage (bank 2) 1, (bank 1) 1, bank 1 if (wolf and goat) or (goat and cabbage): return False return True位掩码的好处是状态可以直接作为整数放进数组下标速度极快。缺点是调试的时候看不出内容你得写一个print_state函数把二进制翻译成中文再打印否则对着一串 0 和 1 你会怀疑人生。这道题的经典解是 7 步带羊过去空手回来带狼过去带羊回来带菜过去空手回来带羊过去。这里有个反直觉的点——人必须把羊带回来一次。因为羊既是狼的猎物又是菜的威胁它是整道题的关键物品。这个结论只有把状态空间图画完整了才能看出来凭直觉硬猜是猜不到的。6. 在这张图上跑搜索BFS、DFS、UCS、A*6.1 队列和栈一行代码的差别状态空间图建好之后怎么在上面找路最简单的两种算法是广度优先和深度优先它们的代码结构几乎一样唯一的区别在于从 frontier 里取节点的顺序。广度优先BFS用队列先进先出。先访问的节点先扩展效果是一层一层往外扩。它保证找到的是步数最少的解。深度优先DFS用栈后进先出。它一路往下钻撞到死胡同再回来。空间占用小但不保证最短还可能因为图里有环而陷入无限循环。为什么 BFS 能保证最短原因在于它按层扩展第一次遇到目标状态时一定是所有通往目标的路径里层数最少的那条。这个性质建立在每条边代价相同的前提上。如果边代价不同比如不同动作的耗时不一样BFS 就失效了得换成一致代价搜索。DFS 的死循环问题在状态空间图上尤其容易踩。因为图里有环深度优先可能 A→B→A→B 无限转下去。解决办法就是前面提到的已访问集合。但要注意加了已访问集合的 DFS 已经变成了图搜索而不是树搜索它在某些情况下会找不到解这是有向图上搜索的固有代价。6.2 closed 表和重复状态检测正规的图搜索算法里有三个结构frontier也叫 open 表待扩展的节点集合用优先队列或者双端队列实现。closed 表已经扩展过的节点集合用来防止重复扩展。parent 表记录每个节点是从哪个节点来的找到目标后靠它回溯路径。closed 表的实现方式影响很大。用列表存每次判断if state in closed是 O(n) 的线性扫描状态一多程序就会卡死用集合或字典存判断是 O(1)这是标准做法。我见过有同学的八数码程序跑了两分钟没出结果改成 set 之后 0.2 秒跑完就是这个原因。还有一个细节parent 表要在生成子节点时写入而不是扩展时写入。写法是如果子节点既不在 frontier 也不在 closed 里就把它加进 frontier 并记录父节点。这样能保证每个状态在 frontier 里只出现一次省内存也省时间。6.3 启发式函数怎么设计才可采纳A* 算法是 BFS 的升级版它给每个节点打分f(n) g(n) h(n)。g 是从起点走到当前的已知代价h 是对从当前走到目标还要多少步的估计。h 的设计要满足可采纳性估计值永远不能超过真实值即h(n) h*(n)。一旦 h 估计过头A* 就可能错过最优解。八数码里有两个经典的 h错位数字个数数一下有多少个数字不在目标位置上。这个估计肯定不超标因为每个错位的数字至少要动一步。曼哈顿距离之和每个数字当前位置到目标位置的横纵坐标差之和。这个估计更紧搜索效率高得多而且它依然可采纳因为一次移动只能让一个数字的曼哈顿距离减少 1。实测下来同一个困难初始状态用错位数当 h 大约要扩展几千个节点用曼哈顿距离只要几百个差距非常明显。所以写作业时我一般直接上曼哈顿距离代码多不了几行效果立竿见影。要提醒的是曼哈顿距离对八数码是可采纳的但换成只能斜着走的棋盘就不一定了。可采纳性永远针对具体的问题和具体的动作集合没有放之四海皆准的启发式函数。7. 用 Python 把状态空间图跑起来7.1 一个通用的图搜索骨架我把 BFS 的逻辑抽成一个通用函数只要传入初始状态、目标判定和邻居生成器就能跑四种例题共用同一套骨架from collections import deque def graph_search(init, goal_test, neighbors): frontier deque([init]) parent {init: None} while frontier: state frontier.popleft() if goal_test(state): path [] while state is not None: path.append(state) state parent[state] return path[::-1] for nxt, action in neighbors(state): if nxt not in parent: # 生成时查重避免重复入队 parent[nxt] state frontier.append(nxt) return None这段代码有三个关键点parent字典同时承担了 closed 表和路径记录两个职责查重放在生成子节点时而不是扩展当前节点时路径回溯用path[::-1]反转。看起来简单但每一处都是踩过坑之后定下来的写法。7.2 八数码的完整实现GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def neighbors_8p(state): i state.index(0) r, c divmod(i, 3) for dr, dc, name in ((-1, 0, 上), (1, 0, 下), (0, -1, 左), (0, 1, 右)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: j nr * 3 nc lst list(state) lst[i], lst[j] lst[j], lst[i] yield tuple(lst), name def solvable(state): seq [x for x in state if x ! 0] inv sum(1 for i in range(len(seq)) for j in range(i 1, len(seq)) if seq[i] seq[j]) return inv % 2 0 start (2, 8, 3, 1, 6, 4, 7, 0, 5) if not solvable(start): print(该状态无解) else: path graph_search(start, lambda s: s GOAL, neighbors_8p) print(解的长度, len(path) - 1) for step, node in enumerate(path): print(f第 {step} 步: {node})跑之前先判断可解性这一步能帮你省掉一次漫长的等待。上面的start是一个经典的中等难度初始状态BFS 大概几秒内能出结果。如果你想要更快的版本把 BFS 换成 A*用heapq维护优先队列h 用曼哈顿距离。7.3 水壶问题的完整实现CAP (4, 3) def neighbors_wj(state): a, b state # 装满 yield (CAP[0], b), 装满 4L yield (a, CAP[1]), 装满 3L # 倒空 yield (0, b), 倒空 4L yield (a, 0), 倒空 3L # 互相倒 t min(a, CAP[1] - b) yield (a - t, b t), 4L 倒入 3L t min(b, CAP[0] - a) yield (a t, b - t), 3L 倒入 4L path graph_search((0, 0), lambda s: s[0] 2 or s[1] 2, neighbors_wj) for step, node in enumerate(path): print(f第 {step} 步: {node})注意目标判定用的是任意一个壶里有 2 升而不是某个具体状态。这正是前面强调的目标条件要按题意写松一点。8. 手画状态空间图时最容易翻车的几个地方8.1 状态变量漏项这是第一大坑前面反复提过。传教士问题漏了船的位置狼羊菜漏了农夫的位置八数码漏了空格的位置。判断自己有没有漏用一句话自检给我这个状态我能不能唯一确定下一步所有可能的走法如果答不上来说明状态描述不完整。8.2 把不合法状态也画进图里传教士问题里那些某岸野人多于传教士的组合属于约束违规压根不该出现在状态空间图里。有些同学图省事先把 32 种组合全画出来再在旁边标注哪些不合法考试的时候这样画是要扣分的。正确的做法是先筛后画图里只保留合法节点。8.3 忘记标注边上的算符状态空间图的边是有语义的每条边对应一个具体动作。手画的时候最好在箭头旁边写上动作名称比如狼过河装满 3L而不是光秃秃一条线。这在批改时是重要的得分点也能帮你在后面找路径时快速复述出解法的每一步。8.4 认为目标状态唯一水壶问题、狼羊菜这类题目标往往是一类状态而不是一个点。如果你按必须精确等于某个状态去判断很容易搜不到解或者搜出一条莫名其妙的路径。8.5 深拷贝和浅拷贝写代码的同学容易在这里翻车。八数码生成子状态时如果你直接修改原列表再把它存进去后面的所有节点都会指向同一个对象图就全乱了。正确做法是每次都list(state)造一个新列表再转成元组。我一般干脆全程用元组lst list(state)只在生成的那一刻临时用一下转换完立刻丢弃。8.6 用递归写 DFS 导致栈溢出Python 默认递归深度限制是 1000 层。状态空间图稍微大一点递归版的 DFS 就会抛RecursionError。建议用显式的栈来写迭代版本既安全又能清楚地看到 frontier 的变化过程。9. 我个人的几条经验第一画图之前先把状态定义写在纸上标清楚每个变量的取值范围然后再动手。这一步花三分钟能省掉后面半小时的重画。第二先算状态总数再估图的大小。传教士问题 20 个状态水壶问题 20 个狼羊菜 16 个八数码 18 万。数字心里有底之后你就知道该用 BFS 还是该上 A*也大概能预判程序会跑多久。第三遇到搜索跑不出来先怀疑状态定义再怀疑算法。我个人的排查顺序是逆序数八数码→ 目标判定是不是写太严 → 算符是不是漏了 → 查重是不是写错 → 最后才去看算法本身。这个顺序几乎每次都能命中问题所在。第四把每道题的解路径打印出来人工走一遍。程序说 11 步能过河你就拿纸笔按这 11 步走一遍看看有没有哪一步之后某岸的野人比传教士多。这个过程很枯燥但能帮你抓住绝大多数逻辑错误比盯着代码看有效得多。第五如果时间充裕把同一道题用 BFS、DFS、A* 各写一遍对比扩展节点数。这个对比会让我对启发式函数值多少钱这件事有非常具体的感受也更容易在考试里判断出题人到底想考哪个算法。最后说一个小的调试技巧。状态用元组存的时候打印出来是一串数字很难看。写一个render(state)函数把它还原成棋盘或者两岸的示意图调试效率能提升一大截。我至今保留着这个习惯写任何状态空间相关的代码第一个函数永远是这个渲染函数。
状态空间图怎么画？八数码到A*搜索全解析
带过几届人工智能导论的助教之后我摸出一个规律凡是状态空间图没画明白的同学后面的 A*、启发式搜索、甚至强化学习里的马尔可夫决策过程基本都会跟着塌方。原因很简单——人工智能里所谓的求解问题绝大多数时候就是在一张图上找一条从起点到终点的路图都没画对路自然找不到。这篇文章不讲虚的我拿四道最经典的例题八数码、传教士与野人过河、水壶问题、农夫带狼羊菜过河从头到尾把状态空间图的画法、约束条件、坑点和代码实现拆一遍你看完可以直接拿去对付课程作业和考试里的大题。适合刚入门人工智能的同学也适合当年学的时候囫囵吞枣、现在想补回来的朋友。预备知识只要一点点会写循环知道 Python 里的字典和集合怎么用就够了。至于为什么要有状态空间图、它和状态空间树有什么区别、BFS 和 DFS 在这张图上跑起来为什么结果差这么多这些我会在文中逐个说清楚。1. 状态空间图这张图到底画的是什么1.1 把解题翻译成在图上走路在人工智能里一个问题的状态空间图由两部分组成节点和边。节点代表问题在某一时刻的完整快照我们叫它状态边代表一个动作把系统从一个状态推到另一个状态这个动作我们叫算符。你手上有了这样一张图求解这个动作就退化成了一件事从初始状态节点出发找一条通往目标状态节点的路径。听起来像是把简单问题复杂化了但它带来的好处非常实在。现实问题五花八门下棋、倒水、机器人搬箱子、安排课程表表面上毫无关系可一旦都变成状态空间图我们就能用同一套搜索算法去处理。这就是人工智能导论里花大量篇幅讲状态空间图的真正原因——它是后续所有搜索算法的公共地基。我把这个转换过程总结成四个必答的问题你在做任何一道题之前先问自己状态是什么用一组变量完整描述当前局面。注意完整两个字缺一个变量图就是错的。初始状态是什么也就是起点通常题目会直接给。算符有哪些每一步允许做什么做了之后状态怎么变。目标状态怎么判断是完全确定的一个状态还是满足某个条件的一类状态。这四个问题答不上来别急着画图画了也是白画。我见过太多人一上来就开始连箭头连到一半发现状态里忘了记录船在哪边整张图作废重来。1.2 状态空间图的形式化定义学术一点的说法一个状态空间问题可以用四元组表示S, S₀, O, G。S 是所有可能状态的集合S₀ 是初始状态O 是算符集合G 是目标状态的判定条件。如果每条边的代价不一样还要再加一个代价函数 c。这里有个细节很多人忽略S 到底包不包含不合法的状态严格的写法是先定义所有变量取值组合的笛卡尔积得到形式上可达的状态全集然后再用约束条件把不合法的状态剔除掉。传教士与野人问题就是最好的例子形式上 4×4×2 共 32 种组合但满足任何一岸的野人数不能超过传教士数这个约束的只有 20 种。这一点我在第 4 章会详细展开。1.3 图和树别混为一谈教材里经常同时出现状态空间图和状态空间树很多同学以为是一回事其实差别很大。状态空间树是把搜索过程展开成树形结构同一个状态可能出现多次只要你从不同路径走到它它就在树里出现多个副本。状态空间图则要求相同的状态必须合并成同一个节点同一个状态在图里只能有一个节点但可以有多个入边。举个直观的数字。八数码问题里棋盘一共 9 个格看起来有 9! 362880 种排列但真正从某个初始状态出发能走到的状态只有 9!/2 181440 个因为有一半排列在奇偶性上根本不可达。如果你按树的方式搜索节点数会以指数级别爆炸按图的方式搜索节点数被死死限制在 18 万这个量级。提示考试里画状态空间图一定要合并重复状态。如果你画出来一棵树哪怕逻辑没错也会被扣分因为这恰恰暴露了你没理解图和树的区别。2. 动手画图之前先把状态编码定下来2.1 三种常见的状态编码方式状态怎么存直接决定了你后面代码写得顺不顺。我常用的有这么三种编码方式示例八数码优点缺点元组(1,2,3,4,5,6,7,8,0)天然可哈希能直接丢进集合拷贝时要注意不可变特性字符串123456780打印好看调试直观要频繁做 int/str 转换整数位压缩把每个格塞进 4 bit极致省内存可读性差容易写错我个人的建议是做题和写作业用元组性能敏感的场景再考虑位压缩。元组是不可变对象可以直接当字典的键也可以放进 set 做去重这两件事在搜索里用到的地方太多了。用列表的同学经常栽一个坑——列表是可变对象不能哈希往 set 里一放就报TypeError: unhashable type: list。2.2 算符的定义和合法性判定算符的定义要注意两个层面语义层说清楚这个动作干什么实现层写清楚边界怎么判断。还是拿八数码举例。空格可以往上下左右四个方向移动但边界上的空格只有两三个方向可走。写代码时如果忘了判断数组下标越界Python 会给你抛 IndexError而 C 语言里则会偷偷跑到相邻内存上产生一个你在图上永远找不到的幽灵状态。这种情况在考试手写代码时倒是不至于但检查图的时候会犯有人把左上角空格的向上移也画了一条边然后自己绕不出来。判断逻辑我习惯写成先算目标格坐标再判断是否在范围内比在四个方向上各写一遍 if 更清晰r, c divmod(index_of_blank, 3) 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: # 合法生成新状态 ...2.3 初始状态和目标条件的形式化目标条件的写法有两个流派一种是给一个确定的目标状态比如八数码就是(1,2,3,4,5,6,7,8,0)另一种是给一个判定函数只要状态满足条件就算到达目标比如水壶问题某一壶里恰好有 2 升水这就有无数个目标状态。第二种写法在作业里特别容易被判错因为很多同学默认目标就是一个点。你可以想象一下如果把水壶问题的目标写成(2, 0)那所有其他壶里有 2 升水的状态都被当成非目标搜索可能会绕很大一圈甚至找不到解。注意目标判定函数要写得足够松只要满足题意就算数但也不能太松把不含目标的状态也算进去。这一松一紧之间靠的是把题目原文再读一遍。3. 例题一八数码问题里的状态空间图3.1 从棋盘到子节点空格的四种走法八数码也叫重排九宫是状态空间图最经典的入门例题。3×3 的棋盘上放 1 到 8 八个数字和一个空格每次只能把空格与相邻的数字交换。初始状态随便给一个排列目标状态通常是123456780。以(1,2,3,4,0,5,7,8,6)为例空格在下标 4 的位置也就是正中间。它的四个方向都合法能生成四个子状态。这一步一定要手算一遍把所有子状态写出来然后在纸上画箭头。为什么强调手算因为你会在这一步第一次真切地感受到节点数增长得有多快——中间位置展开 4 个边上展开 3 个角上只展开 2 个平均分支因子大概是 3。8 步之内到达的搜索空间就已经上万了。展开一层之后你会立刻遇到一个问题子状态里有一个和父状态长得一模一样。比如空格向上再向下就回到了原点。这就是有环图处理不当会让搜索算法原地打转永远出不来。3.2 逆序数三分钟判断这道题有没有解八数码有个非常漂亮的结论不是所有初始状态都能到达目标状态。判断方法叫逆序数。把棋盘按行展开成一个序列去掉空格然后数一数有多少对数字满足前面的比后面的大。这个数量叫逆序数。如果逆序数是偶数那么这个状态和目标状态标准的12345678逆序数为 0属于同一个连通分量有解如果逆序数是奇数无解搜索跑再久也找不到答案。这个结论只对奇数宽度3×3、5×5成立。如果是 4×4 的十五数码还得把空格所在行数的影响算进去规则变成逆序数 空格所在行号从下往上数的奇偶性。我在作业里批过太多次这种情况程序写得完全正确BFS 跑了十分钟没出结果学生来问是不是算法写错了。一看初始状态逆序数是奇数本身就无解。所以在写搜索代码之前先花三分钟算一下逆序数能省掉大量无谓的调试。def solvable(state, goal(1, 2, 3, 4, 5, 6, 7, 8, 0)): seq [x for x in state if x ! 0] goal_seq [x for x in goal if x ! 0] # 简化版目标为 12345678 时逆序数为偶即可解 inv sum(1 for i in range(len(seq)) for j in range(i 1, len(seq)) if seq[i] seq[j]) return inv % 2 03.3 亲手展开两层理解图的合并动作我建议每个初学的人都做一次这样的练习拿一个初始状态手动展开两层把生成的每个状态编号重复出现的画虚线指向已有节点。做完之后你会得到一张比想象中小得多的图。这个练习的价值在于它让你直观理解为什么合并重复状态这么重要。假设不合并展开第 d 层时有大约 3^d 个节点合并之后因为状态总数只有 18 万深度到 20 层左右时节点数就被封顶了。这个差距就是你写的搜索程序能不能在几秒内跑完的关键。还有一个经常被忽略的细节合并动作应该发生在生成节点时还是扩展节点时这两种写法对应的算法正确性不一样。生成时就查重能保证 frontier 里没有重复扩展时才查重同一个状态可能先以较差路径进入 frontier后面又被更好的路径覆盖。对于 BFS 这种每条边代价相同的算法两种写法结果一样对于代价不同的搜索就得用后面第 6 章讲的致性检查。4. 例题二传教士与野人过河的完整状态空间4.1 状态三元组 (M, C, B)三对传教士和三个野人要过河船上最多坐两人任何一岸只要野人数超过传教士数传教士就会被吃掉。船必须有人划不会自己开。这个题的第一个难点是你能不能想到把船的位置也塞进状态里。状态定义为M左岸传教士人数取值 0 到 3C左岸野人数取值 0 到 3B船的位置1 表示在左岸0 表示在右岸。写成三元组就是(M, C, B)。少写一个 B你就永远不知道下一步该从哪边开船整张图是错的。这是这道题最高频的失分点没有之一。4.2 20 个合法状态是怎么筛出来的先看形式上的状态总数M 有 4 种取值C 有 4 种取值B 有 2 种取值一共 4×4×2 32 种组合。接下来加约束。设右岸的传教士人数为 3−M野人数为 3−C那么在左岸要求M 0 或者 M C在右岸要求(3−M) 0 或者 (3−M) (3−C)。两个条件同时满足才算合法。我一个一个筛给你看(M, C)左岸合法右岸 (3−M, 3−C)右岸合法结论(0, 0)是M0(3, 3)是保留(0, 1)是(3, 2)是保留(0, 2)是(3, 1)是保留(0, 3)是(3, 0)是保留(1, 1)是(2, 2)是保留(1, 2)否1 2——剔除(1, 3)否——剔除(2, 2)是(1, 1)是保留(3, 0)是(0, 3)是保留(3, 1)是(0, 2)是保留(3, 2)是(0, 1)是保留(3, 3)是(0, 0)是保留(1, 0)是(2, 3)否2 3剔除(2, 0)是(1, 3)否剔除(2, 1)是(1, 2)否剔除(2, 3)否2 3——剔除筛下来是 10 组合法的 (M, C)乘上 B 的两种取值合法状态一共 20 个。其中(0,0,左)和(3,3,右)是可达但无法继续推进的死状态实际参与搜索的节点更少。记住这个 20考试里如果老师让你手画状态空间图画完数一数节点数对不上就说明筛错了。4.3 解路径与回退陷阱从初始状态(3, 3, 1)到目标状态(0, 0, 0)经典解是 11 步。手画图的时候你会发现一个现象搜索过程中经常出现走两步看起来回到了类似局面的情况比如把人送过去又立刻送回来。这不是算法错了而是状态空间图里本来就存在环。处理环的标准做法是维护一个已访问集合。图上每扩展一个节点就把它标记为已访问之后如果某个算符生成的子状态已经在集合里直接丢弃。这样做的代价是我们可能漏掉某些路径但对于只要求找到一条解路径的题目来说完全够用。提示传教士与野人有个变体是船的容量为 3这时候解会变成 9 步。如果你按照容量 2 的图去算容量 3 的题会出现明明画了图却怎么都走不到的诡异情况。做题前先把题目里的每个数字圈出来这不是啰嗦是保命。5. 例题三、四水壶问题与狼羊菜过河5.1 水壶问题的六个算符题目有两个壶容量分别是 4 升和 3 升没有刻度线允许的操作是装满、倒空、互相倒水问怎么得到恰好 2 升水。状态定义为(a, b)a 是 4 升壶里当前的水量b 是 3 升壶里的水量。a 取值 0 到 4b 取值 0 到 3形式上共 5×4 20 个状态全部合法。算符一共六个每一个都要写清楚状态转移规则算符转移规则说明装满 4 升壶(4, b)无条件装满 3 升壶(a, 3)无条件倒空 4 升壶(0, b)无条件倒空 3 升壶(a, 0)无条件4 升倒入 3 升(a - t, b t)t min(a, 3 - b)倒到对方满或自己空为止3 升倒入 4 升(a t, b - t)t min(b, 4 - a)同上第六个算符是这道题的精髓。很多同学写成(a b, 0)那是错的因为 4 升壶装不下 3 升壶里的全部水。正确的写法是先算出能倒多少t min(b, 4 - a)再把t从源壶减去、加到目标壶上。这个min的细节是这道题在作业里最容易被扣分的地方。从(0, 0)出发BFS 找到的解是 6 步装满 3 升壶 → 倒入 4 升壶 → 装满 3 升壶 → 倒入 4 升壶至满 → 倒空 4 升壶 → 把 3 升壶里剩下的 2 升倒入 4 升壶。走到这里(2, 0)目标达成。5.2 狼羊菜过河用位掩码把状态压到 4 位农夫要带狼、羊、白菜过河船每次只能带一样东西或者不带。人不在的一岸狼会吃羊羊会吃白菜。状态用一个 4 位的二进制数表示物品在左岸的集合再加一位表示农夫的位置。狼、羊、菜各占一位比如0b0111表示狼、羊、菜都在左岸。这样状态总数是 16 种实际可达的更少。合法性检查的逻辑是对每一岸如果农夫不在这一岸那么这一岸不能同时出现狼和羊也不能同时出现羊和菜。写成代码就是def legal(left_mask, farmer_left): for bank in (left_mask, (~left_mask) 0b111): # 如果农夫不在这岸 if bank ... : wolf, goat, cabbage (bank 2) 1, (bank 1) 1, bank 1 if (wolf and goat) or (goat and cabbage): return False return True位掩码的好处是状态可以直接作为整数放进数组下标速度极快。缺点是调试的时候看不出内容你得写一个print_state函数把二进制翻译成中文再打印否则对着一串 0 和 1 你会怀疑人生。这道题的经典解是 7 步带羊过去空手回来带狼过去带羊回来带菜过去空手回来带羊过去。这里有个反直觉的点——人必须把羊带回来一次。因为羊既是狼的猎物又是菜的威胁它是整道题的关键物品。这个结论只有把状态空间图画完整了才能看出来凭直觉硬猜是猜不到的。6. 在这张图上跑搜索BFS、DFS、UCS、A*6.1 队列和栈一行代码的差别状态空间图建好之后怎么在上面找路最简单的两种算法是广度优先和深度优先它们的代码结构几乎一样唯一的区别在于从 frontier 里取节点的顺序。广度优先BFS用队列先进先出。先访问的节点先扩展效果是一层一层往外扩。它保证找到的是步数最少的解。深度优先DFS用栈后进先出。它一路往下钻撞到死胡同再回来。空间占用小但不保证最短还可能因为图里有环而陷入无限循环。为什么 BFS 能保证最短原因在于它按层扩展第一次遇到目标状态时一定是所有通往目标的路径里层数最少的那条。这个性质建立在每条边代价相同的前提上。如果边代价不同比如不同动作的耗时不一样BFS 就失效了得换成一致代价搜索。DFS 的死循环问题在状态空间图上尤其容易踩。因为图里有环深度优先可能 A→B→A→B 无限转下去。解决办法就是前面提到的已访问集合。但要注意加了已访问集合的 DFS 已经变成了图搜索而不是树搜索它在某些情况下会找不到解这是有向图上搜索的固有代价。6.2 closed 表和重复状态检测正规的图搜索算法里有三个结构frontier也叫 open 表待扩展的节点集合用优先队列或者双端队列实现。closed 表已经扩展过的节点集合用来防止重复扩展。parent 表记录每个节点是从哪个节点来的找到目标后靠它回溯路径。closed 表的实现方式影响很大。用列表存每次判断if state in closed是 O(n) 的线性扫描状态一多程序就会卡死用集合或字典存判断是 O(1)这是标准做法。我见过有同学的八数码程序跑了两分钟没出结果改成 set 之后 0.2 秒跑完就是这个原因。还有一个细节parent 表要在生成子节点时写入而不是扩展时写入。写法是如果子节点既不在 frontier 也不在 closed 里就把它加进 frontier 并记录父节点。这样能保证每个状态在 frontier 里只出现一次省内存也省时间。6.3 启发式函数怎么设计才可采纳A* 算法是 BFS 的升级版它给每个节点打分f(n) g(n) h(n)。g 是从起点走到当前的已知代价h 是对从当前走到目标还要多少步的估计。h 的设计要满足可采纳性估计值永远不能超过真实值即h(n) h*(n)。一旦 h 估计过头A* 就可能错过最优解。八数码里有两个经典的 h错位数字个数数一下有多少个数字不在目标位置上。这个估计肯定不超标因为每个错位的数字至少要动一步。曼哈顿距离之和每个数字当前位置到目标位置的横纵坐标差之和。这个估计更紧搜索效率高得多而且它依然可采纳因为一次移动只能让一个数字的曼哈顿距离减少 1。实测下来同一个困难初始状态用错位数当 h 大约要扩展几千个节点用曼哈顿距离只要几百个差距非常明显。所以写作业时我一般直接上曼哈顿距离代码多不了几行效果立竿见影。要提醒的是曼哈顿距离对八数码是可采纳的但换成只能斜着走的棋盘就不一定了。可采纳性永远针对具体的问题和具体的动作集合没有放之四海皆准的启发式函数。7. 用 Python 把状态空间图跑起来7.1 一个通用的图搜索骨架我把 BFS 的逻辑抽成一个通用函数只要传入初始状态、目标判定和邻居生成器就能跑四种例题共用同一套骨架from collections import deque def graph_search(init, goal_test, neighbors): frontier deque([init]) parent {init: None} while frontier: state frontier.popleft() if goal_test(state): path [] while state is not None: path.append(state) state parent[state] return path[::-1] for nxt, action in neighbors(state): if nxt not in parent: # 生成时查重避免重复入队 parent[nxt] state frontier.append(nxt) return None这段代码有三个关键点parent字典同时承担了 closed 表和路径记录两个职责查重放在生成子节点时而不是扩展当前节点时路径回溯用path[::-1]反转。看起来简单但每一处都是踩过坑之后定下来的写法。7.2 八数码的完整实现GOAL (1, 2, 3, 4, 5, 6, 7, 8, 0) def neighbors_8p(state): i state.index(0) r, c divmod(i, 3) for dr, dc, name in ((-1, 0, 上), (1, 0, 下), (0, -1, 左), (0, 1, 右)): nr, nc r dr, c dc if 0 nr 3 and 0 nc 3: j nr * 3 nc lst list(state) lst[i], lst[j] lst[j], lst[i] yield tuple(lst), name def solvable(state): seq [x for x in state if x ! 0] inv sum(1 for i in range(len(seq)) for j in range(i 1, len(seq)) if seq[i] seq[j]) return inv % 2 0 start (2, 8, 3, 1, 6, 4, 7, 0, 5) if not solvable(start): print(该状态无解) else: path graph_search(start, lambda s: s GOAL, neighbors_8p) print(解的长度, len(path) - 1) for step, node in enumerate(path): print(f第 {step} 步: {node})跑之前先判断可解性这一步能帮你省掉一次漫长的等待。上面的start是一个经典的中等难度初始状态BFS 大概几秒内能出结果。如果你想要更快的版本把 BFS 换成 A*用heapq维护优先队列h 用曼哈顿距离。7.3 水壶问题的完整实现CAP (4, 3) def neighbors_wj(state): a, b state # 装满 yield (CAP[0], b), 装满 4L yield (a, CAP[1]), 装满 3L # 倒空 yield (0, b), 倒空 4L yield (a, 0), 倒空 3L # 互相倒 t min(a, CAP[1] - b) yield (a - t, b t), 4L 倒入 3L t min(b, CAP[0] - a) yield (a t, b - t), 3L 倒入 4L path graph_search((0, 0), lambda s: s[0] 2 or s[1] 2, neighbors_wj) for step, node in enumerate(path): print(f第 {step} 步: {node})注意目标判定用的是任意一个壶里有 2 升而不是某个具体状态。这正是前面强调的目标条件要按题意写松一点。8. 手画状态空间图时最容易翻车的几个地方8.1 状态变量漏项这是第一大坑前面反复提过。传教士问题漏了船的位置狼羊菜漏了农夫的位置八数码漏了空格的位置。判断自己有没有漏用一句话自检给我这个状态我能不能唯一确定下一步所有可能的走法如果答不上来说明状态描述不完整。8.2 把不合法状态也画进图里传教士问题里那些某岸野人多于传教士的组合属于约束违规压根不该出现在状态空间图里。有些同学图省事先把 32 种组合全画出来再在旁边标注哪些不合法考试的时候这样画是要扣分的。正确的做法是先筛后画图里只保留合法节点。8.3 忘记标注边上的算符状态空间图的边是有语义的每条边对应一个具体动作。手画的时候最好在箭头旁边写上动作名称比如狼过河装满 3L而不是光秃秃一条线。这在批改时是重要的得分点也能帮你在后面找路径时快速复述出解法的每一步。8.4 认为目标状态唯一水壶问题、狼羊菜这类题目标往往是一类状态而不是一个点。如果你按必须精确等于某个状态去判断很容易搜不到解或者搜出一条莫名其妙的路径。8.5 深拷贝和浅拷贝写代码的同学容易在这里翻车。八数码生成子状态时如果你直接修改原列表再把它存进去后面的所有节点都会指向同一个对象图就全乱了。正确做法是每次都list(state)造一个新列表再转成元组。我一般干脆全程用元组lst list(state)只在生成的那一刻临时用一下转换完立刻丢弃。8.6 用递归写 DFS 导致栈溢出Python 默认递归深度限制是 1000 层。状态空间图稍微大一点递归版的 DFS 就会抛RecursionError。建议用显式的栈来写迭代版本既安全又能清楚地看到 frontier 的变化过程。9. 我个人的几条经验第一画图之前先把状态定义写在纸上标清楚每个变量的取值范围然后再动手。这一步花三分钟能省掉后面半小时的重画。第二先算状态总数再估图的大小。传教士问题 20 个状态水壶问题 20 个狼羊菜 16 个八数码 18 万。数字心里有底之后你就知道该用 BFS 还是该上 A*也大概能预判程序会跑多久。第三遇到搜索跑不出来先怀疑状态定义再怀疑算法。我个人的排查顺序是逆序数八数码→ 目标判定是不是写太严 → 算符是不是漏了 → 查重是不是写错 → 最后才去看算法本身。这个顺序几乎每次都能命中问题所在。第四把每道题的解路径打印出来人工走一遍。程序说 11 步能过河你就拿纸笔按这 11 步走一遍看看有没有哪一步之后某岸的野人比传教士多。这个过程很枯燥但能帮你抓住绝大多数逻辑错误比盯着代码看有效得多。第五如果时间充裕把同一道题用 BFS、DFS、A* 各写一遍对比扩展节点数。这个对比会让我对启发式函数值多少钱这件事有非常具体的感受也更容易在考试里判断出题人到底想考哪个算法。最后说一个小的调试技巧。状态用元组存的时候打印出来是一串数字很难看。写一个render(state)函数把它还原成棋盘或者两岸的示意图调试效率能提升一大截。我至今保留着这个习惯写任何状态空间相关的代码第一个函数永远是这个渲染函数。