“小船過河問題”這四個(gè)字我教了十多年也看著它從物理卷子一路爬到算法面試題里。很多人覺得它簡單可每次考場上總有人因?yàn)橐粋€(gè)方向角度多扣好多分。原因不是公式難背而是這個(gè)題考的從來不是算數(shù)而是兩個(gè)運(yùn)動(dòng)疊加在一起時(shí)你愿不愿意先把它們拆開再合并。這篇文章想把這道經(jīng)典題從物理、邏輯、算法三個(gè)層面完整拆一遍講清楚最短時(shí)間和最短位移為什么不是同一個(gè)解講清楚農(nóng)夫過河為什么本質(zhì)上是一張狀態(tài)圖再給出一套可以直接用代碼跑的搜索模板。備考的學(xué)生、輔導(dǎo)孩子的家長、刷題的工程師都能從里面對號(hào)入座。1. 先別急著劃船小船過河到底在問什么1.1 卷子上最常見的兩種問法如果你去翻一本高中物理練習(xí)冊最常見的過河題長這樣一條河寬為 d水流速度恒為 v水一艘船在靜水中的速度是 v船。然后題目分成兩種問法一種問“最短過河時(shí)間是多少”另一種問“船到達(dá)正對岸需要多長時(shí)間”。題干信息就這么多卻能延伸出完全不同的計(jì)算過程。我給學(xué)生上課時(shí)第一步永遠(yuǎn)是讓他們回答一個(gè)問題發(fā)動(dòng)機(jī)給你的速度是相對于水的速度還是相對于岸的速度答案是前者。船速 v船 是船相對水的速度它只由船頭指向決定水速 v水 是水相對岸的速度而船真正走過的軌跡是這兩個(gè)速度疊加出來的合速度。很多人題目沒做錯(cuò)但問他船實(shí)際朝哪開卻說不清就是這三個(gè)概念沒在腦子里立住。這道題真正的考點(diǎn)是“速度是矢量”。既然是矢量就不能像小學(xué)算術(shù)一樣直接相減相加必須先定方向再按平行四邊形法則合成。只要你把“船速、水速、合速度”三個(gè)量放對位置剩下全是初中幾何。1.2 跑步機(jī)類比把抽象概念一次性說透我用一個(gè)生活類比來解釋速度合成效果一直很好。想象你站在商場里的跑步機(jī)上跑步機(jī)以每秒 1 米向后滾動(dòng)你以每秒 2 米的速度向前跑。對旁邊的人來說你實(shí)際上是以每秒 1 米的速度前進(jìn)而不是每秒 3 米也不是每秒 2 米。如果這時(shí)候你要去跑步機(jī)正前方的一杯水你得微調(diào)跑步方向不能完全順著跑步機(jī)方向走。小船過河一模一樣水速相當(dāng)于跑步機(jī)船速相當(dāng)于你的跑步能力而“實(shí)際軌跡”是這兩個(gè)速度共同作用的結(jié)果。這個(gè)類比的另一個(gè)好處是能直觀解釋“為什么船頭直指對岸時(shí)時(shí)間最短”。在跑步機(jī)上如果你想到達(dá)正前方某個(gè)點(diǎn)最好的辦法不是側(cè)著跑而是先加速往前跑再修正方向。但如果你只關(guān)心“從這頭到那頭時(shí)間最少”跑步機(jī)能不能把你帶偏根本不重要你只要朝目標(biāo)方向全力跑就行。對應(yīng)的物理結(jié)論是船頭垂直指向?qū)Π稌r(shí)船在橫渡方向上的速度分量最大時(shí)間自然最短。1.3 所有過河問題共享的骨架不管題目怎么變形背后只有三條規(guī)則把船速分解成“垂直于岸”和“平行于岸”兩個(gè)方向垂直于岸的分速度決定過河時(shí)間也就是 t d / v垂直平行于岸的分速度疊加水速后決定船實(shí)際到達(dá)的位置。這三條規(guī)則聽起來平淡卻是整道題的骨架。最短時(shí)間、最短位移、最小路程、以及你以后可能在算法題里見到的各類“過河變體”本質(zhì)上都是這三句話在不同條件下的推演。想通這一點(diǎn)你就不會(huì)覺得它是一個(gè)孤立公式而是一套可以復(fù)用的分析方法。2. 最短時(shí)間、最短位移、最短航程三種經(jīng)典問法的推導(dǎo)與陷阱2.1 最短時(shí)間船頭對準(zhǔn)對岸但人確實(shí)“漂”下去了先看最短時(shí)間。要讓橫渡時(shí)間最短就得讓垂直于岸的方向速度分量最大。船速大小固定什么時(shí)候分量最大當(dāng)然是船頭完全垂直于岸的時(shí)候此時(shí)垂直分速度就是 v船。于是最短時(shí)間t_min d / v船這段時(shí)間里水會(huì)把人往下游沖多遠(yuǎn)Δx v水 × t_min v水 × d / v船很多人做完第一問就順手填了“終點(diǎn)在正對岸”這是不對的。船在水流里走了斜線它確實(shí)是最快到達(dá)對岸的方案但到達(dá)點(diǎn)一定偏向下游。要記住一個(gè)反直覺的結(jié)論最短時(shí)間不等同于最短位移想要快就別管漂不漂想要準(zhǔn)就得犧牲速度。這個(gè)問題的陷阱還在于經(jīng)常有人問“最短時(shí)間內(nèi)到底沿什么方向開”。方向就是垂直岸開沒有第二個(gè)答案。有些同學(xué)試圖“稍微偏上游一點(diǎn)好讓落點(diǎn)不那么偏”結(jié)果垂直分量變小時(shí)間反而變長。方向一動(dòng)時(shí)間就長這是這類題最容易踩的坑。2.2 最短位移當(dāng)船速大于水速船頭必須“斜著搶”再看最短位移也就是讓船實(shí)際到達(dá)對岸正對的位置。這種情況下船頭不能再直指對岸了必須斜向上游用船速的一個(gè)分量去抵消水速。設(shè)船頭與垂直岸方向的夾角為 α則沿河方向v船 sinα 抵消 v水于是 sinα v水 / v船垂直岸方向的分速度v船 cosα sqrt(v船2 - v水2)過河時(shí)間t d / sqrt(v船2 - v水2)這里的幾何關(guān)系很漂亮水速是直角邊船速是斜邊合速度是另一直角邊。合速度必須嚴(yán)格垂直于岸船實(shí)際軌跡才是直線正對岸。有人把合速度理解成 v船 - v水那就犯了把矢量當(dāng)標(biāo)量的錯(cuò)誤。垂直與抵消是完全不同的兩個(gè)方向只能走勾股定理。還需要注意一個(gè)條件這個(gè)解法要求 v船 v水。如果船速和水速一樣大即使船頭完全逆著水流方向開到極限也剛剛能保證不往下游漂垂直方向分速度已經(jīng)變成 0船根本過不了河。所以 v船 v水 是“垂直正對岸過河”的硬門檻。2.3 船速小于水速最短位移不是垂直而是斜向下游當(dāng) v船 v水 時(shí)垂直過河已經(jīng)不可能船必然會(huì)被沖向下游。那題目如果還問“最短位移”要怎么理解就是要讓實(shí)際軌跡偏離正對岸的角度最小也就是在不可避免的漂移里挑一個(gè)最小的。這時(shí)的幾何結(jié)論非常漂亮讓船頭斜向上游并使得船速與合速度垂直偏距最小。具體公式船頭偏向上游且 sinα v船 / v水實(shí)際路徑與垂直岸方向的夾角 β 滿足 tanβ sqrt(v水2 - v船2) / v船最短實(shí)際路程 d × v水 / v船過河時(shí)間 d × v水 / (v船 × sqrt(v水2 - v船2))我拿一個(gè)典型數(shù)值舉例河寬 100 米水速 4 m/s船速 2 m/s。按公式最短路程是 100 × 4 / 2 200 米過河時(shí)間約 57.7 秒。也就是說船速只有水速一半時(shí)你想“盡可能正對岸”到達(dá)實(shí)際走的距離已經(jīng)是河寬的兩倍。這個(gè)結(jié)果對第一次接觸的人非常反直覺但它是完全正確的。這里有個(gè)記憶技巧不管 v船 比 v水 大還是小“最短位移”對應(yīng)的那個(gè)角度公式長得像一對鏡像。v船 v水 時(shí) sinα v水/v船v船 v水 時(shí) sinα v船/v水。其實(shí)就是把“誰在分母”換一下本質(zhì)是讓較強(qiáng)的那個(gè)速度充當(dāng)斜邊。2.4 三種問法對比表我把上面三種情況整理成一個(gè)表方便直接對照問法船頭方向合速度方向過河時(shí)間實(shí)際路程最短時(shí)間垂直對岸斜向下游d / v船d × sqrt(1 (v水/v船)2)最短位移v船 v水偏上游sinα v水/v船嚴(yán)格垂直對岸d / sqrt(v船2 - v水2)d最短位移v船 v水偏上游sinα v船/v水斜向下游d×v水 / (v船×sqrt(v水2 - v船2))d×v水/v船用這個(gè)表之前永遠(yuǎn)先判斷 v船 和 v水 誰大誰小。大小關(guān)系判斷錯(cuò)了整個(gè)題就廢了。2.5 常見翻車點(diǎn)把速度三角形畫反最后講一個(gè)我在批改里見了幾百次的問題速度三角形畫反。很多人畫圖習(xí)慣“先畫水速再畫合速度”這沒問題。但一旦題目考最短位移他們就讓合速度參加三角形合成畫出來船頭方向就錯(cuò)了。正確的畫法是先用平行四邊形或者矢量三角形把三個(gè)速度的關(guān)系畫對。水速沿河向下游船頭方向畫船速船速與合速度共同決定實(shí)際軌跡。如果要求垂直過河合速度必須指向正對岸水速作為水平直角邊船速作為斜邊構(gòu)成一個(gè)直角三角形。還有一類人求最短位移的時(shí)間時(shí)直接除以 v船。這等于默認(rèn)船頭正對岸時(shí)間當(dāng)然會(huì)被低估。最短位移的代價(jià)就是船頭偏了垂直速度分量變小時(shí)間必然比 d/v船 長這一點(diǎn)可以用上面的表格自行驗(yàn)證。3. 從物理題到邏輯題農(nóng)夫過河為什么是狀態(tài)搜索3.1 場景切換船還在但問題變成了“誰和誰不能單獨(dú)待”如果說物理版小船過河看到的是連續(xù)軌跡那么邏輯版過河看到的是一系列離散狀態(tài)。最經(jīng)典的例子就是農(nóng)夫過河農(nóng)夫要帶狼、羊、白菜從河左岸到右岸船每次只能載農(nóng)夫和一樣?xùn)|西。狼會(huì)吃羊羊會(huì)吃白菜農(nóng)夫不在場時(shí)絕對不能讓它倆單獨(dú)相處。我第一次給學(xué)生講這個(gè)題時(shí)很多人直接懵住因?yàn)檫@里沒有公式可以套只有規(guī)則。但換個(gè)角度看它其實(shí)就是一個(gè)帶約束的狀態(tài)搜索問題每一步之后兩岸的物品組合都必須“安全”。所謂安全就是不出現(xiàn)狼羊同岸且農(nóng)夫不在、羊菜同岸且農(nóng)夫不在這兩種情況。如果你靜下心自己走一遍會(huì)發(fā)現(xiàn)最自然的正確步驟恰恰是那個(gè)七步解法。我把每一步列在下面方便你直接照著推演。3.2 七步解法最關(guān)鍵的“倒車”并不多余步驟農(nóng)夫動(dòng)作農(nóng)夫位置左岸剩余物品右岸剩余物品0初始狀態(tài)左狼、羊、菜、農(nóng)夫無1帶羊過河右狼、菜羊、農(nóng)夫2農(nóng)夫獨(dú)自返回左狼、菜、農(nóng)夫羊3帶狼過河右菜狼、羊、農(nóng)夫4帶羊返回左菜、羊、農(nóng)夫狼5帶菜過河右羊狼、菜、農(nóng)夫6農(nóng)夫獨(dú)自返回左羊、農(nóng)夫狼、菜7帶羊過河右無狼、羊、菜、農(nóng)夫很多初學(xué)者不愿意走“帶羊返回”那一步覺得這是在繞路。但正是這個(gè)倒車動(dòng)作打破了“狼和羊已經(jīng)在右岸”的危險(xiǎn)局面。換句話說某些物品必須先運(yùn)過去充當(dāng)臨時(shí)中轉(zhuǎn)等到另一側(cè)有了足夠安全條件再回來把它接到最終位置。這是這類狀態(tài)搜索題的核心思想最短路徑不一定讓每件東西都只被運(yùn)一次有時(shí)需要回撤。3.3 農(nóng)夫的位置才是最容易被忽略的狀態(tài)變量如果你自己推演時(shí)發(fā)現(xiàn)某些步驟“怎么也算不通”大概率是忽略了農(nóng)夫在船上的這個(gè)屬性。狼羊菜問題里船不能自己動(dòng)所有行動(dòng)都必須有農(nóng)夫隨船。也就是說“農(nóng)夫在左岸”和“農(nóng)夫在右岸”是兩個(gè)完全不同的狀態(tài)必須寫進(jìn)狀態(tài)定義里。有一種常見錯(cuò)誤是這樣的有人把狀態(tài)只記錄成“左岸物品集合”然后搜著搜著出現(xiàn)一個(gè)轉(zhuǎn)移右岸的狼和羊沒人管卻假定安全。這就是因?yàn)闆]把農(nóng)夫位置納入狀態(tài)導(dǎo)致非法轉(zhuǎn)移被當(dāng)作合法轉(zhuǎn)移。只要記住一點(diǎn)——農(nóng)夫在哪船就在哪——整個(gè)狀態(tài)定義就完整了。如果把這個(gè)邏輯題寫得更形式化狀態(tài)就是一個(gè)二元組(左岸物品集合, 農(nóng)夫所在岸)。初始狀態(tài)是左岸包含狼羊菜農(nóng)夫在左岸目標(biāo)狀態(tài)是左岸為空集農(nóng)夫在右岸。每一次動(dòng)作都從船所在側(cè)選擇空船或帶一件物品前往對岸然后檢查兩岸是否安全。你看這不就天然變成了一個(gè)搜索問題。4. 把過河問題寫進(jìn)代碼一個(gè)通用的 BFS 模板4.1 為什么是 BFS農(nóng)夫過河問題換成代碼來解幾乎是 BFS廣度優(yōu)先搜索的標(biāo)準(zhǔn)教學(xué)案例。原因是所有動(dòng)作花費(fèi)的步數(shù)都一樣過河一次算一步。BFS 從初始狀態(tài)一層層向外擴(kuò)展第一層到達(dá)目標(biāo)時(shí)路徑一定是最短步數(shù)。DFS 也能搜到解但它可能一條路走到黑找到的路徑不一定最短。這種問題狀態(tài)規(guī)模也很小左岸物品是狼羊菜三元素的子集再加上農(nóng)夫位置總共只有 2 × 23 16 個(gè)狀態(tài)。BFS 不會(huì)遇到性能壓力代碼邏輯反而最直觀。狀態(tài)少的時(shí)候暴力搜索就是最好的優(yōu)雅。4.2 狀態(tài)、動(dòng)作與合法性檢查代碼的核心是三個(gè)部分狀態(tài)表示、狀態(tài)轉(zhuǎn)移、安全校驗(yàn)。狀態(tài)我習(xí)慣用一個(gè)元組表示(左岸物品集合, 農(nóng)夫是否在左岸)。為了讓狀態(tài)可哈希、能放進(jìn) visited 集合左岸集合用 frozenset 而不是 set。動(dòng)作是從農(nóng)夫當(dāng)前所在側(cè)選一件物品帶走或者空船獨(dú)自返回。每一次轉(zhuǎn)移后都要執(zhí)行安全校驗(yàn)農(nóng)夫不在的那一側(cè)不能同時(shí)出現(xiàn)狼和羊也不能同時(shí)出現(xiàn)羊和菜。這里直接給一份完整可運(yùn)行的 Python 代碼核心模板都在里面from collections import deque ITEMS {wolf, sheep, cabbage} def is_safe(left_set, farmer_left): right_set set(ITEMS) - set(left_set) # 農(nóng)夫不在的那一側(cè)不能出現(xiàn)食物鏈組合 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 # 船當(dāng)前所在側(cè)的全部物品 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) # 農(nóng)夫、狼、羊、菜都在左岸 target (frozenset(), False) # 農(nóng)夫和所有物品都在右岸 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]))運(yùn)行這段程序得到的動(dòng)作序列就是經(jīng)典七步帶羊過去、農(nóng)夫獨(dú)自回來、帶狼過去、帶羊回來、帶菜過去、農(nóng)夫獨(dú)自回來、帶羊過去。代碼不會(huì)“思考”它只是把合法狀態(tài)一層層展開直到碰到目標(biāo)。4.3 這個(gè)模板能遷移到哪些場景很多人學(xué)算法喜歡套模板但真正有用的不是背模板而是會(huì)“翻譯”。過河問題的 BFS 模板換一層皮就可以解決很多同類問題。比如傳教士與野人過河三個(gè)傳教士和三個(gè)野人過河船最多載兩人任意一側(cè)野人數(shù)量不能超過傳教士數(shù)量。狀態(tài)定義無非多一個(gè)變量安全規(guī)則換成“野人是否超過傳教士”。再比如兩個(gè)水壺倒水問題、八數(shù)碼問題、華容道本質(zhì)也都是狀態(tài)搜索定義好狀態(tài)、動(dòng)作、合法性和目標(biāo)判斷然后用 BFS 或 A 星去搜。你只要熟悉一遍“小船過河”這種狀態(tài)題再看這些題會(huì)感覺它們的骨架長得一模一樣。如果狀態(tài)空間變大比如物品數(shù)量從 3 變成 1016 個(gè)狀態(tài)變成幾千個(gè)BFS 仍然可解但可以把 visited 設(shè)計(jì)得更精細(xì)或者改用雙向 BFS、A 星搜索來提速。更重要的是狀態(tài)表示本身決定搜索效率寫狀態(tài)題的第一個(gè)動(dòng)作永遠(yuǎn)是設(shè)計(jì)狀態(tài)而不是寫循環(huán)。5. 我在講這道題時(shí)反復(fù)遇到的坑和積累的技巧5.1 畫矢量圖的第一筆決定了整道題的生死關(guān)于物理版本的小船過河我最深的體會(huì)是圖形畫對了題目就做對了一半。很多學(xué)生列不出公式不是公式?jīng)]背而是不知道合速度該從哪里指向哪里。我建議畫圖時(shí)嚴(yán)格按這個(gè)順序來先畫水速方向沿河箭頭標(biāo)成 v水再從船頭方向畫船速最后把起點(diǎn)和終點(diǎn)連起來得到合速度。如果是求最短位移合速度方向必須是你希望船實(shí)際走的方向然后用幾何關(guān)系反推船頭方向。順序一旦反了角度會(huì)跟著錯(cuò)后面全盤皆輸。我在黑板上演示時(shí)喜歡用一支筆和一把尺把三個(gè)速度向量岔開畫成胖三角形。等學(xué)生親眼看到“水速不是跟船速直接抵消而是跟船速在河方向上的分量抵消”大多數(shù)錯(cuò)誤都能當(dāng)場消失。5.2 做題順序建議先判大小再選公式還有一個(gè)經(jīng)驗(yàn)值得刻在腦門上看到過河題先別急著套最短位移公式先看 v船 和 v水 誰大誰小。v船 v水可以垂直過河最短位移等于河寬 d。v船 v水理論極限合速度不能獲得橫向分量船只能沿著水流方向漂嚴(yán)格說無法過河。v船 v水不能垂直過河最短位移是 d×v水/v船且船頭偏角用 sinα v船/v水。我見過不少人在 v船 v水 的題里硬套 d/sqrt(v船2-v水2)結(jié)果算出根號(hào)下負(fù)數(shù)或者算出一個(gè)比 d 還短的路程。碰到這種明顯不合理的數(shù)字就該回頭檢查前提。5.3 如果“過河”出現(xiàn)在算法題里先分清是哪種過河不過如果你是在算法題里看到“過河”兩個(gè)字還要多個(gè)心眼。算法題里的過河往往是另一種模型若干人夜晚過橋每次最多兩人需要手電筒每個(gè)人速度不同求最短總時(shí)間。這就是經(jīng)典的“n人過橋問題”和物理小船題、農(nóng)夫狀態(tài)題完全是兩碼事。舉一個(gè)四人過橋的例子速度分別是 1、2、5、8 分鐘。只用最快的人來回送總時(shí)間是 8 1 5 1 2 17 分鐘。但更優(yōu)的做法是讓最快的兩個(gè)先過最慢的兩個(gè)一起過耗時(shí) 2 1 8 2 2 15 分鐘。核心思路是最慢的兩個(gè)人必須綁定在一起過橋這樣能省一次慢速往返。這種問題不是 BFS而是一個(gè)貪心加動(dòng)態(tài)規(guī)劃的決策問題。所以碰到“過河”類題目我建議先自查三件事有哪些主體它們之間有沒有互斥關(guān)系船/橋的運(yùn)力是多少目標(biāo)是最短時(shí)間還是找到一個(gè)合法路徑這三件事搞清楚選對思路題基本就解了一半。最后再分享一個(gè)小習(xí)慣我做這類題時(shí)從不直接跳到公式或代碼而是先手寫一張小狀態(tài)表把“誰在哪一邊、下一步能做什么”寫下來。看起來很笨但恰恰是這套方法幫我避開了大部分低級(jí)錯(cuò)誤。小船過河問題之所以經(jīng)典就是因?yàn)樗米钌俚脑乇颇阆肭宄\(yùn)動(dòng)的合成、狀態(tài)的約束和搜索的路徑。想通這三件事再遇到它就不會(huì)只是背公式而是一種非常自然的推理過程。