从农夫过河理解状态空间搜索：状态编码与BFS/DFS

简介：《人工智能 狼 羊 白菜 农夫过河》是一份面向计算机科学与人工智能初学者的经典逻辑推理题学习文档，围绕有限状态机、状态空间搜索与约束条件展开，适合用来练习DFS、BFS及动态规划设计。压缩包内仅含1个doc文件，大小约371KB，篇幅集中，便于直接阅读和整理笔记。目前已有3849人学习，说明该题在算法入门与课程练习中具有较高参考价值。文档以四元组描述农夫、狼、羊、白菜的位置，定义左右岸操作符与安全约束，并梳理先带羊、先带菜两类过河策略，配合状态转移思路展示从初始状态到目标状态的搜索过程，可帮助读者理解回溯、状态合法性判断及用程序自动求解的方法。

1. 状态空间：为什么农夫过河的本质是一张 10 个节点的有向图

大多数人第一次解“农夫、狼、羊、白菜过河”时，靠的是在纸上反复推演，试到某一步突然发现问题成立。但如果让计算机解这道题，几乎没人会教它“推理”，标准做法是把整个局面压成 16 个四元组，砍掉不合法的，剩下的连成一张图，然后在图上找一条从起点到终点的路径。这套视角的价值不在于这道题本身，而在于它是“用状态空间搜索替代人类直觉”能运行的最小样本：走迷宫、解数独、拼图、任务调度，骨架完全一样，只是状态编码和约束函数换了皮。搞懂这一步转换是怎么发生的，你就拿到了理解一大类搜索算法的钥匙。

2. 状态编码：(L, J, M, N) 四元组为什么能完整描述一次博弈

2.1 为什么农夫自己也得占用一个二进制位

最直觉的编码是只记三样东西：狼在哪、羊在哪、菜在哪，3 个 bit，8 种组合，看起来够用。但这样写出来的程序一定跑不通。原因在于船的移动规则，船只能跟着农夫走：农夫在左岸，下一步就只能从左岸出发；农夫在右岸，下一步就只能从右岸出发。因此，农夫的位置实际上是一个“回合指示器”，而不仅仅是一个普通元素。若缺少它，你就无法区分当前是谁的回合，也就不知道哪些动作在当下是合法的。

补上这一位之后，状态变成(f, w, s, c)，每个分量取 0（左岸）或 1（右岸），总共 2⁴ = 16 种组合。这个规模小到可以全部列出，这是本题作为教学案例的最大便利：状态空间小到可以被完全列出，所有边都能用眼睛数出来。

# 状态四元组：(farmer, wolf, sheep, cabbage) # 0 表示在左岸，1 表示在右岸 START = (0, 0, 0, 0) # 全部在左岸 GOAL = (1, 1, 1, 1) # 全部在右岸

参数顺序一旦定下来就不能乱，后面所有safe()、move()都依赖这个下标约定。我习惯把农夫放第 0 位，因为它是唯一一个“每步必变”的分量，写在最前面读代码时最省心。

2.2 把食物链翻译成 safe()：判断粒度是“岸”，不是“全局”

题目给的关系是“狼吃羊、羊吃菜”。这个关系有一个关键前提：只有在农夫不在场时才会触发。农夫只要和它们待在同一岸，这一岸就是安全的；危险永远发生在农夫不在的那一岸。

所以合法性判断不能写成“狼和羊不能同岸”，那是错的。正确写法是把两岸分开看，只检查没有农夫的那一岸：

def safe(state): f, w, s, c = state # 农夫不在的那一岸才可能出事 # 狼和羊同岸，且农夫不在这一岸 -> 羊被吃 if w == s and f != w: return False # 羊和菜同岸，且农夫不在这一岸 -> 菜被吃 if s == c and f != s: return False return True

注意f != w这个条件。有人会写成f == 0，理由是“农夫在左岸时右岸无人看管”这半句确实成立，但另一半就漏掉了：农夫在右岸时，左岸同样无人看管。写成f != w，让判断相对于农夫当前位置，左右两侧就自动对称了，不用写两遍。

还有一处容易出错的地方：题目里列的六个“约束状态”，其实混了两类东西。(1,0,0,1)、(1,1,0,0)、(0,1,1,0)、(0,0,1,1)、(1,0,0,0)、(0,1,1,1) 这六个里，前两个和后一个是安全的，中间三个恰恰是危险状态。我第一次照着题面理解时，把它们全当成了“允许出现的状态”，结果搜索怎么都走不通。区分方法很简单：拿safe()跑一遍，返回 False 的就是要淘汰的。

