状态空间搜索实战：狼羊白菜过河BFS/DFS与Python实现

简介围绕“狼、羊、白菜、农夫过河”这一经典逻辑推理题整理的doc学习文档面向人工智能、计算机科学入门学习者及算法课程备课教师核心涉及有限状态机、状态空间搜索、约束条件判定与可行路径求解。压缩包内共1个doc文件约371KB内容覆盖题目描述与食物链约束分析、四元组状态表示、L/R操作符定义、非法状态判定以及先带羊或先带菜两类策略的逐步推演并延伸到DFS、BFS和状态转移图思路。已有3852人学习下载可用于课堂示例、搜索算法练习与逻辑思维训练读者可借此理解从问题建模、状态枚举到方案验证的完整流程也能据此编写自动求解程序或做算法对照实验。文档中对合法状态筛选、回溯尝试与搜索顺序的说明较具体适合作为状态空间类题目的入门案例和自动求解程序的建模参考。1. 别急着写 if-else这道人工智能 狼 羊 白菜 农夫过河真正要交的是搜索器很多人拿到这道题的第一反应是手推七个步骤然后把步骤写死成七行打印语句。演示时被问一句换成三样别的物品还跑得动吗就卡住了。这道人工智能课里被反复使用的经典题本质是状态空间搜索的最小完整样本状态怎么定义、操作符怎么设计、约束怎么判、搜索怎么终止四件事全齐一件都不能含糊。这套方案面向两拨人一拨是要交人工智能导论、算法设计课设的同学需要一个能跑、能演示、经得起追问的完整结构另一拨是想把搜索框架沉淀成模板的开发者后面遇到调度、路径规划这类问题直接套用。下面从状态建模写到搜索实现再写到工程化和验收代码用 Python可以照着跑通。2. 状态建模四元组、约束函数与十种合法局面这道题最容易翻车的地方不在算法在建模。建模一旦漏了某个维度后面搜索写得再漂亮也是错的。这一章把状态怎么定义、约束怎么写、合法局面一共有多少一次说清楚。2.1 把局面压成四元组位序约定与初始/目标状态题目里人、狼、羊、菜各有左岸/右岸两种位置四样东西组合起来就是 2 的 4 次方共 16 种局面。用四元组 S (L, J, M, N) 表示L 是农夫J 是狼M 是羊N 是菜0 表示在左岸1 表示在右岸。初始状态 S0 (0, 0, 0, 0)目标状态 G (1, 1, 1, 1)。这个表示法有三个好处缺一个都会在后面付出代价。第一是可哈希元组可以直接放进 set 做去重换成自定义对象就要自己实现__hash__和__eq__。第二是可比较两个状态相等就是逐位相等不需要写复杂的相等判断。第三是可压缩四位二进制正好对应一个 0 到 15 的整数用位运算压成整数后可以直接做数组下标状态表的访问从哈希查找变成 O(1) 寻址。我一般会在代码顶部把位序写死成常量并且所有函数都用同一套索引不允许某个函数用农夫在第 0 位、另一个函数用农夫在最后一位这种混搭。这类不一致在单文件小脚本里不容易暴露一旦拆成多文件就是血泪经验级别的排查成本。# 状态统一用四元组表示(农夫, 狼, 羊, 菜) # 取值 0 左岸1 右岸 # 位序固定索引 0..3 依次是 农夫、狼、羊、菜任何函数都不得改变这个约定 NAMES (农夫, 狼, 羊, 菜) START (0, 0, 0, 0) # 全部在左岸 GOAL (1, 1, 1, 1) # 全部到右岸 def encode(state): 把四元组压成 0..15 的整数用于数组下标或位图去重 f, w, s, c state return (f 3) | (w 2) | (s 1) | c def decode(code): encode 的逆运算便于调试时把整数还原成可读局面 return ((code 3) 1, (code 2) 1, (code 1) 1, code 1)encode里的移位顺序必须和decode完全对称 3拿最高位当农夫 1拿最低位当菜。写反了不会报错只会得到一堆看起来正常的错误结果这类 bug 排查起来最费时间。状态只有 16 种其实用元组做 key 完全够快整数编码更多是为了后面扩展到十几件物品时留出空间。2.2 约束条件写成布尔函数不要散落成一堆 if题目的安全规则只有两条没有农夫看管时狼和羊不能同岸羊和菜不能同岸。注意主语是农夫不在的那一岸。很多实现把它写成左岸不能同时有狼和羊结果农夫在左岸时明明看着也被判成不合法直接无解。正确的判法是先看农夫在哪再检查他不在的那一岸。农夫在左岸L0右岸无人看管查右岸有没有狼羊同岸或羊菜同岸农夫在右岸L1左岸无人看管查左岸。def is_safe(state): 合法状态判定农夫不在的那一岸不允许出现 狼羊 或 羊菜 f, w, s, c state if f 0: # 农夫在左岸右岸没人看着 if w 1 and s 1: return False if s 1 and c 1: return False else: # 农夫在右岸左岸没人看着 if w 0 and s 0: return False if s 0 and c 0: return False return True这里用存在即违规的短路写法四条判断任意命中就返回 False剩下情况一律合法。参数只有一个四元组没有副作用可以放心在搜索里被调用几万次。如果后面把物品从三件扩展到 N 件这个函数要重写成按食物链关系遍历相邻对而不是继续堆 if。另一种写法是枚举表事先把 6 个不合法状态列成集合判断时查表。这种写法在状态数很少时可读性极高缺点是扩展性差加一件物品就要重算整张表。两种方式的取舍见下表。写法实现方式优点缺点适用场景布尔函数按规则实时计算扩展性好规则改动只改一处每次调用有分支开销物品数大于等于 4、规则可能变化枚举黑名单预先列出不合法状态集合可读性强判定 O(1)状态一多就要重新枚举容易漏固定三件物品的教学演示2.3 十种合法局面与状态转移图16 种组合里有 6 种不合法剩下 10 种才是搜索真正会踩到的节点。把这张表列出来后面调试时对着看比盯着日志猜要快得多。序号状态 (L,J,M,N)农夫左岸右岸是否合法1(0,0,0,0)左农夫狼羊菜空合法初始2(0,1,0,0)左农夫羊狼合法3(0,0,1,0)左农夫狼菜羊合法4(0,0,0,1)左农夫狼羊菜合法5(0,1,0,1)左农夫羊狼菜合法6(1,1,1,1)右空农夫狼羊菜合法目标7(1,0,1,1)右狼农夫羊菜合法8(1,1,0,1)右羊农夫狼菜合法9(1,1,1,0)右菜农夫狼羊合法10(1,0,1,0)右狼菜农夫羊合法—(1,0,0,1)右狼羊农夫菜不合法狼吃羊—(1,1,0,0)右羊菜农夫狼不合法羊吃菜—(0,1,1,0)左农夫菜狼羊不合法狼吃羊—(0,0,1,1)左农夫狼羊菜不合法羊吃菜—(1,0,0,0)右狼羊菜农夫不合法羊菜同岸—(0,1,1,1)左农夫狼羊菜不合法羊菜同岸从初始状态出发农夫在左岸能带的东西有四种选择自己走、带狼、带羊、带菜。逐个算一下后继自己走得到 (1,0,0,0)不合法带狼得到 (1,1,0,0)不合法带羊得到 (1,0,1,0)合法带菜得到 (1,0,0,1)不合法。四条路只活下来一条。这个结果不是巧合它就是第一步只能带羊的数学解释。把这张转移表想清楚手推答案和写程序就是同一件事的两种表达答辩被问到为什么第一步不能带狼时直接指着这四行后继状态回答比背口诀有说服力得多。3. 搜索策略BFS 与 DFS 的取舍和操作符设计建模完成后剩下的问题是怎么在状态图上走。这道题的状态图只有 10 个节点任何像样的搜索都能出解但能出解和交得出方案是两回事。选 BFS 还是 DFS取决于你要不要保证最短以及演示时能不能解释清楚为什么这么选。3.1 为什么这道题默认选 BFS题目要的是使农夫可以无损失的过河没有明确写最少步数。但几乎所有老师都会追问一句你找到的是最短的吗。BFS 按层扩展第一次碰到目标状态时走过的边数就是最短步数这个性质不需要额外证明。DFS 一路走到底可能先撞上一条绕远的路径虽然也能到终点但要在代码里额外加记录当前最优的逻辑才能回答最短性问题。代价是空间。BFS 要把同一层的所有状态都放在队列里状态图大的时候内存吃紧。这道题一共 10 个节点队列最长不过几个元素空间完全不是问题。真正需要权衡的是那种状态数上百万、只求一条可行路径的场景那时候 DFS 或者启发式搜索才划算。维度BFSDFS数据结构队列先进先出栈后进先出是否保证最短保证边权相同时不保证需要额外的全局最优记录空间开销与状态图宽度成正比与搜索深度成正比本题实际表现7 步两个最优解也能出 7 步但取决于扩展顺序可解释性层数即步数讲起来直观需要解释为什么先走这条分支我通常的做法是主流程用 BFS 出最短解DFS 版本作为对照实验一起提交。这样既回答了最短性又展示了对两种搜索的理解差异课设报告里还能多一节两种策略的对比结果。3.2 操作符设计一次建模两个方向原题把操作符拆成 L(i) 和 R(i) 两组L 表示农夫带东西到右岸R 表示带东西回左岸i0 表示农夫自己i1/2/3 分别对应狼、羊、菜。这样写清楚但实现时会变成两个几乎一样的函数改一处忘一处。更省事的办法是把方向参数化农夫当前在 f 岸下一步必然去 1-f 岸动作只描述带谁走。带的东西必须和农夫在同一岸否则这个动作根本不成立。这样一套逻辑覆盖两个方向代码量减半出错面也减半。def successors(state): 生成所有合法后继。返回 [(新状态, 动作描述), ...] f, w, s, c state items [w, s, c] # 狼、羊、菜的当前位置 nxt 1 - f # 农夫下一步必然去对岸 result [] # i -1 表示农夫独自过河i 0/1/2 对应狼、羊、菜 for i in range(-1, 3): if i -1: new_state (nxt, w, s, c) action 农夫独自 else: if items[i] ! f: continue # 东西不在农夫这一岸带不走 moved list(items) moved[i] nxt new_state (nxt, moved[0], moved[1], moved[2]) action NAMES[i 1] if is_safe(new_state): # 只保留不违反食物链的后继 result.append((new_state, action)) return resultitems[i] ! f这一行是关键过滤它同时处理了两个方向的合法性农夫在左岸时只能带左岸的东西在右岸时只能带右岸的东西。i -1那一支单独处理空手过河这个动作在后面会变成决定成败的一步漏掉它整道题无解——后面避坑章节会专门讲这个翻车点。返回值里带上动作描述是为了后面打印路径时不用反推这一步到底带了谁。搜索算法本身不需要这个字符串但它让输出可读性提升一个量级报告里的步骤表直接由此生成。3.3 BFS 的完整实现与父指针回溯BFS 的骨架很固定队列存待扩展状态visited 集合防止绕圈parent 字典记录我是从哪个状态、通过哪个动作来的。三者缺一不可。visited 只记状态不记路径parent 只记来源不做判重各司其职。from collections import deque def bfs(startSTART, goalGOAL): 返回 (状态路径, 动作序列)无解时返回 (None, None) if start goal: return [start], [] visited {start} # 入队时即标记避免同一状态重复入队 parent {start: (None, None)} # state - (前驱状态, 到达该状态的动作) queue deque([start]) while queue: cur queue.popleft() for nxt, action in successors(cur): if nxt in visited: continue visited.add(nxt) parent[nxt] (cur, action) if nxt goal: return rebuild_path(parent, start, goal) queue.append(nxt) return None, None # 队列空仍未到目标说明无解 def rebuild_path(parent, start, goal): 沿 parent 反向回溯再整体翻转成正序 states, actions [], [] cur goal while cur ! start: prev, action parent[cur] states.append(cur) actions.append(action) cur prev states.append(start) states.reverse() actions.reverse() return states, actionsvisited.add(nxt)放在入队之前而不是出队之后这个顺序决定了 BFS 的效率上限。如果放到出队时才标记同一个状态可能被多个前驱重复入队队列膨胀不说parent 里记下的前驱还可能被后写入的覆盖路径就乱了。这是 BFS 实现里最常见的一处细节写对了不觉得写错了排查半天。rebuild_path里先 append 再 reverse得到的是从初始到目标的正序。动作序列比状态序列少一个元素第 k 个动作连接第 k 个和第 k1 个状态打印时要注意这个偏移。3.4 DFS 版本与它的适用边界DFS 用栈替代队列其余结构一致。递归写法更短但 Python 默认递归深度只有一千层状态图大了会撞上限迭代写法多几行胜在不会栈溢出。def dfs(startSTART, goalGOAL, max_depth50): 迭代版 DFSmax_depth 防止状态图意外成环时无限下探 stack [(start, [start], [])] # (当前状态, 路径状态, 路径动作) visited set() while stack: cur, path_states, path_actions stack.pop() if cur goal: return path_states, path_actions if cur in visited or len(path_states) max_depth: continue visited.add(cur) for nxt, action in successors(cur): if nxt not in visited: stack.append((nxt, path_states [nxt], path_actions [action])) return None, None这里把路径直接塞进栈元素省掉了 parent 字典代价是每个栈元素都持有一份路径副本空间开销随深度线性增长。状态少的时候无所谓状态多的时候还是要换成 parent 回溯。需要提醒的是DFS 里的visited是全局的一旦某状态被访问过就不再扩展这在状态图搜索里是正确的——从同一状态出发能到达的集合是固定的重复扩展没有意义。但如果把它当成树搜索来理解以为同一条路径上不能重复节点、不同路径之间可以重复就会写出漏解的版本。这两种理解在这道题上恰好结果相同换成有环图就会分道扬镳。4. 工程实现从能跑的脚本到能交的程序代码能出结果只是及格线。要交得出手还得考虑结构清晰、输出可读、能被测试、能被扩展。这一章讲怎么把一个几十行的脚本整理成一份完整方案。4.1 模块划分与文件组织单文件也能写完但拆成三块之后答辩时指哪讲哪会顺很多。我一般按数据与规则 / 搜索算法 / 展示与入口来切边界清楚改动互不影响。文件职责主要内容state.py状态表示与规则位序常量、encode/decode、is_safe、successorssearch.py搜索算法bfs、dfs、rebuild_pathmain.py入口与展示参数解析、结果打印、步骤表生成、自测断言这样切的直接好处是换搜索算法不用动规则改规则不用动打印。状态规则里如果加一件物品只需改is_safe和successorssearch.py一行不用碰。4.2 输出排版把七步过程打印成一张能看的表演示环节最忌讳刷屏一堆裸元组。人眼要看的是左岸有什么、右岸有什么、这一步带了谁。写一个渲染函数把状态翻译成两岸清单再配一个步骤表观感立刻不一样。def render(state): 把四元组渲染成两岸清单空岸显示为破折号 f, w, s, c state left .join(NAMES[i] for i, v in enumerate((f, w, s, c)) if v 0) or — right .join(NAMES[i] for i, v in enumerate((f, w, s, c)) if v 1) or — return f左岸: {left:8} 右岸: {right:8} def print_solution(states, actions): 按 步号 / 动作 / 局面 三列输出 print(f{步:4}{动作:12}{局面}) print(- * 60) print(f{0:4}{出发:12}{render(states[0])}) for i, action in enumerate(actions, start1): print(f{i:4}{action:12}{render(states[i])}){:8}是左对齐补空格中文宽度和英文不一致对齐会有偏差这是终端的锅不是代码的锅报告里截图时手动调一下列宽即可不必为此引入第三方表格库。or —处理空岸的情况用空字符串会让这一列看起来像丢数据。跑出来的结果大致是这样步 动作 局面 ------------------------------------------------------------ 0 出发 左岸: 农夫狼羊菜 右岸: — 1 羊 左岸: 狼菜 右岸: 农夫羊 2 农夫独自 左岸: 农夫狼菜 右岸: 羊 3 狼 左岸: 菜 右岸: 农夫狼羊 4 羊 左岸: 农夫羊菜 右岸: 狼 5 菜 左岸: 羊 右岸: 农夫狼菜 6 农夫独自 左岸: 农夫羊 右岸: 狼菜 7 羊 左岸: — 右岸: 农夫狼羊菜七步每一步都能对着上表核验合法性。第 2 步和第 6 步是农夫独自这两步在文字版解法里经常被省略成农夫返回但程序里必须是一个显式动作否则状态对不上。4.3 用断言把结论钉死只靠肉眼看输出是不是对的太脆弱。写几条断言python main.py --test就能自检比反复跑反复看靠谱。def self_check(): # 1. 合法状态恰好 10 个 legal [s for s in ((f, w, s, c) for f in (0, 1) for w in (0, 1) for s in (0, 1) for c in (0, 1)) if is_safe(s)] assert len(legal) 10, f合法状态数应为 10实际 {len(legal)} # 2. BFS 最短步数为 7 states, actions bfs() assert states is not None, BFS 未找到解 assert len(actions) 7, f最短步数应为 7实际 {len(actions)} # 3. 路径上每个状态都合法 assert all(is_safe(s) for s in states), 路径中存在非法状态 # 4. 相邻状态之间只允许变化 农夫 至多一件物品 for a, b in zip(states, states[1:]): diff sum(1 for x, y in zip(a, b) if x ! y) assert diff in (1, 2), f非法转移{a} - {b} assert a[0] ! b[0], 农夫必须换岸 # 5. 起点终点正确 assert states[0] START and states[-1] GOAL print(全部自检通过)第 4 条断言最值钱。它把每一步只能带一样东西这条规则变成了机器可验证的条件两个相邻状态之间变化的位数只能是 1农夫独自走或 2农夫带一件。如果搜索逻辑里漏了东西必须和农夫同岸的过滤这里立刻就会炸。4.4 扩展方向换物品、加容量、改规则课设答辩的加分项往往不是把原题做对而是能说清楚这套结构还能怎么改。三个自然的扩展方向一是把三件物品换成 N 件食物链关系用邻接表描述is_safe改成遍历所有相邻对检查是否有农夫不在且捕食双方同岸的情况。这一步改完程序就能处理狼吃羊、羊吃菜、菜吸收某养分之类的变体。二是把船的容量从 1 改成 2successors里从枚举单件变成枚举组合用itertools.combinations生成所有可带的子集。搜索算法完全不用动因为搜索只关心状态和边不关心边是怎么生成的。三是给每个动作加上代价变成带权图然后换 Dijkstra 或 A*。这时候 BFS 就不够用了但successors、is_safe、rebuild_path这些基础设施依然能复用。这也是为什么前面强调规则和搜索要分开写。5. 避坑排查这五个地方最容易翻车题目看着简单真正动手写的时候翻车点相当集中。下面五条是这类作业里出现频率最高的按现象 → 原因 → 解决的顺序排。5.1 程序跑完说无解但手推明明有解现象BFS 队列空了返回None可纸面上七步就能过河。原因漏掉了农夫独自过河这个动作。successors里只枚举了带狼、带羊、带菜三种农夫移动时必然带东西于是像 (1,0,1,0) 到 (0,0,1,0) 这种空手返回的边根本不存在状态图被切断。解决把i -1那一支补上new_state (nxt, w, s, c)其余三位不变。补完之后再数一遍出边初始状态应有 1 条合法出边中间状态有 2 到 3 条数量对得上才说明动作生成没漏。5.2 状态里没带农夫位置判断条件全乱现象搜索跑得飞快但找到的路径里有一步狼和羊单独待在一起人眼一看就是错的。原因状态只用了 (J, M, N) 三元组描述物品位置农夫的位置靠最后一步动作隐式推断。一旦路径回溯和动作序列错位农夫位置就算错了is_safe检查的是错误的一岸。解决农夫必须进状态四元组一个都不能少。判断安全时先看f的值决定查哪一岸这一步不能省。三元组省下的那点空间换来的是一整套错位 bug。5.3 队列越跑越长最后内存告急现象状态只有 10 个队列却涨到几十上百程序半天不结束。原因visited.add写在了出队之后。同一状态被多个前驱反复入队每个副本出队时又被标记一次队列只增不减parent里记录的前驱还会被后来的覆盖最后回溯出来的路径长度对不上步数。解决把标记动作提到入队之前if nxt in visited: continue紧跟着visited.add(nxt)两行挨着写中间不插别的逻辑。改完之后队列长度的峰值应该和状态图宽度同量级。5.4 打印出来的步骤是倒着的现象输出的第一行是目标状态最后一行才是初始状态或者动作和局面错开一位。原因回溯是从目标往起点走的states里天然是逆序。另外动作序列比状态序列短一个打印时用states[i]配actions[i]会整体错位。解决回溯结束后统一reverse()动作和状态各反转一次。打印时第 0 步只有状态没有动作从第 1 步开始才是动作 到达后的局面用enumerate(actions, start1)对齐。5.5 以为答案唯一被问到第二个解时愣住现象程序只输出一条路径老师问还有别的走法吗答不上来。原因BFS 碰到目标就返回只保留了第一条。实际上这道题有两个最优解区别在于第二次带过去的是狼还是菜。解决把碰到目标就返回改成碰到目标就记录继续扩展直到整层结束或者简单地跑两遍第二遍在successors里调整扩展顺序。更规范的做法是记录所有长度等于最短步数的路径在报告里列成对比表说明两条路径的对称性。这一步能直接体现对搜索终止条件的理解深度。6. 验收与答辩怎么证明这套方案是站得住的验收不是把程序跑一遍给人看而是要让对方在任何一处追问上都能得到确定答案。我一般按结论先行、过程可查、边界可扩三层准备。第一层是结论。开口就说三个数合法状态 10 个、最短步数 7 步、最优解 2 条。这三个数背后各有一条断言撑着self_check跑通就是证据。不要一上来就讲代码先把结论摆出来对方才有兴趣往下问。第二层是过程。准备好一张步骤表和 4.2 节打印出来的格式一致每行都能指着说这一步农夫带了谁、为什么这一步合法。被问到为什么第一步只能带羊时不要背口诀直接展示初始状态的四个后继里三个不合法的那张表让对方自己看出来。第三层是边界。提前想清楚四个问题的答案可能的提问回答要点为什么用 BFS 不用 DFSBFS 首次到达即最短本题状态图小、空间无压力DFS 需额外维护全局最优才能回答最短性如果船能带两样呢只改successors的枚举部分用组合生成待带物品搜索层不动如果物品增加到五件改is_safe为按食物链邻接表遍历状态编码从 4 位扩到 5 位其余复用你怎么保证路径没走错四条断言合法状态数、最短步数、路径合法性、相邻状态差异位数有个细节容易被忽略演示时把终端字号调大或者提前把输出存成文本文件。现场敲命令跑程序一旦环境有问题Python 版本、依赖缺失场面会很难看。多留一手用python main.py out.txt提前存一份出问题时直接打开文件讲。还有一个我自己踩过的坑早期版本我把is_safe写成左岸不能同时有狼和羊测试用例只测了初始状态和目标状态两个都恰好通过直到手推中间步骤才发现农夫在左岸时被误判。从那以后我每次写这类状态判定都强制走一遍农夫在左、农夫在右两个分支各取一个中间状态手算再让断言覆盖到全部 16 种组合——穷举 16 种组合的成本几乎为零能挡掉的错误却不少。这套结构跑通之后狼羊白菜只是一个入口真正留下来的是状态怎么定义、动作怎么生成、搜索怎么终止、结果怎么验证这条链路。把代码和那张步骤表一起整理进报告附上自检输出基本就没什么可挑的了。希望帮到你。本文还有配套的精品资源点击获取