简介：经典“农夫过河”是人工智能与算法课程中讲解状态空间搜索的典型题目，这份 Word 文档面向初学搜索算法、准备实验或复习图论基础的读者，系统整理了题目分析、四元组状态定义、操作符设计及约束状态，并详细比较了“先带羊过河”与“先带菜过河”等策略的逐步推导。包体信息很轻量，压缩包仅 1 个文件、以 doc 文档形式呈现，总大小 371KB，无需复杂环境即可阅读。当前已有 3839 人学习参考，适合快速入门。文档不仅提供了可直接验证的过河方案，还演示了如何用有限状态机、DFS/BFS 思路将问题建模并求解，帮助读者理解状态转移图的构建方法，为后续处理类似规划问题打下基础。
1. 人工智能大作业里的农夫过河：一个被低估的状态空间搜索模型
如果你在人工智能导论或算法课的大作业里遇到“农夫过河”，第一反应多半是“这不就是个脑筋急转弯”。但真把它当作一个搜索问题来写，你会发现它其实是理解状态空间搜索最干净的入口：状态怎么编码、转移怎么写、为什么BFS能找到最短路径、死循环怎么避免——这些问题全部压缩在一个只有几十个节点的模型里。它的规模小到可以手推验证，又复杂到足以暴露你对搜索算法的所有误解。这篇文章就沿着“状态设计 → BFS实现 → 去重避坑 → 搜索进阶”的顺序，把这条技术路线完整拆开。无论你是正在赶人工智能大作业，还是想补一条人工智能学习路径上的关键技能，这个题目都值得认真做一遍。
2. 把“人狼羊菜”变成机器能算的状态：状态表示与转移规则设计
2.1 为什么五元组比二元组好用：状态编码的三种常见做法
农夫过河问题的本质是：四个对象（农夫、狼、羊、白菜）分布在河的两岸，农夫每次划船，最多带一个对象过河，要求任何时刻狼和羊不能单独在一起、羊和白菜不能单独在一起。第一次写这个题的人最容易犯的错误，是试图用“左岸有哪些对象”来描述状态。比如用{"农夫", "狼"}表示农夫和狼在左岸，其余在右岸。这个表示法能跑，但写转移的时候非常别扭——你要频繁判断“某个对象在哪岸”，而集合的包含判断在代码里又啰嗦又慢。
我一般推荐用五元组(farmer, wolf, sheep, cabbage)，每个分量取值0表示左岸、1表示右岸。这样状态从(0,0,0,0)（全部在左岸）出发，目标是(1,1,1,1)（全部到右岸）。为什么五元组比集合好？因为它天然对应“哪岸”这一布尔语义，转移时只需翻转对应分量的值。而且五元组可以压缩成一个四位的二进制数——最多16种组合，配合一个visited布尔数组就能去重，连哈希表都省了。这不是性能问题，是代码可读性和正确性问题。
还有一种常见做法是“位置数组”，把四个对象的位置存成[0,0,0,0]这样的列表。Python里列表可以做相等比较，放进集合去重也没问题。但列表是可变对象，放进集合前必须转成元组，否则会报TypeError: unhashable type: 'list'。这个坑我在下面的避坑章节里还会展开。总之，状态表示的第一原则是：让转移操作尽量简单，让去重操作尽量安全。五元组在这两个维度上都是最优解。
2.2 状态转移函数：卡住新手的第一道坎
有了状态表示，下一步是写转移函数。这也是这个题里最容易“逻辑对但代码错”的地方。转移规则可以归纳成三条：
- 农夫必须和船在同一岸，也就是说只有
farmer所在的岸才能发起转移。 - 农夫可以单独过河，也可以带一个对象过河，所以每次转移最多翻转两个分量：农夫必翻，可选另一个对象同翻。
- 转移完成后，新状态必须满足安全约束——狼和羊不能在没有农夫的一岸单独相处，羊和白菜同理。
按这个思路，BFS里对当前状态的展开逻辑就是：先把农夫翻到对岸，得到一个“农夫独自过河”的候选状态；再依次检查狼、羊、白菜是否和农夫在同一岸，如果是，就把该对象也翻过去，得到“农夫带某物过河”的候选状态。最多4个候选，逐个做安全性和重复性检查。这段逻辑写成代码只有十来行，但很多人会在这里把“单个对象翻转”和“农夫翻转”的顺序搞混。正确的做法是翻转发生在检查之后——先判断对象是否在农夫所在岸，再翻。
这里还有一个容易忽略的细节：当农夫不在某一岸时，该岸的狼和羊会不会吃掉对方？答案是“会”的前提是它们在同一岸且没有农夫。所以安全判定函数必须以农夫位置为条件：如果农夫在左岸，那么右岸不能同时有狼和羊，也不能同时有羊和白菜；反之亦然。这个函数写不对，整个搜索要么漏解，要么给出非法路径。
2.3 安全约束：判定条件要先于搜索写对
安全判定是整个搜索正确性的基石。我的做法是单独写一个is_valid(state)函数，返回布尔值，而且只用一行表达式。具体逻辑是：分别取狼、羊、白菜的位置，如果狼和羊位置相同且与农夫位置不同，则非法；如果羊和白菜位置相同且与农夫位置不同，则非法。注意这里用的是“与农夫位置不同”——换句话说，只要农夫在场，狼羊同岸是允许的，因为农夫看着它们。很多人会把这个条件错写成“狼和羊在同一岸就非法”，那样的话初始状态和目标状态都会被判非法，搜索直接空手而归。
写这个函数的时候有个技巧：先写注释，把四种非法场景列出来，再写代码。我见过有同学用“农夫是否在左岸”作为条件分支，然后在每个分支里硬编码右岸/左岸的非法组合——这样也能对，但一旦状态编码从0/1改成True/False，或者从五元组改成三元组，就得重写。用“位置不同”这一条判断逻辑，跟状态编码细节解耦，后面改起来省很多事。
还有一个验证方法：把合法状态全部打印出来，人工数一遍。这个题目的合法状态一共只有10个左右，加上农夫位置的变化，完整状态空间也就27个节点。打印出来核对一遍，比你对着代码 review 十遍都管用。
3. 用BFS在本地跑通最小可行代码：完整实现与逐行说明
3.1 最小命令：20行核心搜索逻辑能跑通
状态空间搜索的经典算法是广度优先搜索（BFS），因为它保证第一次到达目标状态的路径就是最短路径。对于农夫过河这种无权图搜索，BFS是最简单也最不容易出错的选项。下面这段代码是我整理过的最小可运行版本，去掉了所有打印装饰，只保留核心逻辑：
from collections import deque def is_valid(state): f, w, s, c = state # 狼和羊同岸且农夫不在场：非法 if w == s and w != f: return False # 羊和白菜同岸且农夫不在场：非法 if s == c and s != f: return False return True def bfs(): start = (0, 0, 0, 0) goal = (1, 1, 1, 1) queue = deque([start]) visited = {start} parent = {start: None} while queue: state = queue.popleft() if state == goal: break f, w, s, c = state # 农夫总是要过河的，翻转农夫位置 nf = 1 - f # 候选1：农夫独自过河 candidates = [(nf, w, s, c)] # 候选2-4：农夫带一个对象过河 if w == f: candidates.append((nf, 1 - w, s, c)) if s == f: candidates.append((nf, w, 1 - s, c)) if c == f: candidates.append((nf, w, s, 1 - c)) for nxt in candidates: if is_valid(nxt) and nxt not in visited: visited.add(nxt) parent[nxt] = state queue.append(nxt) else: print("无解") # 本题必然有解，但保留这个分支 return # 回溯路径 path = [] cur = goal while cur is not None: path.append(cur) cur = parent[cur] path.reverse() return path path = bfs() for step in path: print(step)这段代码的核心就是bfs()函数里的 while 循环。每次从队列头部取出一个状态，生成最多4个候选转移，逐个做安全判定和去重检查。parent字典记录每个状态的前驱节点，用于最终回溯路径。这里的visited用集合存状态元组，Python 元组可以哈希，所以直接塞进集合没问题。运行结果应该是11步，这是最短路径长度。
3.2 队列设计与路径回溯：拿到的不只是“能不能过”
很多人以为 BFS 跑到目标状态就算完事，但大作业评分往往要求你输出“农夫怎么走的每一步”。路径回溯靠的是parent字典——你在扩展新状态时，把parent[nxt] = state存下来，记录“这个状态是从哪个状态来的”。BFS 保证第一次发现某个状态时，到达它的路径就是最短的，因此parent里存的也是最优前驱。
回溯的细节值得注意：我从goal开始往前找，一直找到parent为None的初始状态，然后reverse。这里有个隐性假设——初始状态的parent必须设为None。如果你忘了初始化，回溯时会因为KeyError中断。另一个容易翻车的点是：如果你在 BFS 里用if state == goal: break提前退出，那么queue里可能还留着未扩展的状态，但它们不会影响parent，回溯依然正确。
关于队列选择：Python 里用collections.deque而不是列表，这是因为列表的pop(0)是 O(n) 操作，而deque.popleft()是 O(1)。这个问题状态空间极小，列表的性能差异你感知不到，但养成用deque的习惯没坏处。如果你是给人工智能大作业交代码，助教可能会问队列为什么用deque——这个回答能体现你的工程意识。
3.3 参数怎么调：状态容量、访问集合与剪枝顺序
农夫过河的状态空间总共 2^4 = 16 种原始组合，加上安全约束剪枝后剩 10 个合法状态，再算上农夫位置，整个图只有 27 个节点。这个规模下，没有任何参数需要“调优”。但如果你想把这个方案推广到更大的搜索空间（比如 n 个对象过河），有几个参数和设计点是可调的：
第一个是visited的数据结构。小规模用set，规模上万时可以考虑位图——把状态编码成一个整数，用布尔数组做访问标记。比如把(f,w,s,c)编码成f*8 + w*4 + s*2 + c，然后visited就是一个长度为 16 的列表。这样做的优势是内存可控、查询 O(1)，劣势是代码可读性下降。我一般建议：作业代码用集合，工程代码用位图。
第二个是候选状态的生成顺序。把“农夫独自过河”放在最前面还是最后面，会影响搜索树的分支顺序，但不影响 BFS 的最短路径长度。不过如果你用的是 DFS 或迭代加深，候选顺序会直接影响第一个解的质量。在这个题里，我习惯把带羊的转移放在前面——因为羊是唯一与狼、白菜都有冲突的“核心对象”，优先处理它往往能更快逼近目标。
第三个是安全判定和去重的先后。我的代码先做is_valid再做visited检查，这是有讲究的：非法状态往往比重复状态多，先过滤掉非法状态，再去查集合，可以减少集合查询次数。在这个小问题上差别微乎其微，但搜索空间大时，这个顺序能省出可感知的时间。
4. 状态去重与环路检测：三个必避的坑和一次排查实录
4.1 坑一：对称状态导致的“假死循环”
第一次跑通 BFS 的同学可能会遇到一种诡异现象：程序不死，但就是不停扩展新状态，队列越来越长，永远到不了目标。我当年排查这个问题的过程很有代表性——打印前几层状态，发现(0,0,0,0)被扩展后生成了(1,0,0,0)和(1,1,1,0)（带白菜），然后下一步又出现(0,0,0,0)——显然，农夫带着白菜过去又回来了，这一来一回形成了一个长度为 2 的环路。
这是 BFS 的经典陷阱：无向图里每条边都是可逆的，如果不用visited记住曾经到达过的状态，搜索就会在回路里无限转圈。农夫过河这个例子里，最典型的回路就是“农夫独自过去，再独自回来”。你不去重，BFS 就会在这两个状态之间反复横跳。解决方式就是visited集合，它保证每个状态最多被扩展一次。这也是为什么我说visited不只是优化，而是正确性的一部分。
4.2 坑二：访问集合用列表而不是集合
有同学图省事，把所有访问过的状态放进一个列表，每次用if nxt not in visited_list做检查。在小状态空间里这确实能跑，而且结果也一样，但有两个隐患。第一个是性能：列表的in是线性扫描，状态空间一大，O(n^2) 的复杂度会拖垮搜索。第二个是语义混淆：列表允许重复元素，虽然你用的时候保证不重复插入，但代码读起来无法立即确认“这个列表是集合语义还是序列语义”。
正确的做法是用set。如果你担心集合和元组的哈希问题，记住：元组是不可变对象，天然可哈希；列表是可变对象，不能放进集合。一个常见的报错场景是：有人用列表存储状态，然后visited.add(list_state)，Python 立刻抛出TypeError: unhashable type: 'list'。这个报错本身是好事——它在运行时提醒你数据结构选错了。把列表转成元组再入集合，问题就解决。
4.3 坑三：把“岸边”建模成布尔值带来的边界问题
状态分量取值 0/1 表示左岸/右岸，这很直观，但边界操作容易踩坑。比如判断“农夫和羊是否在同一岸”时，新手可能会写if farmer == sheep:，这没问题；但接下来翻转时写sheep = 1 - sheep，这在 Python 里也是对的，因为1 - 0 = 1，1 - 1 = 0。可是如果你用的是not运算符，比如farmer = not farmer，那状态就从0/1变成了True/False，而is_valid里如果写的是if w == s and w != f，False == 0在 Python 里是成立的，所以逻辑没错，但状态的哈希值变了——False和0的哈希值相同，但这不是问题；真正的隐患是你把状态类型混用了，(True, 0, 0, 0)和(1, 0, 0, 0)在集合里是同一个元素，可代码一混用，你打印路径时会看到True和1交替出现，观感很差。
我的建议是：全代码统一用整数 0/1，禁用not翻转。用1 - x而不是not x，这样从状态表示到打印输出，全部保持一致，不需要做类型转换。这个习惯看起来是小事，但混用布尔和整数是状态搜索作业里最常见的“隐性 bug 温床”。
4.4 排查方法：打印状态树一层一层看
如果搜索结果不对，我一般第一步不是改代码，而是把搜索过程可视化。BFS 天然适合分层打印：记录每个状态的前驱，然后从初始状态开始递归打印。我写过一个调试函数，把所有状态按“层数”分组输出，层数就是parent链的长度。这样你能一眼看出：是某一步转移写错了（生成了非法状态），还是去重失效（同层出现重复状态），还是目标不可达（状态空间被错误约束切断了）。
对农夫过河这个具体问题，有一个著名的调试验证点：合法状态数量。全部合法状态（含农夫位置）一共 27 个，其中可到达的从初始状态出发的合法状态是 10 个。如果你程序的visited长度超过了 27，那说明安全判定漏掉了某条规则，或者是把重复状态当成新状态了。这个数字可以作为硬性校验标准。
5. 从BFS向上走：A*搜索、双向BFS与状态空间规模分析
5.1 为什么这个问题的状态空间只有27个节点
你可能会奇怪前面的章节反复提到“27”这个数字。原因在于：四个对象的位置组合是 2^4 = 16 种，农夫的位置也参与转移，因此总状态空间是 2^5 = 32 种。但其中 5 种违背安全约束，——狼羊同岸且农夫不在场（2种）、羊菜同岸且农夫不在场（2种）、同时违背（1种，即狼羊菜都在同一岸且农夫在另一岸）。剩下 27 个合法状态。而从初始状态真正能到达的是 10 个状态（不含农夫位置的五种组合，加上农夫位置变化后的对偶状态），这构成一个连通分量。理解这个规模，是你要不要上 A* 的决策依据——27 个节点根本不需要启发式搜索，BFS 一步都不会多走。但如果你把它推广到 n 个对象，状态数会指数增长，这时 A* 才真正有优势。
5.2 双向BFS的改造点与代码差异
双向 BFS 的思路是同时从初始状态和目标状态向中间搜索，当两个方向的搜索前沿相遇时，路径即为最短。在 27 个节点的图上，双向 BFS 的优势是路径长度减半，扩展节点数大约从单方向的几十个降到十几个。但代价是代码复杂度翻倍，还要处理“相遇”状态的判断和路径拼接逻辑。
改造的核心有两点。第一，你需要两个visited字典（或者一个字典加方向标记），分别记录从起点和终点出发访问过的状态及其前驱。第二，每次扩展时先检查新状态是否在另一方向的visited中出现，如果出现，就把两个方向的路径拼起来。拼接时注意方向：从起点方向拿到的路径是正序，从终点方向拿到的是逆序，需要先reverse再拼接。双向 BFS 在这个题上没有实际性能收益，但它是你理解“启发式思想”的第一步——搜索方向的选择本身能带来指数级的效率差异。
5.3 启发式函数怎么设计才不算作弊
如果你非要给农夫过河加一个 A* 搜索，启发式函数的设计是个有趣的话题。常见且有效的启发式是：当前还在左岸的对象数量。因为每次最多带一个对象过河，所以至少还需要“还在左岸的对象数”次过河——这被称为“每次移动至少改变一个对象的状态”的下界。注意这里的“对象”指狼、羊、白菜，不包括农夫（因为农夫每次必过河，不计入对象数）。用这个启发式，A* 会在 BFS 的基础上减少部分无效扩展，但在这个规模下看不出明显优势。
真正要紧的是另一个问题：这个启发式是否可采纳（admissible）？检查方法是看它是否高估了从当前状态到目标的实际代价。显然，“左岸对象数量”不超过实际剩余步数，因为农夫可以一次带一个对象，但还可以空船返回，实际步数必然大于等于左岸对象数量，所以这个启发式是可采纳的，A* 找到的路径依然是最优的。如果你写的是 1.5 倍的左岸对象数，那可能在复杂情况中失效。作业里遇到这种题，不建议硬套 A*——但如果课程要求实现 A*，用这个启发式作为对比实验会让人工智能导论老师眼前一亮。
6. 一个能带到其他问题里的搜索框架：封装与验证技巧
6.1 把BFS封装成通用状态搜索类
做完农夫过河这道题，你会发现 BFS 的骨架与具体问题无关：队列、访问集合、前驱字典、目标判定、邻接生成——只有后两步是问题相关的。为了让你后面遇到八数码、迷宫求解、华容道作业时能复用，我建议把 BFS 封装成一个通用的状态搜索类。核心接口就两个：get_neighbors(state)返回所有合法邻接状态，is_goal(state)判断是否到达目标。逻辑可以这样写：
class StateSearch: def __init__(self, start, goal, get_neighbors, is_goal=None): self.start = start self.goal = goal self.get_neighbors = get_neighbors self.is_goal = is_goal or (lambda s: s == goal) def bfs(self): from collections import deque queue = deque([self.start]) visited = {self.start} parent = {self.start: None} while queue: state = queue.popleft() if self.is_goal(state): return self._reconstruct(parent, state) for nxt in self.get_neighbors(state): if nxt not in visited: visited.add(nxt) parent[nxt] = state queue.append(nxt) return None def _reconstruct(self, parent, end): path = [] cur = end while cur is not None: path.append(cur) cur = parent[cur] return path[::-1]这个类的好处是：你换一道题只需要写get_neighbors和is_goal，搜索逻辑永远不用动。注意visited用集合，parent用字典，两者都是状态对象到状态对象的映射——只要状态可哈希，这套框架就能跑。这是我做了几个搜索课题后才总结出来的模式，建议你也把自己的代码按这个方向收敛，后面复用会省很多事。
6.2 验证方法：枚举所有解和最短路径长度对比
搜索引擎写完后，光跑通不算完，得验证正确性。这个题最硬核的验证方式是枚举所有最短路径：BFS 只能告诉你最短路径的长度和其中一条，而“最短路径一共有几条”这个数字可以作为交叉验证的参考。枚举方法是 DFS + 深度限制：限制深度为 11（已知最短长度），从初始状态出发递归，遇到目标就计数，途中状态不能重复出现在当前路径里。跑出来的结果应该是 若干条（这个题目的最短路径数量是确定的，但每条路径的体验不同，手动枚举就能验证）。
还有个更简单的验证点：最短路径长度必须是奇数。因为农夫每次从一岸到另一岸，都翻转位置，从全左岸 (0,0,0,0) 到全右岸 (1,1,1,1)，农夫位置从 0 变 1，需要奇数次过河。如果程序输出偶数步解，那必然是状态表示或目标判定写错了。这个验证我每次写状态搜索题都先用一遍，成本极低。
6.3 个人习惯：状态空间搜索作业的三个检查清单
以农夫过河为出发点，总结一下我多年交作业和改作业攒下来的自查清单。第一个是“对称性检查”：把狼和白菜对调位置，题目条件不变，那么搜索路径也应该镜像对称。如果你程序在对称输入下给出不同长度的解，恭喜你，bug 找到了——这两个对象在转移规则里是完全等价的，不可能出现不同最优解长度。第二个是“安全函数单元测试”：单独把is_valid对全部 32 种状态跑一遍，对照手写的合法状态表核对。第三个是“路径合法性逐行审计”：把输出路径的每一步都套进is_valid和转移规则里验算，不要用眼睛扫——写一个循环自动验。
这三个检查做完，你的搜索代码基本可以放心交了。顺便说一句，如果你正在赶人工智能大作业，别急着上那些花哨的可视化、GUI、多线程——先把 BFS 核心逻辑跑对，再考虑加分项。这个题目里 90% 的代码量都用不到，价值全在“状态建模到搜索闭环”这一条主线上。希望这篇笔记帮你把这一课真正吃透。
本文还有配套的精品资源，点击获取