2.3 16 个状态里其实只有 10 个能活下来

把 16 个组合全过一遍safe()，结果是 10 个合法、6 个非法。这个数字值得记下来，因为它是你验证自己代码写没写对的第一道关。

表里最后一行 (1,0,0,0) 值得单独说一句，因为它在原题里被列成了约束状态，看起来像是允许的。但农夫在右岸、三样东西全在左岸、无人看管，狼和羊待在一起，羊和菜待在一起，这显然不该成立。这类“看着像合法”的条目就是检验有没有真跑过safe()的试金石。

合法状态里有 10 个，其中有出边的更少。起点 (0,0,0,0) 只有一条出边，这直接解释了题面里“第一次人只能带羊”的结论：不是推理出来的，是枚举出来只剩这一条。

3. 操作符 L(i)/R(i)：一次“带谁过河”怎么变成可枚举的动作

3.1 方向由农夫决定，物品也要由农夫决定，两个维度别混

原题定义了 L(i) 和 R(i) 两组操作符，L 表示向右，R 表示向左，i 取值 0 到 3 分别对应农夫自己、狼、羊、菜。看起来是 8 个动作，实际上任意时刻能用的只有其中几个：方向那一半由农夫位置唯一确定，物品那一半必须满足“东西和农夫在同一岸”。

这里有个思维上的小坎。很多人第一反应是写两个函数go_right()和go_left()，各自内部再分支处理带什么。这样写不算错，但会让搜索代码出现两层循环和一堆 if，越写越乱。更干净的做法是把方向合并进状态转移：不管当前在哪边，动作都是“农夫换到对岸，可选地捎上一个与自己同岸的物品”。方向不再是一个参数，而是由状态自己决定。

# 物品下标：0=农夫自己，1=狼，2=羊，3=菜 # 返回新状态；动作非法则返回 None def move(state, i): f, w, s, c = state new = [f, w, s, c] # 船必须由农夫划，所以农夫一定换岸 new[0] = 1 - f if i != 0: # 只有和农夫原来在同一岸的物品才能被带走 if new[i] != f: return None new[i] = 1 - f return tuple(new)

new[i] != f这一行比较的是物品的原位置（此时new[i]还没被改写）和农夫的原位置f。顺序不能反，先把new[i]改成1 - f再比较，就变成永远相等了。这种下标和赋值顺序的错误，调试时极难发现，因为代码不报错，只是悄悄地允许了“隔空取物”。

3.2 为什么“空手过河”必须被建模成一个正式动作

原题的分析里反复出现“空手回到 a”“优先选择空手过河”，说明空手是一个真实存在的步骤，不是可省略的细节。把它统一成i = 0之后，动作空间固定为 4 个候选，搜索代码只有一层for i in range(4)，不需要为“空手”写任何特判分支。

如果反过来，只允许带东西过河，然后另写一个cross_alone()函数，代码会立刻分成两条路径：主循环里一堆“带东西”的逻辑，旁边再挂一个“单独过河”的调用。功能上没问题，但一旦要统计步数、记录路径、做去重，两条路径就得各写一遍，很快就乱。统一动作空间是典型的“用一个稍微抽象一点的表示，换掉一堆同构分支”的取舍。

反过来说，这个抽象也有代价：i = 0在语义上是一个占位符，读代码时需要在脑子里把它翻译成“什么也不带”，可读性略打折扣。我一般会在枚举动作的地方加一行注释说明，让后来人不用猜。

3.3 动作空间的实际有效规模

把这套动作生成规则跑遍 10 个合法状态，会发现每个状态的出边数在 1 到 4 之间，平均下来接近 2.4。这个数字解释了为什么哪怕用最朴素的深度优先搜索，这道题也是瞬间出结果：搜索树的分支因子小，深度也只有 7 层，最坏情况下的节点数连一百都不到。

同一套规则放到别的问题上就不一样了。八数码问题平均分支因子接近 3，但最短解动辄二三十步，搜索树规模是指数级的；十五数码更夸张。所以“小分支因子 + 浅深度”是这道题能被当作手算练习的前提，也是它适合作为算法第一课的原因：算法本身的所有结构都在，但不会被规模问题掩盖。

