简介围绕人工智能经典状态空间搜索问题展开的「狼、羊、白菜与农夫过河」学习文档面向计算机科学初学者、算法课程学习者及需要理解搜索与约束建模的读者。内容从题目描述与食物链约束入手梳理先带羊或先带菜两类过河策略并用四元组表示农夫、狼、羊、菜的位置给出初始状态、目标状态及L/R操作符定义便于理解状态转移、回溯与可行解验证。资源包共1个doc文件约371KB适合作为课堂例题、算法练习或复习笔记使用。已有3852人学习文档中整理了约束状态列表、分步推理和状态空间图构建思路可帮助读者把DFS、BFS、动态规划等搜索方法落到具体问题上也能为图论与有限状态机练习提供可对照的案例。1. 农夫过河到底在考什么一句话拆开这道经典题“农夫带狼、羊、白菜过河”是一道流传很广的经典题。农夫有一条小船每次只能带一样东西人不在场时狼会吃羊、羊会吃菜怎么让三者都安全到对岸很多人第一次听到会觉得像脑筋急转弯试了两步就卡住带羊过去回来带狼狼又和羊凑到一起。其实它考的不是急智而是一个计算机科学里极常见的思路——把局面写成“状态”用“约束”筛掉危险局面再靠“搜索”一步步试出一种走法。搞懂这道题你会更容易看懂人工智能里路径规划、任务调度、自动推理这些名词在说什么而不是把它们当成玄学。它真正有价值的地方是给了一个小到可以手推、又完整到能装下搜索算法全部要素的模型。2. 为什么第一步只能带羊约束条件才是题眼很多人拿到这道题第一反应是“先带谁过去”。这个问法本身就偏了。真正决定第一步的不是带什么过去方便而是带完之后留在原岸的组合会不会出事。换句话说约束条件才是题眼。2.1 食物链构成的“危险组合”题目给出的关系很明确狼吃羊羊吃菜狼不吃菜。这三句话翻译成组合就是两组危险搭配和一组安全搭配。同在无人看管的一岸后果狼 羊羊被吃羊 白菜白菜被吃狼 白菜相安无事注意表头里的限定词——“无人看管的一岸”。农夫在场的时候狼和羊关在一个笼子边上也没事因为有人拦着。所以判断危险永远要同时看两件事哪两样东西在一起以及农夫在不在那一岸。只看组合不看农夫位置是后面一系列误区的源头。这条规则还有一个容易忽略的对称性农夫在左岸要检查的是右岸农夫在右岸要检查的是左岸。检查的对象永远是“农夫不在的那一岸”不是“东西多的那一岸”也不是“刚放东西的那一岸”。2.2 每一次往返都在解除一个定时炸弹把第一步的所有可能摊开看只有四种动作农夫空手走、带狼走、带羊走、带白菜走。逐个检查留在左岸的组合。农夫空手走左岸剩狼、羊、白菜狼吃羊、羊吃菜同时踩两个雷不行。带狼走左岸剩羊和白菜羊吃白菜不行。带白菜走左岸剩狼和羊狼吃羊不行。带羊走左岸剩狼和白菜这两个搭配安全行。所以第一步不是“优选带羊”而是“只能带羊”。这一步没有第二个合法选项任何号称先带狼或先带菜的说法都漏掉了留在原岸的那一组。羊到了右岸农夫要回去继续运东西。这时如果农夫把羊再带回去等于原地转圈所以只能空手回。空手回的那一刻右岸只有羊没有农夫但羊单独待着不会出事左岸有狼、白菜和农夫狼和白菜也不冲突。这个局面是安全的第二步就成立了。接下来运狼还是运白菜才是真正出现分岔的地方。假设第三步带狼到右岸右岸变成狼、羊、农夫同在。农夫只要一离开右岸狼和羊就会独处所以农夫回左岸时必须把羊捎回去。于是第四步是“带羊回左岸”右岸剩狼左岸有羊、白菜和农夫。这时左岸的羊和白菜都在农夫眼皮底下安全。第五步农夫带白菜到右岸右岸变成狼、白菜、农夫。第六步农夫空手回左岸右岸的狼和白菜安全左岸只剩羊。第七步带羊到右岸全部到位。把这条路径写成动作序列带羊到右岸 → 空手回左岸 → 带狼到右岸 → 带羊回左岸 → 带白菜到右岸 → 空手回左岸 → 带羊到右岸一共七次单程移动。如果第三步换成带白菜后面就是“带羊回、带狼去、空手回、带羊去”同样七步只是狼和白菜的出场顺序对调。两条路径结构完全对称差别只在先运哪一个。这里有个细节值得停一下第六步为什么可以空手回因为那时左岸只剩羊右岸是狼加白菜两边都没有触发危险组合。空手回不是偷懒而是当前局面下唯一不会制造新危险的走法。整道题的节奏就是这样——每一步都在解除一个即将引爆的定时炸弹同时避免制造下一个。2.3 四元组状态表示把局面写成机器能读的格式手工推演靠的是眼睛和直觉要让机器接手得先把“局面”翻译成符号。题目给出的办法是四元组S (L, J, M, N)四个位置分别代表农夫、狼、羊、白菜0 表示在左岸1 表示在右岸。初始状态是(0, 0, 0, 0)目标状态是(1, 1, 1, 1)。每移动一次就有一个或两个分量的值翻转。操作符也做了编号L(i)表示农夫带东西去右岸R(i)表示农夫带东西回左岸i0是农夫自己i1是狼i2是羊i3是白菜。这个编号看起来琐碎实际很有用——它把“带谁”变成了一个可以循环遍历的整数代码里一个for循环就能枚举所有动作。题目还列了一串“约束状态”比如(0,1,1,0)、(0,0,1,1)、(1,0,0,0)。拿(0,1,1,0)来说农夫在左岸狼和羊在右岸农夫不在右岸而狼羊同在右岸羊会被吃。再看(1,0,0,0)农夫在右岸狼、羊、白菜全在左岸左岸无人看管且三样俱全两个危险组合同时成立。这些四元组的共同点是它们都活不过一次安全检查。注意原材料把这些组合叫“约束状态”但从上下文看它们其实是“被约束排除掉的状态”。这个叫法上的模糊是初学者最容易栽跟头的地方后面会单独展开。2.4 为什么“先带菜”这个写法经不起推敲有些手写笔记在列举分支时会写“选择二先带白菜到右岸”。单看这一句没问题但把它放回约束里检查就露馅了白菜被带走的瞬间左岸剩下狼和羊农夫在右岸狼立刻吃羊。这一步在物理上做得到在规则上不合法。这个写法之所以流传多半是因为记录的人只盯着“到了右岸的东西”忘了回头看“留在左岸的东西”。过河题的每一步都要同时检查两岸只检查目的岸等于只做了一半的安检。把这一点理清之后两条对称路径就好理解了它们不是“第一步不同”而是“第一步之后先运谁不同”。第一步永远是羊这一点没有商量余地。3. 状态空间搜索人脑推理和机器试错的同一件事手工推演到第七步靠的是对局面的持续跟踪。机器没有眼睛它靠的是一张表和一个循环把所有合法状态列出来把状态之间的合法跳转连成边然后从起点开始一条条试。人脑和机器做的其实是同一件事只是机器不会累、不会漏。3.1 状态转移图长什么样四个物体各有两种位置理论上最多十六种组合。用“农夫不在的那一岸不能同时出现狼羊或羊菜”这把筛子过一遍只剩十个合法状态。状态 (L,J,M,N)含义(0,0,0,0)全部在左岸起点(0,0,0,1)农夫、狼、羊在左白菜在右(0,0,1,0)农夫、狼、白菜在左羊在右(0,1,0,0)农夫、羊、白菜在左狼在右(0,1,0,1)农夫、羊在左狼和白菜在右(1,1,1,1)全部在右岸终点(1,1,1,0)农夫、狼、羊在右白菜在左(1,1,0,1)农夫、狼、白菜在右羊在左(1,0,1,1)农夫、羊、白菜在右狼在左(1,0,1,0)农夫、白菜在右狼和羊在左这十个状态就是整张图的全部节点。边是操作农夫从自己所在的岸出发带一样东西或者空手到对岸去落点必须还在这十个状态里。以起点(0,0,0,0)为例空手走、带狼走、带白菜走都会落到表外的非法组合只有带羊走能落到(1,0,1,0)。所以起点只有一条出边这也是“第一步唯一”在图上的直观体现。从(1,0,1,0)出发农夫在右岸可以空手回左岸落到(0,0,1,0)也可以带羊回左岸落回起点。前者是前进后者是倒退。搜索算法要做的事情就是在不重复踩点的前提下从起点一路走到(1,1,1,1)。这张图还有一个很实用的性质它是对称的。把每个四元组里的 0 和 1 全部翻转得到的还是一个合法状态而且起点和目标正好互换。这意味着从终点倒着搜和从起点正着搜工作量差不多。3.2 DFS 和 BFS 在这道题上的不同走法深度优先搜索DFS的思路是“一条道走到黑”。用一个栈存待探索的状态每次取最新压入的那个能往前就往前走不动了再退回来换一条。放到过河题上它可能先沿着“带羊、空手回、带狼、带羊回、带白菜”这条链一路走到底发现到终点了就停。如果中途走进死胡同就弹出栈顶回到上一个分岔点。DFS 的优点是省内存只存当前路径上的节点。缺点是它找到的路径不一定最短。如果动作顺序换一换它可能先走一条绕远的路线照样能到终点但步数更多。在过河题这种小图上绕远也绕不了几步问题不大换成大一点的图DFS 可能一头扎进很深的角落半天回不来。广度优先搜索BFS的思路是“一圈一圈往外扩”。用一个队列存待探索的状态先看离起点一步能到哪些状态再看两步能到哪些依此类推。第一次碰到目标状态时走过的步数一定是最少的。过河题的最短解是七步BFS 第一次抵达(1,1,1,1)时路径长度必然是七。BFS 的代价是内存。它要把每一层的状态都存下来状态一多队列就会胀得很快。在这道题里十个状态塞不满一个队列随便怎么跑都行。两种搜索还有个共同的前提必须记录“已经访问过的状态”。不记录的话农夫带羊过去、再带羊回来状态回到原点搜索就会在这两个状态之间来回打转永远走不到新地方。这个去重动作行话叫“剪枝”或者“避免重复扩展”是搜索算法里最便宜也最有效的一招。3.3 用一段代码把搜索跑起来把上面的规则翻译成代码核心只有三块判断一个状态安不安全、生成从当前状态出发的所有合法下一步、按队列顺序往外扩展。from collections import deque # 状态 (L, J, M, N)0 表示在左岸1 表示在右岸 # L 农夫J 狼M 羊N 白菜 START (0, 0, 0, 0) GOAL (1, 1, 1, 1) def is_safe(state): L, J, M, N state far 1 - L # 农夫不在的那一岸 if J far and M far: return False # 狼和羊独处羊被吃 if M far and N far: return False # 羊和白菜独处白菜被吃 return True def next_states(state): L, J, M, N state result [] # item0 农夫自己1 狼2 羊3 白菜 for item in range(4): pos [L, J, M, N] if item ! 0 and pos[item] ! L: continue # 东西不在农夫身边带不走 nxt pos[:] nxt[0] 1 - L # 农夫换到对岸 if item ! 0: nxt[item] 1 - L nxt tuple(nxt) if is_safe(nxt): result.append((nxt, item)) return result def bfs(): queue deque([(START, [START])]) seen {START} # 记录已访问状态防止来回打转 while queue: state, path queue.popleft() if state GOAL: return path for nxt, item in next_states(state): if nxt not in seen: seen.add(nxt) queue.append((nxt, path [nxt])) return None path bfs() for step, state in enumerate(path): print(step, state)is_safe只查农夫不在的那一岸这是整段代码里最容易被写错的地方。next_states里的item0对应农夫空手过河这个分支不能省因为第六步就是空手回。seen集合负责去重没有它搜索会在“带羊过去、带羊回来”之间死循环。如果想把问题改复杂一点比如加一只额外的动物只需要改状态元组的长度和is_safe里的判断规则搜索骨架一行都不用动。这也是这类写法值得学的原因规则和流程是分开的换题不换框架。参数上唯一值得留意的是动作顺序。for item in range(4)先试空手、再试狼、再试羊、再试白菜BFS 找到的会是“先运狼”那条路径。把顺序调成先试白菜找到的就是另一条对称解。路径不同步数一样。4. 常见误区与易混概念五组最容易混的说法初学者在这道题上翻车很少是因为算不明白多数是因为某个概念的第一印象偏了后面越推越拧。下面五组说法是手推和写代码时最容易混的。4.1 误区一只要农夫在场怎么放都安全易混点把“危险”理解成“两样东西不能待在一起”忽略了农夫位置这个前提。为什么混日常生活里狼和羊放一块就是危险这个印象太强容易把“无人看管”这个条件自动省略掉。一省略就会觉得“狼和羊都在左岸农夫也在左岸这有什么问题”。怎么区分危险组合只在农夫离开那一岸时成立。农夫在左岸要检查的是右岸农夫在右岸要检查的是左岸。同一条“狼羊”农夫在左岸时它发生在右岸才危险发生在左岸反而不危险。判断安全永远问一句农夫不在的那一岸有没有狼羊或者羊菜。4.2 误区二约束状态就是合法状态易混点原材料列了一串四元组叫“约束状态”有人读成“满足约束的状态”以为这些是允许出现的局面。为什么混“约束”这个词太中性。它既可能指“被约束保护的状态”也可能指“被约束排除的状态”单看字面分不出来。怎么区分看上下文。那串四元组后面跟着的解释是“狼、羊在左岸”“羊、菜在左岸”全是会出事的组合。它们真正的作用是当反面清单用搜索时碰到这些状态直接扔掉。叫“非法状态”或“危险状态”更不容易误会。四元组农夫位置无人看管岸上的组合判定(0,1,1,0)左岸右岸有狼和羊非法(0,0,1,1)左岸右岸有羊和白菜非法(1,0,0,1)右岸左岸有狼和羊非法(1,1,0,0)右岸左岸有羊和白菜非法(1,0,0,0)右岸左岸三样俱全非法(0,1,1,1)左岸右岸三样俱全非法把这六行当成黑名单记住比背“约束状态”这个模糊叫法管用得多。4.3 误区三先带羊和先带菜是两条对称的起点易混点看到两条路径都能到终点就以为第一步也有两个选择一个先带羊一个先带菜。为什么混只盯着“到达右岸的东西”忘了看“留在左岸的东西”。带白菜过去这个动作本身很顺船上有位置白菜也搬得动看起来完全可行。怎么区分第一步带什么取决于左岸剩下什么。带狼走左岸羊加白菜带白菜走左岸狼加羊两种都触发危险组合。只有带羊走左岸狼加白菜才安全。所谓的两条路径是“带羊之后先运狼”和“带羊之后先运白菜”分岔点在第三步不在第一步。把分岔点前移一格整个推理就顺了。4.4 误区四这题和迷宫最短路完全一样易混点都叫“搜索”都在一张图上找一条从起点到终点的路径看起来是同一类问题。为什么混形式上确实像。迷宫有格子、有墙、有起点终点过河题有状态、有操作、有初始和目标。两者都能用 BFS 跑代码骨架几乎一样。怎么区分迷宫里的“墙”是事先画好的格子之间的连通关系固定不变过河题的“墙”是算出来的每一步都要拿当前局面去过一遍安全规则。迷宫搜的是空间位置过河题搜的是局面组合。更关键的是过河题里存在“物理上走得到、规则上不允许”的动作比如带白菜第一步这种动作在迷宫模型里没有对应物。写代码时迷宫只需要判断“下一格是不是墙”过河题需要判断“下一个状态是不是非法”后者是动态的、依赖上下文的。4.5 误区五答案只有一个搜索没意义易混点手推七步就能推出来写程序显得多此一举。为什么混这道题的规模太小人脑够用程序的优势显不出来。加上网上流传的答案通常只给一条路径更容易让人觉得“标准答案唯一”。怎么区分这道题至少有两条对称解先运狼和先运白菜各一条步数都是七。程序能一次把两条都找出来人手推很容易推完一条就收工。更重要的是这套写法的价值不在这一道题而在它换个规模还能用。把狼、羊、白菜换成三台设备、两个互斥条件、五个待办任务人手推几天搜索几秒钟。学的是把局面写成状态、把规则写成函数、把试错交给循环不是背一条七步路径。5. 从玩具题到真实系统状态空间方法还能用在哪儿过河题的状态只有十个小到可以画在纸上。但它的结构——状态、动作、约束、目标——和很多真实系统是同构的。区别只在规模和规则复杂度。5.1 什么场景适合用状态搜索建模判断一个场景适不适合套这套方法可以看四个条件。局面能不能离散成有限个状态动作是不是有限且可枚举有没有明确的安全规则或合法性规则目标能不能用一组条件判定。四条都满足状态搜索就能上场。常见的例子拼图还原每个排列是一个状态移动一块是一步八皇后每行放一个皇后是一个状态检查列和对角线是约束任务调度每个任务的完成情况是一个状态依赖关系是约束物流装箱每件货物的位置是一个状态承重和体积是约束棋类走子棋盘局面是状态走法规则是动作。拿调度来说假设有一组设备需要按顺序启停某些设备不能同时运行某些设备必须在另一台之后启动。把每台设备的开/关写成 0/1整个局面就是一个二进制串把“不能同时运行”写成类似is_safe的检查函数把“启动一台”或“停止一台”写成动作。剩下的就是让 BFS 从初始串走到目标串。过河题里的狼羊白菜在这里变成了设备之间的互斥关系结构一模一样。5.2 什么情况下这套方法会“算不动”状态搜索的软肋是规模。每一步有 b 种选择走 d 步搜索树的节点数大致是 b 的 d 次方。过河题里 b 最多是 4d 是 7组合数小得可以忽略。换成真实系统这两个数字都会往上蹿。按二进制状态估算10 个物体各有两种位置一共 1024 种组合20 个物体是一百多万种30 个物体是十亿种40 个物体就到了一万亿。这还只是“每个物体只有两种状态”的乐观估计如果每个物体有三种以上状态数字涨得更快。BFS 要把这些状态塞进队列内存在中途就会告急。还有一种更隐蔽的“算不动”状态表示选得不好把本质相同的局面记成了不同状态。比如两个可互换的物体交换位置后其实还是同一个局面如果状态元组把它们当成两个不同分量搜索就会在等价状态之间反复横跳白白烧掉算力。这类问题不报错只是慢排查起来很费劲。5.3 状态压缩与剪枝让搜索不爆炸的小技巧第一招是状态压缩。把四元组压成一个整数用位运算存取比存元组省内存哈希也更快。# 把 (L, J, M, N) 压成一个 4 位整数 def encode(state): L, J, M, N state return (L 3) | (J 2) | (M 1) | N # 从整数还原回四元组 def decode(code): return ((code 3) 1, (code 2) 1, (code 1) 1, code 1)encode把四个 0/1 分量按位拼起来decode再拆回去。四个物体只占四位换成三十个物体也只占三十位一个整数就能装下整个状态。这一步在状态多的时候收益很明显。第二招是去重。每扩展一个新状态先查它有没有被访问过访问过就跳过。过河题里这招省不了多少但在大图上它能砍掉大量回头路。第三招是利用对称性。过河题里狼和白菜在规则上并不对称不能随便互换但很多真实系统里存在完全等价的物体把它们归成一类状态数会成倍下降。第四招是双向搜索。从起点和终点同时往外扩两边在中间碰头。过河题的正反两张图结构对称双向搜索能把扩展量压到原来的一半左右。第五招是启发式搜索。给每个状态估一个“离目标还有多远”的分数优先扩展分数低的。A* 算法就是这一类只要估价函数不夸大真实距离找到的仍然是最短路径。过河题里可以拿“还没过河的东西数量”当估价效果一般但能说明思路。提示这几招不是越多越好。小规模问题上加太多优化代码会变得难读收益却看不出来。先把朴素的 BFS 跑通确认结果对再按需要往上加。6. 什么时候用、什么时候别用这套思路的边界状态搜索不是万能锤。它适合的局面有明确特征不适合的局面也有明确信号。把边界划清楚比多背几个算法名有用。场景特征适合用状态搜索不适合硬套状态形态离散、有限、可枚举连续变量、无限取值规模组合数在可控范围内维度高、组合爆炸规则明确、可写成函数模糊、依赖外部判断目标可用条件判定目标本身需要协商路径要求需要一条可解释的操作序列只关心最终结果、不关心过程举一个具体例子。某自动化脚本要安排一组设备的启停顺序设备之间有互斥关系A 运行时 B 不能运行C 启动前必须等 D 停止。把每台设备的开/关写成 0/1整个局面是一个二进制串把互斥和依赖写成检查函数把“切换某台设备”写成动作。这套结构和过河题几乎一样BFS 能找出一组最短的切换序列而且每一步都解释得清为什么这么切。但如果设备数量到了几十台状态数会指数上涨队列撑不住这时候就该换约束求解器或者启发式规划而不是硬把 BFS 往上堆。判断标准很简单先数一遍状态规模估算一下内存和耗时再决定要不要上搜索。数不出来就先拿小规模跑一遍看状态增长曲线。还有一种情况要避开规则本身说不清。过河题的规则只有两条白纸黑字。真实系统里经常出现“一般情况下不能这样但特殊情况可以”的条款这种模糊规则写不进is_safe硬写进去只会得到一堆看似合法、实际没法执行的路径。规则没理清之前先别急着写搜索。从那以后我每次遇到“看起来像过河题”的需求都先做三件事把局面写成状态元组把危险组合列成黑名单估算一下状态总数。三步走完能不能用搜索、该用哪种搜索基本就有答案了。希望帮到你。本文还有配套的精品资源点击获取