状态空间搜索入门：从过河谜题掌握状态编码与BFS/DFS

简介面向人工智能初学者与算法练习者的经典「狼、羊、白菜与农夫过河」逻辑推理资料围绕有限状态机与状态空间搜索梳理完整求解思路。压缩包共 1 个 doc 文件约 371KB篇幅紧凑便于打印或随堂讲解。内容从题目描述和食物链约束入手说明首趟为何只能带羊、返程为何须空手并列举“先带羊”与“先带菜”两条可行策略及逐步状态变化随后抽象出四元组 S(L,J,M,N) 表示农夫、狼、羊、菜的位置定义 L(i)、R(i) 两类操作符给出初始状态 (0,0,0,0)、目标状态 (1,1,1,1) 与四组非法约束把过河过程转化为可搜索的状态转移图对应 DFS、BFS 或动态规划实现。已有 3852 人学习。读者可据此掌握状态表示、约束校验与搜索回溯的推演方法并作为自己写程序验证时的对照答案。1. 状态空间搜索为什么四个比特位就能装下整道过河题大多数人第一次看到农夫、狼、羊、白菜过河这道题第一反应是拿草稿纸推演试错几次也能凑出答案。但真正有意思的地方不在答案本身——把农夫和三样东西的位置拆成四个二进制位之后整个谜题就塌缩成一张只有 16 个节点的有限状态机其中 10 个节点合法6 个一踩就炸。问题从“想出一个方案”变成了“在图上找一条从起点到终点的路径”。这也是状态空间搜索最干净的样本没有花哨数据结构没有复杂分支只有“编码状态、翻译约束、搜索路径”这三步。搞懂了这个过程再回头看 BFS、DFS、visited 集合这些东西就不会觉得它们是凭空冒出来的名词了。2. 状态编码四元组如何把一句“狼吃羊”翻译成可计算的约束这道题最核心的一步不是写搜索而是把“狼会吃羊”这句自然语言翻译成计算机能判定的布尔表达式。翻译错了搜索再快也是错的。常见的实现思路是用一个四元组表示当前局面再用一个安全判定函数把规则压成比特运算。2.1 从自然语言到四元组状态定义的第一道关用 S L, J, M, N表示状态其中 L 是农夫、J 是狼、M 是羊、N 是白菜每个分量的取值约定为 0 表示在左岸、1 表示在右岸。初始状态 S (0, 0, 0, 0)目标状态 G (1, 1, 1, 1)。这个编码看起来很朴素但它做了两件关键的事。第一件是把“位置”这个模糊概念压成了单比特。你不需要知道狼具体站在岸边的哪个位置、离羊有多远只需要知道它在左岸还是右岸。多余的信息全部被砍掉留下的正好是判定约束所需的最小信息量。这正是状态编码的核心原则编码的维度必须刚好够用多一个比特都是浪费少一个比特就判不了安全。第二件是把对称的两岸统一成同一个比特维度。无论左岸还是右岸都用 0/1 区分搜索过程中不需要为“农夫在左岸”和“农夫在右岸”写两套逻辑。这种对称性在状态空间里保持得很好任何一个状态取反0 变 1、1 变 0仍然是合法状态——因为过河问题左右对称从左到右和从右到左是对称的操作。整个状态空间大小是 2^4 16。这个数字后面会反复用到搜索最多只会访问 16 个节点没有任何算法层面的复杂度压力所有性能问题都出在实现细节上。2.2 安全状态判定谁吃谁怎么写成布尔不等式题目给的食物链是“菜 → 羊 → 狼”意思是羊会吃菜、狼会吃羊。注意方向不是狼吃菜也不是菜吃羊。约束的本质是当农夫不在场时不能把存在捕食关系的两者单独留在同一岸。形式化之后是两条规则如果狼和羊在同一岸而农夫不在那一岸状态非法。如果羊和白菜在同一岸而农夫不在那一岸状态非法。写成布尔表达式就是非法 ⟺ (J M ∧ L ! J) ∨ (M N ∧ L ! M)等价的合法判定是安全 ⟺ (J ! M ∨ L J) ∧ (M ! N ∨ L M)这里有个容易翻车的细节条件里“L ! J”而不是“L ! M”因为判断的是农夫是否和那一对在一起农夫在左岸还是右岸并不重要重要的是他是否与狼、羊中的任意一个同岸。如果狼和羊都在左岸JM0而农夫在右岸L1那么 L ! J 成立状态非法。如果三者都在左岸LJM0那么 L J 成立说明农夫在看着它们状态合法。用 Python 写出来大概是这样def is_safe(state): L, J, M, N state # 狼吃羊两者同岸且农夫不在那一岸 if J M and L ! J: return False # 羊吃菜两者同岸且农夫不在那一岸 if M N and L ! M: return False return True这三行代码就是整道题最核心的规则映射。参数说明一下L、J、M、N 分别对应四元组中农夫、狼、羊、白菜的位置取值只能是 0 或 1。两个 if 的顺序无所谓但都必须用“同岸且农夫不在”这个合取条件不能简化为“同岸就非法”。有个常见的误区是写成“如果 J M 就返回 False”。这会导致初始状态 (0,0,0,0) 直接被判非法——但初始状态明明是合法的因为农夫也在左岸看着它们。少了 L ! J 这个条件规则就从“无人看管时不能同岸”退化成了“任何时候不能同岸”语义完全错了。这类错误在实现里代价很高因为搜索会从起点就直接失败表现出来的现象是“怎么都找不到解”而不是“找到错的解”排查时容易被误导。2.3 操作符与前驱后继船移动的抽象表示约束翻译好之后接下来要定义“船怎么走”。题目规定农夫每次只能带一样东西过河但也可以空手过河。用操作符 L(i) 表示农夫带东西到右岸R(i) 表示农夫带东西回左岸i 的取值为i 的取值含义0农夫自己过河不带东西1农夫带狼过河2农夫带羊过河3农夫带白菜过河注意 i0 这个操作的存在感很强——两个经典解法里都出现了“农夫空手返回”的步骤少了这个操作船就永远回不来。i1/2/3 的含义是“带某个东西”但前提是那个东西必须和农夫在出发的同一岸上否则这个操作不合法。生成后继状态时需要做三件事确认农夫和要带的东西在同一岸如果是带东西翻转农夫的位置如果需要带东西同时翻转那个东西的位置最后用 is_safe 校验新状态。用代码写def successors(state): L, J, M, N state positions [L, J, M, N] result [] for i in range(4): # 带东西时那东西必须和农夫在同一岸 if i 0 and positions[i] ! L: continue new_state list(state) new_state[0] 1 - L # 农夫过河 if i 0: new_state[i] 1 - new_state[i] # 东西跟着过河 new_state tuple(new_state) if is_safe(new_state): result.append((i, new_state)) return result这段代码里最需要说清楚的是 i0 和 i0 的分支处理。当 i0 时农夫自己走只翻转 new_state[0]当 i0 时先确认 positions[i] L再同时翻转农夫和物品。返回的元组里带着操作编号 i是为后面回溯路径时能打印出“第几步带了什么”用的。还有一个隐含的设计决策这里每次只生成“从农夫当前所在岸出发”的操作。也就是说如果农夫在右岸生成的是 R(i)从右往左走而不是 L(i)。但代码里没有显式区分 L 和 R因为位置翻转 1-L 已经天然包含了方向——L0 时翻转成 1 就是往右L1 时翻转成 0 就是往左。这种对称处理省掉了两个方向的重复逻辑是编码层面顺手拿到的便利。到这里状态、约束、操作符三样东西都齐了。下一步就是在这张 16 节点的图上跑搜索。BFS 和 DFS 都能跑但走法不同、代价不同下一章拆开看。3. 搜索策略BFS 和 DFS 在同一张状态图上走出的两条路径状态空间只有 16 个节点任何搜索算法都能在瞬间跑完。所以这里讨论的“性能”不是指跑得快不快而是指搜索策略本身的行为差异——BFS 天然给出最短解DFS 靠回溯和栈两者在去重、路径记录、解的质量上都有不同的表现。理解这些差异比背下某一种实现更有价值。3.1 广度优先搜索为什么 BFS 能保证最短解BFS 的核心机制是层序遍历从起点出发先访问距离为 1 的所有状态再访问距离为 2 的所有状态以此类推。因为每条边的代价都是 1每过一次河算一步所以第一次到达目标状态时的路径长度必然是最短的——不可能存在一条更短的路径还没被访问到因为更短的层早就遍历完了。实现上用队列来维持这个顺序from collections import deque def solve_bfs(): start (0, 0, 0, 0) goal (1, 1, 1, 1) if start goal: return [] queue deque([(start, [])]) # (状态, 路径) visited {start} while queue: state, path queue.popleft() for move, next_state in successors(state): if next_state in visited: continue # 去重访问过的不再入队 new_path path [(move, next_state)] if next_state goal: return new_path # 第一次到达即为最短 visited.add(next_state) queue.append((next_state, new_path)) return None这段代码里有两个关键点值得展开。第一是visited的加入时机。在 BFS 里状态入队的那一刻就应该标记为已访问而不是等出队再标记。原因很直接如果出队时才标记同一个状态可能被多个父节点重复入队队列膨胀不说还可能导致同一个节点被展开多次。虽然这道题状态少影响不明显但在状态空间大一点的图里这个差别可能就是跑一秒和跑十秒的区别。第二是路径的携带方式。这里用了一个简单粗暴的做法——把路径整个塞进队列的元组里。每扩展一步就复制一份列表状态少的时候没问题状态一多就会产生大量内存拷贝。更稳妥的做法是用 parent 字典记录每个状态的前驱最后从目标状态反向回溯。下一章会讨论这个差异为什么在实现里容易翻车。BFS 在这道题上跑出来的解遵循一个固定模式先把羊带过去农夫空手回来再带狼或白菜过去把羊带回来再带剩下那个过去农夫空手回来最后带羊过去。总共七步。这个解是搜索自己碰出来的不是人工硬编码的——换一组约束比如加一只猫或者换一条食物链代码不需要改结构只需要改编码和 is_safe 函数。3.2 深度优先搜索递归回溯与路径追踪DFS 走的是另一条路沿着一条路径一直往下走走不通就回退到上一个岔路口换一条路。实现上可以用递归也可以用显式栈。递归版本的代码看起来更短def solve_dfs(state, path, visited): if state (1, 1, 1, 1): return path visited.add(state) for move, next_state in successors(state): if next_state in visited: continue result solve_dfs(next_state, path [(move, next_state)], visited) if result is not None: return result return NoneDFS 和 BFS 最大的行为差异在于DFS 找到的解不保证最短。因为 DFS 只会沿着一条分支闷头走到黑它可能在绕着远路兜了一圈之后才碰到目标状态而 BFS 会在所有短路径都试完之后才走长路。在这道题里DFS 一旦先选到“带羊过河”这个分支后面的搜索会顺着羊的移动一直往下推最终找到的解在步数上可能和 BFS 一致也可能不一致——取决于 successors 返回操作的顺序。更隐蔽的问题是 visited 集合在递归里的语义。递归版本里 visited 是全局共享的——进入一个节点时标记但回退时不会取消标记。这带来的后果是一条路径上访问过的状态在另一条路径上不会再被访问。对于“找一条解”这个目标来说没问题但如果要找“所有解”这种写法会漏掉一些路径——因为不同路径可能经过同一个中间状态而先走的路径把状态标记了后走的路径就被挡住了。要枚举所有解visited 要么改成“只在当前路径上标记、回退时取消”要么干脆不用 visited在 16 个节点的图上也无所谓靠路径长度或者步数上限来防止无限循环。这个选择在实现里没有标准答案取决于目标是“找一条”还是“找全部”。3.3 状态去重与访问控制为什么没有 visited 集合会翻车如果没有 visited 集合BFS 和 DFS 都会陷入死循环因为状态图里存在环。举个例子初始状态 (0,0,0,0)带羊到右岸得到 (1,0,1,0)农夫空手回来得到 (0,0,1,0)再把羊带回来又回到 (0,0,0,0)。操作合法、状态安全但形成了一个环。没有去重机制的话搜索会在这个环里来回打转永远出不来。这道题的图很小环也很短手推的时候很容易发现但写代码的时候如果忘了 visited表现就是程序卡死——没有任何输出CPU 拉满。排查这类问题的第一步永远是看搜索循环里有没有标记已访问状态。去重的粒度也值得说一下。有几种常见的做法用 set 存状态元组。简单直接哈希开销可以忽略。这道题用这种就够了。用位掩码存状态。每个状态可以用一个 4 位整数表示set 换成布尔数组。状态少的时候有点杀鸡用牛刀但如果是几十维的状态空间位掩码的优势就出来了。用字典存 parent 指针。既能去重又能回溯路径一举两得。状态多的时候比“路径整个塞队列”更省内存。在实现里选哪种看状态空间大小和路径记录需求。这道题的状态空间只有 16怎么选都行但如果目标是练习搜索的通用模板用 parent 字典的写法更值得记住——换成大图的时候不用改结构只改数据类型就够。4. 避坑与排查搜索实现里最常见的五个翻车现场写搜索算法的代码量不大但错一个条件就可能让结果全错或者直接卡死。下面这几条是手写状态空间搜索时踩过的坑按“现象 → 原因 → 解决”拆开记。4.1 坑一约束判定的方向性错误现象程序跑完返回空列表表示无解。但手动推演明明有解。原因is_safe 里只写了“狼和羊同岸”或者“羊和菜同岸”就判定非法漏了“农夫不在那一岸”这个合取条件。初始状态 (0,0,0,0) 里狼、羊、菜都在左岸如果只判同岸就非法搜索从起点直接失败后面自然什么都找不到。解决约束必须写成“两者同岸 AND 农夫不在那一岸”两个条件缺一不可。写完 is_safe 之后先拿初始状态和目标状态各跑一遍确认初始状态合法、目标状态合法、中间某个“羊单独在右岸”的状态也合法三个测试点过了再往下写搜索。4.2 坑二船移动计数的误解现象步数不对——要么比标准解少一步要么多一步要么中间某个状态看起来合法但算子打印出来是“农夫自己过河”而实际上想打印“带羊过河”。原因混淆了 i 的取值和船的实际载物。i0 表示农夫空手走i1/2/3 分别对应狼/羊/菜。如果生成后继时把 i 直接当成“第 i 个物品”就会出现 i0 走到狼、i1 走到羊这种错位。解决在 successors 里用 positions [L, J, M, N] 建一个显式的索引数组i 遍历 0 到 3i0 单独处理i0 时用 positions[i] 取物品位置。这样索引和物品一一对应不会错位。4.3 坑三路径回溯的指针断裂现象搜索找到了目标状态但回溯出来的路径只有最后一步或者路径里出现了不相邻的两个状态。原因用 parent 字典记录前驱时只记了“当前状态从哪个状态来”但回溯时从目标状态往前跳的时候parent 里某个中间状态没有记录——通常是因为该状态是通过“入队时没标记”的路径到达的parent 被后一次访问覆盖了。解决parent 字典的写入时机和 visited 一致——入队时立刻写 parent[next_state] (current_state, move)不要等出队再写。另外回溯时从目标状态出发每次取 parent[state] 直到回到起点把路径反转不要在搜索过程中拼路径列表。4.4 坑四状态去重的时机错误现象BFS 跑得动但结果不是最短解或者队列长度异常增长内存占用比预期高一个数量级。原因visited 在出队时才标记导致同一个状态被多个相邻状态重复入队。虽然最后结果可能还是对的但队列里积压了大量重复项第一次到达目标状态时路径未必最短。解决visited 的标记移到入队之前——检查 next_state in visited如果不在立刻加入 visited 再入队。这个顺序在 BFS 里是硬性要求在 DFS 里则要看目标是“找一条解”还是“找所有解”前者用全局 visited、后者用路径级 visited。4.5 坑五解的唯一性与对称性误判现象程序只输出了一条解但网上或教材里说有两组不同的解法先带羊和先带菜怀疑代码漏了分支。原因BFS 和 DFS 在遇到第一个目标状态时都会立刻返回天然只给出一条路径。这道题确实存在两条不同的七步解但它们在状态图的早期就分叉了搜索算法只会走其中一条。这不是 bug是“找一条解”这个目标的正常行为。解决如果目标是枚举所有解搜索不能提前返回需要在找到目标后记录路径并继续搜索同时把 visited 改成“路径级”的——只阻止当前路径上的环不阻止不同路径经过同一状态。另外要注意两条解路径在状态图上是对称的打印出来的时候操作序列不同但步数相同。5. 设计取舍从“能解”到“解得漂亮”的那半步这道题的代码量不大但写完能跑之后有几个设计取舍值得停下来想一下。第一个取舍是状态编码的粒度。四元组 (L, J, M, N) 是最小够用的编码每个分量一比特。如果为了“可读性”改成存字符串或者枚举代码看起来更直观但状态比较、哈希、去重全部变慢搜索循环里多出来的字符串比较开销在状态空间大的时候会被放大。反过来如果为了“性能”把四元组压成一个 4 位整数状态比较变成整数比较去重可以用布尔数组但代码可读性明显下降调试的时候需要来回做位运算解码。我的习惯是先用元组写清楚逻辑确认结果正确再考虑要不要压成位掩码——这道题 16 个状态压不压都一样。第二个取舍是路径记录方式。把路径列表塞进队列的写法最直观但每扩展一步就复制一次状态多的时候内存和复制开销都不小。换成 parent 字典搜索过程中只存“谁从谁来”回溯时再拼路径内存占用从 O(路径长度 × 状态数) 降到 O(状态数)。这个差别在小图上感觉不出来但在状态空间上千的搜索里就是能不能跑完的问题。我一般会直接用 parent 字典因为改起来也不麻烦而且回溯逻辑写一次就能复用。第三个取舍是搜索策略的选择。BFS 保证最短解但队列可能膨胀DFS 内存占用小但不保证最短还可能因为 visited 的语义问题漏解。这道题两种都能用因为状态少、环短。但如果把它当成搜索算法的练习模板值得把两种都实现一遍然后拿同一个 successors 函数去跑比较输出路径的差异。这个对比比看十页教材都直观。验证方面除了跑通标准解还有几个检查点值得加初始状态和目标状态的 is_safe 必须返回 True从初始状态出发后继状态的数量应该是 2 或者 3取决于农夫在哪一岸、能带哪些东西如果返回 0 或者 4说明 successors 的逻辑有问题BFS 和 DFS 的输出路径步数应该一致如果不一致先检查 BFS 的 visited 时机。还有一个容易被忽略的点是操作的对称性。L(i) 和 R(i) 在代码里被统一成了“翻转位置”但语义上它们是对称操作——带羊过去和带羊回来在状态图上是对称边。如果后面要加“船只能坐农夫和一样东西”之外的约束比如船有方向、或者过河有代价这个对称性就会被打破代码里需要把 L 和 R 拆开。先想清楚约束会不会变再决定要不要提前把两个操作分开写。从那以后我每次写状态空间搜索都会先把 is_safe 和 successors 单独拿出来跑几个手工构造的用例确认约束和操作符没问题再往上搭 BFS 或 DFS。这个习惯救过我很多次——搜索出了问题的时候九成以上的 bug 都在下面这两层而不是搜索本身。希望这个拆解对你有用把这道题当成练习搜索的起点比背下答案更有价值。本文还有配套的精品资源点击获取