4. 搜索：BFS 为什么天然出最短解，DFS 为什么容易绕圈

4.1 广度优先的队列，以及判重时机这个细节

有了状态编码、合法性判断、动作生成这三块，搜索本身只剩十几行。标准写法是用队列做广度优先：

from collections import deque def bfs(start=START, goal=GOAL): queue = deque([(start, [])]) seen = {start} while queue: state, path = queue.popleft() if state == goal: return path + [state] for i in range(4): nxt = move(state, i) if nxt is None: continue if nxt in seen: continue if not safe(nxt): continue seen.add(nxt) # 入队前就标记，不是出队时 queue.append((nxt, path + [nxt])) return None

这段代码里最要紧的不是队列，而是seen.add(nxt)的位置。同一层的多个父节点完全可能生成同一个子状态，如果等到出队时才判断“访问过没有”，队列里会堆满重复项。更隐蔽的问题是步数：只有做到“一生成就标记”，才能保证某个状态第一次被放进队列时，走的就是到达它的最短路径。晚一步标记，最短性就无法保证。

另外两点值得注意。safe(nxt)检查的是移动之后的状态，起点本身也该检查一次（本题起点合法，但换一道题未必能安全地略过）。path + [nxt]每次都复制整个列表，代价是 O(路径长度)，状态少的时候完全无所谓，是个明确的可读性优先的取舍。

4.2 深度优先的教训：不维护访问表就是无限循环

有人觉得既然只有 10 个节点，随手写个递归 DFS 更快。写完一跑，程序不返回。

原因非常简单：i = 0这个动作让“农夫空手过去”和“农夫空手回来”构成一对互逆动作，两者永远合法。不加任何防护的话，递归会在 (0,0,0,0) 和 (1,0,0,0) 之间来回跳跃……等一下，(1,0,0,0) 是非法的，因为三样东西全在左岸且无人看管。所以实际发生的是在另一个合法对之间来回。但只要存在任意一对互逆的合法动作，递归就停不下来。这是所有状态空间搜索都必须维护访问表的根本原因，不是优化，而是正确性要求。

DFS 加了seen之后能跑通，但它找到的是“第一条走得通的路”，不保证最短。在本题上，DFS 按i = 0,1,2,3的顺序枚举，很容易先走上一条绕远的支路。探索性搜索用 DFS 没问题，要求最短解就必须换 BFS。

4.3 两种搜索在这张图上的真实表现

手工推一遍最短解，是 7 次渡河：

(0,0,0,0) 起点 (1,0,1,0) 带羊过去 (0,0,1,0) 空手回来 (1,1,1,0) 带狼过去 (0,1,0,0) 带羊回来 (1,1,0,1) 带菜过去 (0,1,0,1) 空手回来 (1,1,1,1) 带羊过去，完成

每一步都能用safe()验证。第 4 步“带羊回来”是整条路线的枢纽：如果不把羊带回来，农夫的下一步就会被羊和菜同岸、狼和羊同岸这两个约束同时卡死。这道题的巧妙之处在于它有一个“必须回头”的动作，人的直觉往往不愿意往回带东西，而算法不在乎，它只在乎约束。

有意思的是，这个 7 步解不是唯一的。把狼和菜的处理顺序对调，能得到另一条同样 7 步的路径。题面里列的“选择一”和“选择二”正是这两条，它们在图上是两条对称的支路，最终汇入同一个目标状态。搜索算法返回哪一条，取决于枚举顺序，这在实际工程里意味着“算法给出的最优解”和“人认为合理的解”可能并不一致。

5. 排查与避坑：为什么你的程序会“找不到解”或者“绕死自己”

5.1 现象：跑完返回 None，但人明明解出来了

原因通常是状态编码少了一位，最常见的是把农夫漏掉了，只用三位表示狼羊菜。三位状态下，safe()里的f无从取值，只能臆造一个“假设农夫在左岸”，于是所有右岸场景全被算错，搜索自然走不通。

解决办法是加一行断言，把合法状态的总数打出来：

legal = [st for st in range(16) if safe(tuple((st >> k) & 1 for k in (3, 2, 1, 0)))] assert len(legal) == 10, f"合法状态数不对，实际 {len(legal)}"

10 这个数字是手算过的基准值，对不上就说明约束函数或编码有错，不用往下查搜索逻辑。这种“先验证中间量”的习惯，比盯着搜索代码一行行看有效得多。

