给学生讲完深度优先搜索DFS的二叉树遍历总有人追着问这玩意儿在真实问题里到底长什么样翻来覆去想了几天我从一堆课后题里拎出了农夫过河。别看它题干只有一句话——一个农夫、一匹狼、一只羊、一筐白菜一只一次只能坐农夫加一样东西的小船——它的状态空间小到能手工枚举又完整覆盖了DFS的递归、回溯、去重、剪枝所有环节。这篇文章适合正在学DFS、或者想搞明白“搜索算法解决的到底是什么问题”的读者。读完你会发现原来写递归不是靠感觉而是靠一张先在纸上画清楚的状态图。1. 为什么我把农夫过河当作理解DFS的入场题1.1 一读就懂的问题规则农夫要划船把狼、羊、白菜全部从河左岸运到右岸。船只有两个位置农夫自己外加最多一样东西。难点在于三条约束农夫不在场时狼会吃羊农夫不在场时羊会吃白菜而狼和白菜单独待在一起反而没问题因为狼不吃白菜。换句话说核心危险角色是羊狼和白菜不能分别与它独处。这个问题在很多教材里被归入“经典搜索题”和八皇后、迷宫、传教士过河并列。我之所以先拿它开刀是因为它比迷宫更贴近日常直觉迷宫里你至少看得见路过河问题你根本不知道下一步“合法的选择”有哪些必须自己把所有可能性枚举出来。而枚举可能性这件事正是搜索算法要做的事。1.2 直觉盲试为什么必然折返不懂算法的人也能靠人工推理硬解这个题方法就是“试”先带羊过去空船回来再带狼过去再把羊带回来……但如果你没有章法地瞎试很容易陷入重复。比如你把狼带过去之后发现左岸的羊和白菜没人看管只好把狼又带回来再试带白菜发现左岸的狼和羊又打起来了绕来绕去可能十分钟过去了船还在原地。这个“重复”就是搜索算法存在的理由。人脑盲试的时候很难记住全部试过的状态计算机用一个小小的set就能做到。DFS在这个问题里做的事本质上是把“瞎试”变成“有记忆的、系统的瞎试”一条路走不通就退回上一个岔路口走另一条走过的状态绝对不再走第二次。1.3 DFS在这道题里的角色如果用一句话概括DFS在这个问题里的定位它负责在合法的状态之间移动利用回溯机制处理走不通的分支利用visited集合处理回头路最终找到一条从初始状态到目标状态的合法路径。它不保证这条路径最短只保证“找得到”。搞清楚这个定位很重要因为后面你会发现农夫过河由于状态空间极小DFS表现很好但一旦问题规模变大这种“找到就行”的作风就会带来麻烦。2. 16个状态还是10个状态动手写递归前先把图建出来2.1 用0和1给河岸编码我见过很多人一上来就写递归写了半天不知道终止条件怎么定。问题的根源在于没有建模。农夫过河一共四个对象农夫、狼、羊、白菜。每个对象只有两种位置左岸或右岸。所以完整的状态空间是2的4次方一共16个状态。实际编码时我用一个四元组(f, w, s, c)表示当前状态四个位置从左到右分别代表农夫、狼、羊、白菜。其中1表示在左岸0表示在右岸。初始状态是(1, 1, 1, 1)表示四个对象全在左岸目标状态是(0, 0, 0, 0)表示全在右岸。这样设计的好处是右岸的信息不需要额外记录右岸就是“值为0的那些东西”一个元组同时表达了两个岸的情况。为什么要专门说这个因为很多初学者喜欢用两个列表分别记录左岸和右岸转移的时候同步维护两个列表极其容易出错。用0/1编码后一次过河动作只需要把对应位置从0变1或从1变0简单直接。2.2 6个非法状态一次筛干净16个状态不是都能用的。根据“狼和羊不能独处、羊和白菜不能独处”这条规则我手工枚举了一遍非法状态一共有6个见下表。非法状态 (f, w, s, c)实际场景违规原因(1, 1, 0, 0)左岸农夫、狼右岸羊、白菜右岸羊和白菜独处(1, 0, 0, 1)左岸农夫、白菜右岸狼、羊右岸狼和羊独处(1, 0, 0, 0)左岸农夫右岸狼、羊、白菜右岸狼吃羊、羊吃白菜(0, 1, 1, 1)左岸狼、羊、白菜右岸农夫左岸狼吃羊、羊吃白菜(0, 1, 1, 0)左岸狼、羊右岸农夫、白菜左岸狼和羊独处(0, 0, 1, 1)左岸羊、白菜右岸农夫、狼左岸羊和白菜独处16个状态去掉6个非法状态剩下10个合法状态。初始状态和目标状态都在合法集合里。这个结论是可以直接作为代码注释写进去的一个状态合法当且仅当“没有农夫的那一岸不同时出现狼和羊也不同时出现羊和白菜”。2.3 状态转移可逆的“农夫动作”状态之间的连接关系来自农夫的动作。农夫每次过河可以做两件事之一要么独自过河要么带一个与自己同岸的东西过河。不管哪种情况农夫的位置一定取反如果带了东西那个东西的位置也取反。这个转移有一个非常重要的性质它是可逆的。如果状态A能通过“农夫带羊从左到右”到达状态B那么B一定能通过“农夫带羊从右到左”回到A。也就是说整个合法状态图是无向的。这个性质对DFS意义重大回溯之所以成立就是因为我们总能沿着来路退回去。如果把10个合法状态按转移关系连起来会得到一张非常小的无向图。DFS在这张图上走本质上和一个带记忆的人走迷宫没有区别。3. 完整代码递归、回溯、visited是如何一起工作的3.1 先写合法性判断代码第一块是合法性判断函数。核心逻辑就是顺着2.2的规则翻译def is_valid(state): f, w, s, c state # 农夫不在左岸时左岸不能留下“狼羊”或“羊白菜” if f 0 and ((w 1 and s 1) or (s 1 and c 1)): return False # 农夫不在右岸时右岸不能留下“狼羊”或“羊白菜” if f 1 and ((w 0 and s 0) or (s 0 and c 0)): return False return True这段代码对应着“狼吃羊、羊吃白菜”的全部危险组合。注意我用的是右岸状态取补的方式w 0表示狼不在左岸即在右岸。理解了这个补集逻辑后面的状态转移代码才读得懂。3.2 再写邻居生成邻居生成函数负责从当前状态算出农夫一次过河后可能到达哪些合法状态。逻辑分三步农夫位置取反判断农夫在左岸还是右岸从而决定能带哪些同岸物品逐个尝试并过滤非法结果。def get_neighbors(state): f, w, s, c state nf 1 - f # 农夫必然过河位置取反 result [] # 情况一农夫独自过河 ns (nf, w, s, c) if is_valid(ns): result.append(ns) # 情况二农夫带一个物品过河物品必须与农夫同岸 items [] if f 1: # 农夫在左岸 if w 1: items.append(w) if s 1: items.append(s) if c 1: items.append(c) else: # 农夫在右岸 if w 0: items.append(w) if s 0: items.append(s) if c 0: items.append(c) for item in items: if item w: ns (nf, 1 - w, s, c) elif item s: ns (nf, w, 1 - s, c) else: ns (nf, w, s, 1 - c) if is_valid(ns): result.append(ns) return result这段代码有一个隐含细节我先把“独自过河”放进候选列表再枚举带物品的情况。这个顺序会影响DFS最终搜索路径。后面第4章你会看到仅仅调换这个顺序输出路径就可能完全不同。3.3 最后写DFS主流程主流程是标准的三件套visited集合、path列表、递归函数。我把完整代码贴出来INIT_STATE (1, 1, 1, 1) # 农夫、狼、羊、白菜都在左岸 GOAL_STATE (0, 0, 0, 0) # 全部移到右岸 visited set() path [] def dfs(state): if state GOAL_STATE: return True visited.add(state) for ns in get_neighbors(state): if ns in visited: continue path.append(ns) if dfs(ns): return True path.pop() # 回溯撤销当前选择 return False path.append(INIT_STATE) dfs(INIT_STATE) print(搜索过程中访问过的状态数:, len(visited)) print(完整路径含起点:) for i, s in enumerate(path): print(f第{i}步: {s})这里有几个关键点必须解释清楚。第一visited必须是集合而不是列表因为状态只有10个合法值用集合的查找是O(1)量级大了这个差距会非常明显。第二path记录的是从起点到当前状态的完整路径它和visited是两个东西visited管“别走回头路”path管“最后输出答案”。第三回溯发生在path.pop()这行它的含义是当前状态的所有邻居都试完且都失败撤销刚才的选择回到上一层递归继续尝试别的分支。不少初学者会把visited和path混为一谈用if ns not in path代替if ns in visited。在这个小问题里运气好也能跑通但一旦状态图出现环就会陷入死循环。因为path保存的是当前这一条路径上的节点不是“历史上所有到过的节点”。这一步的差别是DFS面试里最常见的坑之一。4. 跑通之后看细节DFS探索了哪些状态又错过了哪些4.1 运行输出和路径翻译我按上面代码原样运行输出如下搜索过程中访问过的状态数: 8 完整路径含起点: 第0步: (1, 1, 1, 1) 第1步: (0, 1, 0, 1) 第2步: (1, 1, 0, 1) 第3步: (0, 0, 0, 1) 第4步: (1, 0, 1, 1) 第5步: (0, 0, 1, 0) 第6步: (1, 0, 1, 0) 第7步: (0, 0, 0, 0)把这串状态翻译成人话就是经典的七步答案农夫带羊过河左岸剩下狼和白菜农夫空船返回左岸农夫带狼过河右岸变成农夫、狼、羊左岸只剩白菜农夫带羊返回左岸防止狼吃羊农夫带白菜过河右岸变成农夫、狼、白菜左岸只剩羊农夫空船返回左岸农夫带羊过河完成。看到没有整个过程中羊被折腾得最惨来回被带了三次。这不是算法偏心而是羊同时是狼和白菜的天敌它是唯一的“冲突枢纽”必须反复押送。4.2 8个visited状态背后DFS放弃了什么有趣的是10个合法状态里DFS只访问了8个有2个合法状态自始至终没有出现在路径里(1, 1, 1, 0)表示“左岸是农夫、狼、羊右岸是白菜”(0, 1, 0, 0)表示“左岸只有狼右岸是农夫、羊、白菜”。这两个状态之所以没被访问是因为DFS一进入某条分支就直奔目标去了压根没有机会试探另一条分支。这就是DFS最典型的性格宁可一条道走到目标也不愿意先把所有邻居都看一遍。在农夫过河这个图里10个状态太少了所以它看起来“很聪明”一步冤枉路都没多走。但换成状态空间更大的问题这种一根筋的走法就可能把它带进一条很长的死路浪费大量时间。理解这一点才算真正理解了为什么有时候DFS会“碰巧”很快有时候又“离奇”地慢。4.3 换一种遍历顺序结果可能完全不一样我在3.2节提到过get_neighbors里候选状态的枚举顺序会直接影响DFS的输出。如果把候选顺序改成“先带羊、再带狼、再空船、再带白菜”初始状态下第一个合法邻居仍然是带羊但走到(1, 1, 0, 1)这个状态时DFS会优先尝试带白菜过河走另一条分支。我在本地试过调整顺序后的结果路径完全变了第0步: (1, 1, 1, 1) 第1步: (0, 1, 0, 1) 第2步: (1, 1, 0, 1) 第3步: (0, 1, 0, 0) 第4步: (1, 1, 1, 0) 第5步: (0, 0, 1, 0) 第6步: (1, 0, 1, 0) 第7步: (0, 0, 0, 0)这条路径也是7步但中间过程完全不同先带狼过去再带白菜羊在中间只被带了一次比之前的解法少折腾了一趟。这个现象说明对于同一个问题DFS的输出很大程度取决于邻居的枚举顺序。如果枚举顺序不好DFS可能找到一条明显绕弯的路径甚至在某些问题里走了指数级的长路才到达目标。4.4 调试DFS的实用方式递归缩进打印写DFS的时候我最推荐一个调试技巧在递归函数进出时打印状态并用缩进表示递归深度。代码改动极小depth 0 def debug_dfs(state): global depth if state GOAL_STATE: print( * depth f到达目标 {state}) return True print( * depth f进入 {state}) visited.add(state) depth 1 for ns in get_neighbors(state): if ns in visited: continue path.append(ns) if debug_dfs(ns): return True path.pop() depth - 1 print( * depth f回退 {state}) return False输出会呈现一棵清晰的递归树。你会看到“进入 (1,1,0,1)”之后尝试某个邻居被打回再尝试另一个。这个打回的过程就是回溯。很多学生看完这棵缩进树才真正明白“递归调用栈”是什么概念。这个方法我几乎在每个搜索类题目上都会用比单步调试高效得多。5. 约束一改结论就变容量升级和物品扩容下的算法选择5.1 如果船一次能带两件物品把问题里的船升级一下一次能带两样东西。这个改动看似简单状态图和转移关系立刻变复杂。从初始状态(1, 1, 1, 1)出发农夫可以选择带“狼羊”“羊白菜”“狼白菜”甚至任意两件组合其中“狼白菜”的组合直接让左岸只剩羊右岸是农夫、狼、白菜一步就把大部分问题解决了。我用带两件的转移逻辑跑了一下DFS仍然能找到解但路径出现了明显的不同如果枚举顺序是单件优先DFS会先试单件先绕到7步以上的路径如果枚举顺序是双件优先3步就能结束。这个例子非常直观地说明约束越少转移越密DFS“走错分支再退回”的机会成本越高。而BFS在这种转移密集的图里反而能更快给出最短解。5.2 物品数量变大时DFS的处境假设把物品从3样增加到4样、5样状态数量会从16个变成32个、64个。表面上看数量依然不大但合法状态和转移边数可能增长得更快。更麻烦的是如果存在一条很长的非法分支DFS会一头扎进去一直扎到最深处才发现此路不通然后慢慢回溯。这种“深钻”行为在最坏情况下会访问指数级的状态。实际工程里我很少用深度优先来处理这种小规模组合问题除非明确只需要“找到一个可行解”。如果既要找解、又要证明步数最少那优先选BFS如果状态空间大到BFS内存放不下就考虑迭代加深。所谓迭代加深就是反复用DFS但每次都设置一个最大深度第一轮限制只能走3步第二轮限制只能走5步依此类推。它既保留了DFS的低空间占用又能像BFS一样保证首次找到的路径是短路径。5.3 DFS和BFS的选择题还是回到农夫过河本身。假设现在问你是否存在一条不超过5步的合法方案DFS不会回答这个问题因为它找到的第7步解只能证明“有解”。要证明“5步内有解”你必须把所有不超过5步的状态全部展开这正是BFS的活。对比维度DFSBFS空间占用只存当前路径小需要存整层节点可能大是否保证最短路径不保证保证迷宫/连通性问题很合适找路快也能做但空间消耗大状态数量爆炸的组合题容易深陷错误分支层次推进可靠但慢农夫过河这类小状态题足够用完全够用且路径最短我给读者的建议很简单先看问题要什么。只求“有没有解”优先DFS求“最少几步”“最短路径”优先BFS。农夫过河是少有的两者都能轻松搞定的题目正好适合拿来做对比实验。5.4 用BFS写一遍马上看出两种算法的气质差异BFS的代码也很短我用队列实现每个队列元素保存状态和到达该状态的完整路径from collections import deque def bfs(): start INIT_STATE if start GOAL_STATE: return [start] queue deque() queue.append((start, [start])) visited {start} while queue: state, path queue.popleft() for ns in get_neighbors(state): if ns in visited: continue new_path path [ns] if ns GOAL_STATE: return new_path visited.add(ns) queue.append((ns, new_path)) return None跑出来的结果同样是7步路径但它能保证“不可能少于7步”。这就是BFS给你的一颗定心丸。相比之下DFS给不出这样的保证它只是第一个冲过终点线的选手。6. 这个题目讲完我最想对你说的三件事6.1 纸上画状态图比写递归更重要这句话我几乎每次讲搜索都会强调。农夫过河的完整状态图只有10个合法节点用笔在纸上画出来连好转移边再回头看代码递归的每一步都对应图上的某一条边。一旦做到这个对应关系DFS就从一个“玄乎的递归”变成了一个“在图上老老实实走路的程序”。我自己初学DFS时也犯过这个错误抱着代码啃反复看递归过程越看越糊涂。后来把迷宫状态图画出来用笔模拟递归指针移动半小时就通了。6.2 最常见的一个bugvisited用错了地方我帮人改过很多次DFS代码发现最有代表性的错误就是那类“用path代替visited”的写法。问题代码往往长这样# 错误示范用 path 去重 if ns not in path: path.append(ns) dfs(ns) path.pop()在小状态图上它可能侥幸跑通但一旦状态图出现环或者同一个状态可以通过不同路径再次到达程序要么死循环要么重复搜索大量分支。正确的做法是让visited独立记录所有被访问过的状态path只负责记录当前路径。这个坑在二叉树上完全不会出现因为树没有环换成图一下子就暴露了。农夫过河正好是“从树到图”的过渡题踩一次这个坑后面写图的DFS基本就不会再犯了。6.3 下一步可以玩什么变体觉得农夫过河太简单的话我建议试着这么改限制总步数要求DFS在中途剪枝把船容量改成2并把物品变成4样或者比较不同枚举顺序下DFS访问状态数的变化。这些改动都不大但每一个都能让你对搜索算法多一层体感。我个人这两年讲这个题最大的体会是经典题的价值不在于题本身有多难而在于它能不能让人在一张白纸上把思路完整铺开。农夫过河恰好做到了这一点——状态少、规则清晰、结果可人工验证。如果你正在学DFS别急着刷一堆迷宫题先把这道题跑通、画懂、改烦再往前走。
