“小船过河问题”这四个字我教了十多年也看着它从物理卷子一路爬到算法面试题里。很多人觉得它简单可每次考场上总有人因为一个方向角度多扣好多分。原因不是公式难背而是这个题考的从来不是算数而是两个运动叠加在一起时你愿不愿意先把它们拆开再合并。这篇文章想把这道经典题从物理、逻辑、算法三个层面完整拆一遍讲清楚最短时间和最短位移为什么不是同一个解讲清楚农夫过河为什么本质上是一张状态图再给出一套可以直接用代码跑的搜索模板。备考的学生、辅导孩子的家长、刷题的工程师都能从里面对号入座。1. 先别急着划船小船过河到底在问什么1.1 卷子上最常见的两种问法如果你去翻一本高中物理练习册最常见的过河题长这样一条河宽为 d水流速度恒为 v水一艘船在静水中的速度是 v船。然后题目分成两种问法一种问“最短过河时间是多少”另一种问“船到达正对岸需要多长时间”。题干信息就这么多却能延伸出完全不同的计算过程。我给学生上课时第一步永远是让他们回答一个问题发动机给你的速度是相对于水的速度还是相对于岸的速度答案是前者。船速 v船 是船相对水的速度它只由船头指向决定水速 v水 是水相对岸的速度而船真正走过的轨迹是这两个速度叠加出来的合速度。很多人题目没做错但问他船实际朝哪开却说不清就是这三个概念没在脑子里立住。这道题真正的考点是“速度是矢量”。既然是矢量就不能像小学算术一样直接相减相加必须先定方向再按平行四边形法则合成。只要你把“船速、水速、合速度”三个量放对位置剩下全是初中几何。1.2 跑步机类比把抽象概念一次性说透我用一个生活类比来解释速度合成效果一直很好。想象你站在商场里的跑步机上跑步机以每秒 1 米向后滚动你以每秒 2 米的速度向前跑。对旁边的人来说你实际上是以每秒 1 米的速度前进而不是每秒 3 米也不是每秒 2 米。如果这时候你要去跑步机正前方的一杯水你得微调跑步方向不能完全顺着跑步机方向走。小船过河一模一样水速相当于跑步机船速相当于你的跑步能力而“实际轨迹”是这两个速度共同作用的结果。这个类比的另一个好处是能直观解释“为什么船头直指对岸时时间最短”。在跑步机上如果你想到达正前方某个点最好的办法不是侧着跑而是先加速往前跑再修正方向。但如果你只关心“从这头到那头时间最少”跑步机能不能把你带偏根本不重要你只要朝目标方向全力跑就行。对应的物理结论是船头垂直指向对岸时船在横渡方向上的速度分量最大时间自然最短。1.3 所有过河问题共享的骨架不管题目怎么变形背后只有三条规则把船速分解成“垂直于岸”和“平行于岸”两个方向垂直于岸的分速度决定过河时间也就是 t d / v垂直平行于岸的分速度叠加水速后决定船实际到达的位置。这三条规则听起来平淡却是整道题的骨架。最短时间、最短位移、最小路程、以及你以后可能在算法题里见到的各类“过河变体”本质上都是这三句话在不同条件下的推演。想通这一点你就不会觉得它是一个孤立公式而是一套可以复用的分析方法。2. 最短时间、最短位移、最短航程三种经典问法的推导与陷阱2.1 最短时间船头对准对岸但人确实“漂”下去了先看最短时间。要让横渡时间最短就得让垂直于岸的方向速度分量最大。船速大小固定什么时候分量最大当然是船头完全垂直于岸的时候此时垂直分速度就是 v船。于是最短时间t_min d / v船这段时间里水会把人往下游冲多远Δx v水 × t_min v水 × d / v船很多人做完第一问就顺手填了“终点在正对岸”这是不对的。船在水流里走了斜线它确实是最快到达对岸的方案但到达点一定偏向下游。要记住一个反直觉的结论最短时间不等同于最短位移想要快就别管漂不漂想要准就得牺牲速度。这个问题的陷阱还在于经常有人问“最短时间内到底沿什么方向开”。方向就是垂直岸开没有第二个答案。有些同学试图“稍微偏上游一点好让落点不那么偏”结果垂直分量变小时间反而变长。方向一动时间就长这是这类题最容易踩的坑。2.2 最短位移当船速大于水速船头必须“斜着抢”再看最短位移也就是让船实际到达对岸正对的位置。这种情况下船头不能再直指对岸了必须斜向上游用船速的一个分量去抵消水速。设船头与垂直岸方向的夹角为 α则沿河方向v船 sinα 抵消 v水于是 sinα v水 / v船垂直岸方向的分速度v船 cosα sqrt(v船² - v水²)过河时间t d / sqrt(v船² - v水²)这里的几何关系很漂亮水速是直角边船速是斜边合速度是另一直角边。合速度必须严格垂直于岸船实际轨迹才是直线正对岸。有人把合速度理解成 v船 - v水那就犯了把矢量当标量的错误。垂直与抵消是完全不同的两个方向只能走勾股定理。还需要注意一个条件这个解法要求 v船 v水。如果船速和水速一样大即使船头完全逆着水流方向开到极限也刚刚能保证不往下游漂垂直方向分速度已经变成 0船根本过不了河。所以 v船 v水 是“垂直正对岸过河”的硬门槛。2.3 船速小于水速最短位移不是垂直而是斜向下游当 v船 v水 时垂直过河已经不可能船必然会被冲向下游。那题目如果还问“最短位移”要怎么理解就是要让实际轨迹偏离正对岸的角度最小也就是在不可避免的漂移里挑一个最小的。这时的几何结论非常漂亮让船头斜向上游并使得船速与合速度垂直偏距最小。具体公式船头偏向上游且 sinα v船 / v水实际路径与垂直岸方向的夹角 β 满足 tanβ sqrt(v水² - v船²) / v船最短实际路程 d × v水 / v船过河时间 d × v水 / (v船 × sqrt(v水² - v船²))我拿一个典型数值举例河宽 100 米水速 4 m/s船速 2 m/s。按公式最短路程是 100 × 4 / 2 200 米过河时间约 57.7 秒。也就是说船速只有水速一半时你想“尽可能正对岸”到达实际走的距离已经是河宽的两倍。这个结果对第一次接触的人非常反直觉但它是完全正确的。这里有个记忆技巧不管 v船 比 v水 大还是小“最短位移”对应的那个角度公式长得像一对镜像。v船 v水 时 sinα v水/v船v船 v水 时 sinα v船/v水。其实就是把“谁在分母”换一下本质是让较强的那个速度充当斜边。2.4 三种问法对比表我把上面三种情况整理成一个表方便直接对照问法船头方向合速度方向过河时间实际路程最短时间垂直对岸斜向下游d / v船d × sqrt(1 (v水/v船)²)最短位移v船 v水偏上游sinα v水/v船严格垂直对岸d / sqrt(v船² - v水²)d最短位移v船 v水偏上游sinα v船/v水斜向下游d×v水 / (v船×sqrt(v水² - v船²))d×v水/v船用这个表之前永远先判断 v船 和 v水 谁大谁小。大小关系判断错了整个题就废了。2.5 常见翻车点把速度三角形画反最后讲一个我在批改里见了几百次的问题速度三角形画反。很多人画图习惯“先画水速再画合速度”这没问题。但一旦题目考最短位移他们就让合速度参加三角形合成画出来船头方向就错了。正确的画法是先用平行四边形或者矢量三角形把三个速度的关系画对。水速沿河向下游船头方向画船速船速与合速度共同决定实际轨迹。如果要求垂直过河合速度必须指向正对岸水速作为水平直角边船速作为斜边构成一个直角三角形。还有一类人求最短位移的时间时直接除以 v船。这等于默认船头正对岸时间当然会被低估。最短位移的代价就是船头偏了垂直速度分量变小时间必然比 d/v船 长这一点可以用上面的表格自行验证。3. 从物理题到逻辑题农夫过河为什么是状态搜索3.1 场景切换船还在但问题变成了“谁和谁不能单独待”如果说物理版小船过河看到的是连续轨迹那么逻辑版过河看到的是一系列离散状态。最经典的例子就是农夫过河农夫要带狼、羊、白菜从河左岸到右岸船每次只能载农夫和一样东西。狼会吃羊羊会吃白菜农夫不在场时绝对不能让它俩单独相处。我第一次给学生讲这个题时很多人直接懵住因为这里没有公式可以套只有规则。但换个角度看它其实就是一个带约束的状态搜索问题每一步之后两岸的物品组合都必须“安全”。所谓安全就是不出现狼羊同岸且农夫不在、羊菜同岸且农夫不在这两种情况。如果你静下心自己走一遍会发现最自然的正确步骤恰恰是那个七步解法。我把每一步列在下面方便你直接照着推演。3.2 七步解法最关键的“倒车”并不多余步骤农夫动作农夫位置左岸剩余物品右岸剩余物品0初始状态左狼、羊、菜、农夫无1带羊过河右狼、菜羊、农夫2农夫独自返回左狼、菜、农夫羊3带狼过河右菜狼、羊、农夫4带羊返回左菜、羊、农夫狼5带菜过河右羊狼、菜、农夫6农夫独自返回左羊、农夫狼、菜7带羊过河右无狼、羊、菜、农夫很多初学者不愿意走“带羊返回”那一步觉得这是在绕路。但正是这个倒车动作打破了“狼和羊已经在右岸”的危险局面。换句话说某些物品必须先运过去充当临时中转等到另一侧有了足够安全条件再回来把它接到最终位置。这是这类状态搜索题的核心思想最短路径不一定让每件东西都只被运一次有时需要回撤。3.3 农夫的位置才是最容易被忽略的状态变量如果你自己推演时发现某些步骤“怎么也算不通”大概率是忽略了农夫在船上的这个属性。狼羊菜问题里船不能自己动所有行动都必须有农夫随船。也就是说“农夫在左岸”和“农夫在右岸”是两个完全不同的状态必须写进状态定义里。有一种常见错误是这样的有人把状态只记录成“左岸物品集合”然后搜着搜着出现一个转移右岸的狼和羊没人管却假定安全。这就是因为没把农夫位置纳入状态导致非法转移被当作合法转移。只要记住一点——农夫在哪船就在哪——整个状态定义就完整了。如果把这个逻辑题写得更形式化状态就是一个二元组(左岸物品集合, 农夫所在岸)。初始状态是左岸包含狼羊菜农夫在左岸目标状态是左岸为空集农夫在右岸。每一次动作都从船所在侧选择空船或带一件物品前往对岸然后检查两岸是否安全。你看这不就天然变成了一个搜索问题。4. 把过河问题写进代码一个通用的 BFS 模板4.1 为什么是 BFS农夫过河问题换成代码来解几乎是 BFS广度优先搜索的标准教学案例。原因是所有动作花费的步数都一样过河一次算一步。BFS 从初始状态一层层向外扩展第一层到达目标时路径一定是最短步数。DFS 也能搜到解但它可能一条路走到黑找到的路径不一定最短。这种问题状态规模也很小左岸物品是狼羊菜三元素的子集再加上农夫位置总共只有 2 × 2³ 16 个状态。BFS 不会遇到性能压力代码逻辑反而最直观。状态少的时候暴力搜索就是最好的优雅。4.2 状态、动作与合法性检查代码的核心是三个部分状态表示、状态转移、安全校验。状态我习惯用一个元组表示(左岸物品集合, 农夫是否在左岸)。为了让状态可哈希、能放进 visited 集合左岸集合用 frozenset 而不是 set。动作是从农夫当前所在侧选一件物品带走或者空船独自返回。每一次转移后都要执行安全校验农夫不在的那一侧不能同时出现狼和羊也不能同时出现羊和菜。这里直接给一份完整可运行的 Python 代码核心模板都在里面from collections import deque ITEMS {wolf, sheep, cabbage} def is_safe(left_set, farmer_left): right_set set(ITEMS) - set(left_set) # 农夫不在的那一侧不能出现食物链组合 def side_ok(items, farmer_here): if farmer_here: return True return not ( (wolf in items and sheep in items) or (sheep in items and cabbage in items) ) return side_ok(left_set, farmer_left) and side_ok(right_set, not farmer_left) def next_states(state): left_set, farmer_left state # 船当前所在侧的全部物品 boat_items set(left_set) if farmer_left else set(ITEMS) - set(left_set) # 空船过河或者带其中一件过河 for load in [set()] [{item} for item in boat_items]: if farmer_left: new_left set(left_set) - load farmer False else: new_left set(left_set) | load farmer True if is_safe(new_left, farmer): yield (frozenset(new_left), farmer) def solve(): start (frozenset(ITEMS), True) # 农夫、狼、羊、菜都在左岸 target (frozenset(), False) # 农夫和所有物品都在右岸 q deque([(start, [])]) visited {start} while q: state, path q.popleft() if state target: return path for nxt in next_states(state): if nxt not in visited: visited.add(nxt) q.append((nxt, path [nxt]))运行这段程序得到的动作序列就是经典七步带羊过去、农夫独自回来、带狼过去、带羊回来、带菜过去、农夫独自回来、带羊过去。代码不会“思考”它只是把合法状态一层层展开直到碰到目标。4.3 这个模板能迁移到哪些场景很多人学算法喜欢套模板但真正有用的不是背模板而是会“翻译”。过河问题的 BFS 模板换一层皮就可以解决很多同类问题。比如传教士与野人过河三个传教士和三个野人过河船最多载两人任意一侧野人数量不能超过传教士数量。状态定义无非多一个变量安全规则换成“野人是否超过传教士”。再比如两个水壶倒水问题、八数码问题、华容道本质也都是状态搜索定义好状态、动作、合法性和目标判断然后用 BFS 或 A 星去搜。你只要熟悉一遍“小船过河”这种状态题再看这些题会感觉它们的骨架长得一模一样。如果状态空间变大比如物品数量从 3 变成 1016 个状态变成几千个BFS 仍然可解但可以把 visited 设计得更精细或者改用双向 BFS、A 星搜索来提速。更重要的是状态表示本身决定搜索效率写状态题的第一个动作永远是设计状态而不是写循环。5. 我在讲这道题时反复遇到的坑和积累的技巧5.1 画矢量图的第一笔决定了整道题的生死关于物理版本的小船过河我最深的体会是图形画对了题目就做对了一半。很多学生列不出公式不是公式没背而是不知道合速度该从哪里指向哪里。我建议画图时严格按这个顺序来先画水速方向沿河箭头标成 v水再从船头方向画船速最后把起点和终点连起来得到合速度。如果是求最短位移合速度方向必须是你希望船实际走的方向然后用几何关系反推船头方向。顺序一旦反了角度会跟着错后面全盘皆输。我在黑板上演示时喜欢用一支笔和一把尺把三个速度向量岔开画成胖三角形。等学生亲眼看到“水速不是跟船速直接抵消而是跟船速在河方向上的分量抵消”大多数错误都能当场消失。5.2 做题顺序建议先判大小再选公式还有一个经验值得刻在脑门上看到过河题先别急着套最短位移公式先看 v船 和 v水 谁大谁小。v船 v水可以垂直过河最短位移等于河宽 d。v船 v水理论极限合速度不能获得横向分量船只能沿着水流方向漂严格说无法过河。v船 v水不能垂直过河最短位移是 d×v水/v船且船头偏角用 sinα v船/v水。我见过不少人在 v船 v水 的题里硬套 d/sqrt(v船²-v水²)结果算出根号下负数或者算出一个比 d 还短的路程。碰到这种明显不合理的数字就该回头检查前提。5.3 如果“过河”出现在算法题里先分清是哪种过河不过如果你是在算法题里看到“过河”两个字还要多个心眼。算法题里的过河往往是另一种模型若干人夜晚过桥每次最多两人需要手电筒每个人速度不同求最短总时间。这就是经典的“n人过桥问题”和物理小船题、农夫状态题完全是两码事。举一个四人过桥的例子速度分别是 1、2、5、8 分钟。只用最快的人来回送总时间是 8 1 5 1 2 17 分钟。但更优的做法是让最快的两个先过最慢的两个一起过耗时 2 1 8 2 2 15 分钟。核心思路是最慢的两个人必须绑定在一起过桥这样能省一次慢速往返。这种问题不是 BFS而是一个贪心加动态规划的决策问题。所以碰到“过河”类题目我建议先自查三件事有哪些主体它们之间有没有互斥关系船/桥的运力是多少目标是最短时间还是找到一个合法路径这三件事搞清楚选对思路题基本就解了一半。最后再分享一个小习惯我做这类题时从不直接跳到公式或代码而是先手写一张小状态表把“谁在哪一边、下一步能做什么”写下来。看起来很笨但恰恰是这套方法帮我避开了大部分低级错误。小船过河问题之所以经典就是因为它用最少的元素逼你想清楚运动的合成、状态的约束和搜索的路径。想通这三件事再遇到它就不会只是背公式而是一种非常自然的推理过程。 
长河君 · 2026/10/11 8:42:31 · 阅读 1.2k 小船过河全解析：速度合成与BFS状态搜索
“小船过河问题”这四个字我教了十多年也看着它从物理卷子一路爬到算法面试题里。很多人觉得它简单可每次考场上总有人因为一个方向角度多扣好多分。原因不是公式难背而是这个题考的从来不是算数而是两个运动叠加在一起时你愿不愿意先把它们拆开再合并。这篇文章想把这道经典题从物理、逻辑、算法三个层面完整拆一遍讲清楚最短时间和最短位移为什么不是同一个解讲清楚农夫过河为什么本质上是一张状态图再给出一套可以直接用代码跑的搜索模板。备考的学生、辅导孩子的家长、刷题的工程师都能从里面对号入座。1. 先别急着划船小船过河到底在问什么1.1 卷子上最常见的两种问法如果你去翻一本高中物理练习册最常见的过河题长这样一条河宽为 d水流速度恒为 v水一艘船在静水中的速度是 v船。然后题目分成两种问法一种问“最短过河时间是多少”另一种问“船到达正对岸需要多长时间”。题干信息就这么多却能延伸出完全不同的计算过程。我给学生上课时第一步永远是让他们回答一个问题发动机给你的速度是相对于水的速度还是相对于岸的速度答案是前者。船速 v船 是船相对水的速度它只由船头指向决定水速 v水 是水相对岸的速度而船真正走过的轨迹是这两个速度叠加出来的合速度。很多人题目没做错但问他船实际朝哪开却说不清就是这三个概念没在脑子里立住。这道题真正的考点是“速度是矢量”。既然是矢量就不能像小学算术一样直接相减相加必须先定方向再按平行四边形法则合成。只要你把“船速、水速、合速度”三个量放对位置剩下全是初中几何。1.2 跑步机类比把抽象概念一次性说透我用一个生活类比来解释速度合成效果一直很好。想象你站在商场里的跑步机上跑步机以每秒 1 米向后滚动你以每秒 2 米的速度向前跑。对旁边的人来说你实际上是以每秒 1 米的速度前进而不是每秒 3 米也不是每秒 2 米。如果这时候你要去跑步机正前方的一杯水你得微调跑步方向不能完全顺着跑步机方向走。小船过河一模一样水速相当于跑步机船速相当于你的跑步能力而“实际轨迹”是这两个速度共同作用的结果。这个类比的另一个好处是能直观解释“为什么船头直指对岸时时间最短”。在跑步机上如果你想到达正前方某个点最好的办法不是侧着跑而是先加速往前跑再修正方向。但如果你只关心“从这头到那头时间最少”跑步机能不能把你带偏根本不重要你只要朝目标方向全力跑就行。对应的物理结论是船头垂直指向对岸时船在横渡方向上的速度分量最大时间自然最短。1.3 所有过河问题共享的骨架不管题目怎么变形背后只有三条规则把船速分解成“垂直于岸”和“平行于岸”两个方向垂直于岸的分速度决定过河时间也就是 t d / v垂直平行于岸的分速度叠加水速后决定船实际到达的位置。这三条规则听起来平淡却是整道题的骨架。最短时间、最短位移、最小路程、以及你以后可能在算法题里见到的各类“过河变体”本质上都是这三句话在不同条件下的推演。想通这一点你就不会觉得它是一个孤立公式而是一套可以复用的分析方法。2. 最短时间、最短位移、最短航程三种经典问法的推导与陷阱2.1 最短时间船头对准对岸但人确实“漂”下去了先看最短时间。要让横渡时间最短就得让垂直于岸的方向速度分量最大。船速大小固定什么时候分量最大当然是船头完全垂直于岸的时候此时垂直分速度就是 v船。于是最短时间t_min d / v船这段时间里水会把人往下游冲多远Δx v水 × t_min v水 × d / v船很多人做完第一问就顺手填了“终点在正对岸”这是不对的。船在水流里走了斜线它确实是最快到达对岸的方案但到达点一定偏向下游。要记住一个反直觉的结论最短时间不等同于最短位移想要快就别管漂不漂想要准就得牺牲速度。这个问题的陷阱还在于经常有人问“最短时间内到底沿什么方向开”。方向就是垂直岸开没有第二个答案。有些同学试图“稍微偏上游一点好让落点不那么偏”结果垂直分量变小时间反而变长。方向一动时间就长这是这类题最容易踩的坑。2.2 最短位移当船速大于水速船头必须“斜着抢”再看最短位移也就是让船实际到达对岸正对的位置。这种情况下船头不能再直指对岸了必须斜向上游用船速的一个分量去抵消水速。设船头与垂直岸方向的夹角为 α则沿河方向v船 sinα 抵消 v水于是 sinα v水 / v船垂直岸方向的分速度v船 cosα sqrt(v船² - v水²)过河时间t d / sqrt(v船² - v水²)这里的几何关系很漂亮水速是直角边船速是斜边合速度是另一直角边。合速度必须严格垂直于岸船实际轨迹才是直线正对岸。有人把合速度理解成 v船 - v水那就犯了把矢量当标量的错误。垂直与抵消是完全不同的两个方向只能走勾股定理。还需要注意一个条件这个解法要求 v船 v水。如果船速和水速一样大即使船头完全逆着水流方向开到极限也刚刚能保证不往下游漂垂直方向分速度已经变成 0船根本过不了河。所以 v船 v水 是“垂直正对岸过河”的硬门槛。2.3 船速小于水速最短位移不是垂直而是斜向下游当 v船 v水 时垂直过河已经不可能船必然会被冲向下游。那题目如果还问“最短位移”要怎么理解就是要让实际轨迹偏离正对岸的角度最小也就是在不可避免的漂移里挑一个最小的。这时的几何结论非常漂亮让船头斜向上游并使得船速与合速度垂直偏距最小。具体公式船头偏向上游且 sinα v船 / v水实际路径与垂直岸方向的夹角 β 满足 tanβ sqrt(v水² - v船²) / v船最短实际路程 d × v水 / v船过河时间 d × v水 / (v船 × sqrt(v水² - v船²))我拿一个典型数值举例河宽 100 米水速 4 m/s船速 2 m/s。按公式最短路程是 100 × 4 / 2 200 米过河时间约 57.7 秒。也就是说船速只有水速一半时你想“尽可能正对岸”到达实际走的距离已经是河宽的两倍。这个结果对第一次接触的人非常反直觉但它是完全正确的。这里有个记忆技巧不管 v船 比 v水 大还是小“最短位移”对应的那个角度公式长得像一对镜像。v船 v水 时 sinα v水/v船v船 v水 时 sinα v船/v水。其实就是把“谁在分母”换一下本质是让较强的那个速度充当斜边。2.4 三种问法对比表我把上面三种情况整理成一个表方便直接对照问法船头方向合速度方向过河时间实际路程最短时间垂直对岸斜向下游d / v船d × sqrt(1 (v水/v船)²)最短位移v船 v水偏上游sinα v水/v船严格垂直对岸d / sqrt(v船² - v水²)d最短位移v船 v水偏上游sinα v船/v水斜向下游d×v水 / (v船×sqrt(v水² - v船²))d×v水/v船用这个表之前永远先判断 v船 和 v水 谁大谁小。大小关系判断错了整个题就废了。2.5 常见翻车点把速度三角形画反最后讲一个我在批改里见了几百次的问题速度三角形画反。很多人画图习惯“先画水速再画合速度”这没问题。但一旦题目考最短位移他们就让合速度参加三角形合成画出来船头方向就错了。正确的画法是先用平行四边形或者矢量三角形把三个速度的关系画对。水速沿河向下游船头方向画船速船速与合速度共同决定实际轨迹。如果要求垂直过河合速度必须指向正对岸水速作为水平直角边船速作为斜边构成一个直角三角形。还有一类人求最短位移的时间时直接除以 v船。这等于默认船头正对岸时间当然会被低估。最短位移的代价就是船头偏了垂直速度分量变小时间必然比 d/v船 长这一点可以用上面的表格自行验证。3. 从物理题到逻辑题农夫过河为什么是状态搜索3.1 场景切换船还在但问题变成了“谁和谁不能单独待”如果说物理版小船过河看到的是连续轨迹那么逻辑版过河看到的是一系列离散状态。最经典的例子就是农夫过河农夫要带狼、羊、白菜从河左岸到右岸船每次只能载农夫和一样东西。狼会吃羊羊会吃白菜农夫不在场时绝对不能让它俩单独相处。我第一次给学生讲这个题时很多人直接懵住因为这里没有公式可以套只有规则。但换个角度看它其实就是一个带约束的状态搜索问题每一步之后两岸的物品组合都必须“安全”。所谓安全就是不出现狼羊同岸且农夫不在、羊菜同岸且农夫不在这两种情况。如果你静下心自己走一遍会发现最自然的正确步骤恰恰是那个七步解法。我把每一步列在下面方便你直接照着推演。3.2 七步解法最关键的“倒车”并不多余步骤农夫动作农夫位置左岸剩余物品右岸剩余物品0初始状态左狼、羊、菜、农夫无1带羊过河右狼、菜羊、农夫2农夫独自返回左狼、菜、农夫羊3带狼过河右菜狼、羊、农夫4带羊返回左菜、羊、农夫狼5带菜过河右羊狼、菜、农夫6农夫独自返回左羊、农夫狼、菜7带羊过河右无狼、羊、菜、农夫很多初学者不愿意走“带羊返回”那一步觉得这是在绕路。但正是这个倒车动作打破了“狼和羊已经在右岸”的危险局面。换句话说某些物品必须先运过去充当临时中转等到另一侧有了足够安全条件再回来把它接到最终位置。这是这类状态搜索题的核心思想最短路径不一定让每件东西都只被运一次有时需要回撤。3.3 农夫的位置才是最容易被忽略的状态变量如果你自己推演时发现某些步骤“怎么也算不通”大概率是忽略了农夫在船上的这个属性。狼羊菜问题里船不能自己动所有行动都必须有农夫随船。也就是说“农夫在左岸”和“农夫在右岸”是两个完全不同的状态必须写进状态定义里。有一种常见错误是这样的有人把状态只记录成“左岸物品集合”然后搜着搜着出现一个转移右岸的狼和羊没人管却假定安全。这就是因为没把农夫位置纳入状态导致非法转移被当作合法转移。只要记住一点——农夫在哪船就在哪——整个状态定义就完整了。如果把这个逻辑题写得更形式化状态就是一个二元组(左岸物品集合, 农夫所在岸)。初始状态是左岸包含狼羊菜农夫在左岸目标状态是左岸为空集农夫在右岸。每一次动作都从船所在侧选择空船或带一件物品前往对岸然后检查两岸是否安全。你看这不就天然变成了一个搜索问题。4. 把过河问题写进代码一个通用的 BFS 模板4.1 为什么是 BFS农夫过河问题换成代码来解几乎是 BFS广度优先搜索的标准教学案例。原因是所有动作花费的步数都一样过河一次算一步。BFS 从初始状态一层层向外扩展第一层到达目标时路径一定是最短步数。DFS 也能搜到解但它可能一条路走到黑找到的路径不一定最短。这种问题状态规模也很小左岸物品是狼羊菜三元素的子集再加上农夫位置总共只有 2 × 2³ 16 个状态。BFS 不会遇到性能压力代码逻辑反而最直观。状态少的时候暴力搜索就是最好的优雅。4.2 状态、动作与合法性检查代码的核心是三个部分状态表示、状态转移、安全校验。状态我习惯用一个元组表示(左岸物品集合, 农夫是否在左岸)。为了让状态可哈希、能放进 visited 集合左岸集合用 frozenset 而不是 set。动作是从农夫当前所在侧选一件物品带走或者空船独自返回。每一次转移后都要执行安全校验农夫不在的那一侧不能同时出现狼和羊也不能同时出现羊和菜。这里直接给一份完整可运行的 Python 代码核心模板都在里面from collections import deque ITEMS {wolf, sheep, cabbage} def is_safe(left_set, farmer_left): right_set set(ITEMS) - set(left_set) # 农夫不在的那一侧不能出现食物链组合 def side_ok(items, farmer_here): if farmer_here: return True return not ( (wolf in items and sheep in items) or (sheep in items and cabbage in items) ) return side_ok(left_set, farmer_left) and side_ok(right_set, not farmer_left) def next_states(state): left_set, farmer_left state # 船当前所在侧的全部物品 boat_items set(left_set) if farmer_left else set(ITEMS) - set(left_set) # 空船过河或者带其中一件过河 for load in [set()] [{item} for item in boat_items]: if farmer_left: new_left set(left_set) - load farmer False else: new_left set(left_set) | load farmer True if is_safe(new_left, farmer): yield (frozenset(new_left), farmer) def solve(): start (frozenset(ITEMS), True) # 农夫、狼、羊、菜都在左岸 target (frozenset(), False) # 农夫和所有物品都在右岸 q deque([(start, [])]) visited {start} while q: state, path q.popleft() if state target: return path for nxt in next_states(state): if nxt not in visited: visited.add(nxt) q.append((nxt, path [nxt]))运行这段程序得到的动作序列就是经典七步带羊过去、农夫独自回来、带狼过去、带羊回来、带菜过去、农夫独自回来、带羊过去。代码不会“思考”它只是把合法状态一层层展开直到碰到目标。4.3 这个模板能迁移到哪些场景很多人学算法喜欢套模板但真正有用的不是背模板而是会“翻译”。过河问题的 BFS 模板换一层皮就可以解决很多同类问题。比如传教士与野人过河三个传教士和三个野人过河船最多载两人任意一侧野人数量不能超过传教士数量。状态定义无非多一个变量安全规则换成“野人是否超过传教士”。再比如两个水壶倒水问题、八数码问题、华容道本质也都是状态搜索定义好状态、动作、合法性和目标判断然后用 BFS 或 A 星去搜。你只要熟悉一遍“小船过河”这种状态题再看这些题会感觉它们的骨架长得一模一样。如果状态空间变大比如物品数量从 3 变成 1016 个状态变成几千个BFS 仍然可解但可以把 visited 设计得更精细或者改用双向 BFS、A 星搜索来提速。更重要的是状态表示本身决定搜索效率写状态题的第一个动作永远是设计状态而不是写循环。5. 我在讲这道题时反复遇到的坑和积累的技巧5.1 画矢量图的第一笔决定了整道题的生死关于物理版本的小船过河我最深的体会是图形画对了题目就做对了一半。很多学生列不出公式不是公式没背而是不知道合速度该从哪里指向哪里。我建议画图时严格按这个顺序来先画水速方向沿河箭头标成 v水再从船头方向画船速最后把起点和终点连起来得到合速度。如果是求最短位移合速度方向必须是你希望船实际走的方向然后用几何关系反推船头方向。顺序一旦反了角度会跟着错后面全盘皆输。我在黑板上演示时喜欢用一支笔和一把尺把三个速度向量岔开画成胖三角形。等学生亲眼看到“水速不是跟船速直接抵消而是跟船速在河方向上的分量抵消”大多数错误都能当场消失。5.2 做题顺序建议先判大小再选公式还有一个经验值得刻在脑门上看到过河题先别急着套最短位移公式先看 v船 和 v水 谁大谁小。v船 v水可以垂直过河最短位移等于河宽 d。v船 v水理论极限合速度不能获得横向分量船只能沿着水流方向漂严格说无法过河。v船 v水不能垂直过河最短位移是 d×v水/v船且船头偏角用 sinα v船/v水。我见过不少人在 v船 v水 的题里硬套 d/sqrt(v船²-v水²)结果算出根号下负数或者算出一个比 d 还短的路程。碰到这种明显不合理的数字就该回头检查前提。5.3 如果“过河”出现在算法题里先分清是哪种过河不过如果你是在算法题里看到“过河”两个字还要多个心眼。算法题里的过河往往是另一种模型若干人夜晚过桥每次最多两人需要手电筒每个人速度不同求最短总时间。这就是经典的“n人过桥问题”和物理小船题、农夫状态题完全是两码事。举一个四人过桥的例子速度分别是 1、2、5、8 分钟。只用最快的人来回送总时间是 8 1 5 1 2 17 分钟。但更优的做法是让最快的两个先过最慢的两个一起过耗时 2 1 8 2 2 15 分钟。核心思路是最慢的两个人必须绑定在一起过桥这样能省一次慢速往返。这种问题不是 BFS而是一个贪心加动态规划的决策问题。所以碰到“过河”类题目我建议先自查三件事有哪些主体它们之间有没有互斥关系船/桥的运力是多少目标是最短时间还是找到一个合法路径这三件事搞清楚选对思路题基本就解了一半。最后再分享一个小习惯我做这类题时从不直接跳到公式或代码而是先手写一张小状态表把“谁在哪一边、下一步能做什么”写下来。看起来很笨但恰恰是这套方法帮我避开了大部分低级错误。小船过河问题之所以经典就是因为它用最少的元素逼你想清楚运动的合成、状态的约束和搜索的路径。想通这三件事再遇到它就不会只是背公式而是一种非常自然的推理过程。