5.2 现象：程序不返回，或者返回一条几百步的解

原因是没维护seen集合，或者只在递归返回后标记、返回前又撤销了标记。前者导致无限循环，后者在不要求找所有解的场景下会把同一片区域反复搜索很多遍，路径长度失控。

解决办法是区分两种需求：只要一条解，标记后就不要再撤销；要枚举所有解，才需要在回溯时恢复标记，代价是指数级的时间。这两种语义混用是搜索类代码最常见的出错点。

5.3 现象：解出来了，但步数比 7 多

用了 DFS，或者 BFS 里把seen.add挪到了出队之后。前者是算法选择的问题，后者是实现的疏漏。判断方法很直接：打印路径长度，7 是这道题的下界，任何大于 7 的解都说明搜索策略不对。

顺带一提，如果连“7”是怎么来的都不确定，那说明约束还没吃透。可以数一下渡河次数：过去、回来、过去、回来、过去、回来、过去，一共 7 次。这个次数和物品数量、食物链的耦合方式有关，换个规模就不一定是 7 了。

5.4 现象：路径里出现“农夫从右岸带回一个本来就在右岸的菜”这类非法动作

原因是move()里漏了同岸校验，或者校验的比较对象写错了。船不能凭空搬运对岸的东西，这个约束必须落在动作生成阶段，而不是靠后面的safe()去兜底，因为safe()只看结果状态，看不到这个过程是否合法。

解决办法是回到move()，确认比较的是物品的原位置和农夫的原位置。测试方法是单独构造几个应该被拒绝的调用，看是不是真的返回了 None。

5.5 现象：状态数对得上，但搜索走了一条不可能出现的路

顺序上漏了safe(nxt)，或者把它写成了safe(state)。前者会让“狼吃羊”的边进入图里，后者则等于什么都没检查。这类错误不会报错，只会让答案看起来“多了一条捷径”，非常难察觉。

解决办法是把safe()的调用写进生成后继的循环内部，紧跟move()之后，别隔开。代码里离得近，就少一个忘记的机会。

6. 设计取舍：状态去重、搜索方向与“人工解”为什么不是最优解

把这道题完整解出来之后，回头看会发现人的解法和机器的解法走的不是同一条路。人靠的是约束传播，从“第一次只能带羊”这个必然结论出发，一步步倒推；机器靠的是枚举加剪枝，把所有状态摆出来，砍掉非法的，然后在剩下的边上走一遍。两条路最终交会在同一张图上，这张图才是问题的本体，推理和搜索只是两种遍历它的方式。

这带来一个容易被忽略的设计取舍：状态怎么编码。用元组(f, w, s, c)最直观，可读性最好，代价是每次比较和哈希都要逐个元素展开；用位掩码压成一个 0 到 15 的整数，判重和位运算都快得多，但调试时打印出来是一串数字，读起来费劲。本题只有 10 个合法状态，元组的开销可以忽略。可一旦换成八数码或者十五数码，状态数上到 10⁵ 甚至 10⁶ 量级，编码方式就直接决定了哈希表的内存占用和查询速度，这时候位压缩不再是可选项，而是必需项。

另一个取舍在搜索策略本身。BFS 的内存是 O(b^d)，DFS 只要 O(d)，本题 b≈2.4、d=7，BFS 的队列长度根本不会超过两位数，选它毫无压力。但在真实问题里，这个选择经常是生死线：棋盘类搜索深度二三十层，BFS 会被内存直接拖垮，这时候要么上迭代加深，要么引入启发式函数把“盲目搜索”换成“有方向搜索”。我一般会这么理解：BFS 保证最短但吃内存，DFS 省内存但只保证有解，启发式搜索两头都不保证，靠一个好的评估函数来换实际性能。

有一次我做一道类似的约束搜索题，状态里只编码了物品的位置，忘了把“操作者”这一维放进去，结果 BFS 在 8 个状态里反复横跳，怎么都解决不了。查了两个小时，最后发现整个状态空间被压扁了一半，所有本该区分开的局面都混成了同一个。那次之后，我每次写搜索之前都强制先做一件事：手动算出合法状态的个数，写成断言放在代码最前面。数字对不上，后面的工作都不用做。这个习惯帮我避开的问题，比任何调优技巧都多。希望帮到你。

本文还有配套的精品资源，点击获取