过桥与火把问题——4 人 17 分钟过桥的“让最慢两人同行”

大家好，我是 Senko。本文将解读面试谜题里的帝王“过桥与火把问题”。

夜里，四个人站在一座旧吊桥前。桥又暗又危险，过桥必须带火把，可火把只有一支。桥上同时最多只能过两人。四人脚程各异，过桥分别要 1 分、2 分、5 分、10 分，两人同行则要迁就慢的那位。那么，全员过完桥的最短时间是多少分钟？几乎所有人都答 19 分钟，正解却是 17 分钟。那 2 分钟的差里，藏着从根本上改变安排思路的一步棋。

过桥与火把问题是什么

过桥与火把问题（英语 bridge and torch problem），是把含有共享资源（火把）交接的移动安排最优化的谜题。先把规则整理一下。

四人在桥的同一侧，全员都想过到对面
过桥必须带火把。火把只有一支
桥上一次最多两人。两人同行的耗时是慢的那位的时间
四人耗时为 1 分、2 分、5 分、10 分。火把要由人带着走（禁止抛接）

这道谜题已知最早的铅字版本出自 1980 年代的谜题书，到 1990 年代因作为微软招聘面试出的题而闻名世界。据说当时面试会附上“已知 17 分钟能过完”的提示，许多候选人苦恼于“只能缩到 19 分钟，是不是题出错了”。以摇滚乐队 U2 的四名成员要在演唱会开始前 17 分钟内过桥为设定的段子在互联网上广泛流传，也很有名。

直觉的答案是“最快的 1 分接送全员”的 19 分钟

先看看几乎所有人最先想到的作战。带火把往返的角色，当然该让最快的 1 分那位来干——就是这个发想。

1 分和 10 分过桥（10 分）
1 分带火把返回（1 分）
1 分和 5 分过桥（5 分）
1 分返回（1 分）
1 分和 2 分过桥（2 分）

合计19 分钟。把最快的人固定为班车，慢的人一个一个运过去。看着哪儿都不浪费。事实上，在这个作战内部一秒也削不掉。

可一看合计的构成，弱点就浮出来了。10 分和 5 分这两个大数字，都整个儿地上了合计。只要把慢的人分开运，就逃不掉这两个数的加法。

正解是“让最慢的两人同行”的 17 分钟

正解的步骤是这样。

1 分和 2 分过桥（2 分）
1 分带火把返回（1 分）
10 分和 5 分过桥（10 分）
在对岸等着的 2 分带火把返回（2 分）
1 分和 2 分过桥（2 分）

合计 2＋1＋10＋2＋2，即17 分钟。

钥匙在第 3 步。把最慢的 10 分和 5 分放进同一趟，5 分就完全藏进 10 分的影子里，一点也不在合计上露脸。慢的两人分送要 10＋5 即 15 分，同送就只有 10 分。这里能整块省下 5 分。

不过这个作战需要事先做局。慢的两人过完之后，对岸得有人把火把带回来。让慢的两人带回来就前功尽弃了。所以第 1 步要先把快的两人送去对岸，预先安排好回程的司机（2 分）。第 1、2 步看着像白跑一趟，其实是为第 3 步那次大运输埋的伏笔。这种“为后一步先把人布置好”的组织法，我觉得与过河问题的“带着羊返回”并列，是安排类谜题的名手筋。

该不该让慢的两人同行，由加法决定

那么，让慢的两人同行的作战永远正确吗？其实不是。把四人的耗时按快到慢记作 a、b、c、d，两种作战的合计如下。

“最慢配对方式”：a＋3b＋d
“最快班车方式”：2a＋b＋c＋d

一减就知道，最慢配对方式取胜的条件是“2b 小于 a＋c”。也就是说，第二快的人足够快，就能担起回程司机，配对方式合算；第二快的人慢，那就保持班车方式更好。在 1、2、5、10 分里 2b 是 4，a＋c 是 6，所以配对方式胜。反过来比如 1、4、5、10 分，2b 是 8，a＋c 是 6，最快班车方式（合计 21 分）就胜过最慢配对方式（合计 23 分）。

哪种作战最优，会随参数翻盘。我觉得这一带是这道谜题更深一层的味道。它做成了“把‘这个手筋永远正确’背下来的瞬间就会被绊倒”的样子，也就难怪它被面试当题材宠爱了。另外已知人数增加时，“把快的两人当司机，把慢的两人成对送过去”这个手筋的反复也是基本形，一般情形的完整分析由数学家罗特在 2002 年的论文中给出。

瓶颈要并排藏起来

这道谜题的教训翻译成实务的话，就是“慢的处理要彼此叠着跑，别让它们各自排队”。

比如有一串作业含有两项耗时的处理：服务器重启与数据迁移、大型设备搬入与电源施工、耗时的审批与长交期零件的下单。按顺序做，耗时就是加法；同时跑起来，就只花慢的那一项。这就是项目管理里说的缩短关键路径，用做菜打比方，就是趁着炖的工夫把备菜做完的那个发想。

容易忽略的是，要实现并行，得为“埋伏笔的一手”先行投资。17 分钟的解里，第 1、2 步的 3 分就是这笔投资。只看眼前的 3 分，那是白跑，可正是它让后面省下 5 分成为可能。只评价每一步的效率，埋伏笔的那一步就会被当成“浪费”否掉，够不到全局最优。与过河问题相同的教训，在时间最优化这个不同的擂台上又露了面。

放到软件开发上，请想想那些跑起来很慢的测试组。把两组慢测试分别在各自的等待时间里跑，两份时间都得付；并行跑，就只花慢的那一份。为此多准备一套执行环境的功夫，就相当于“埋伏笔的 3 分钟”。搬家时把耗时的宽带施工与大件家具搬入安排在同一天，也是同一个发想。养成先问“最慢的是什么，它能和什么叠在一起”的习惯，各种等待时间就会开始缩短。

最短的证明，以及人数变多时

为什么让最快的人接送全员不是最优

最快班车方式的弱点，是慢的人的耗时会一份不落地全上合计。1 分那位往返确实最便宜，可一旦把 10 分和 5 分排进不同趟，15 分的账就定死了。最慢配对方式则多花 2 分那位一趟当回程司机的钱，换掉整块的 5 分。这是“运送角色的成本”与“把慢的人分送的成本”孰重孰轻的比较，答案随数字而变。

16 分钟过不去吗

过不去。首先 10 分那位所在的那一趟最少要 10 分。再者，为把火把送回来至少需要两趟回程，再快也是 1 分和 2 分（就算回程都由同一人跑也是 1 分＋1 分）。此外除最后一趟外还要再有一趟去程。把所有必需的趟次按最小组合数一遍，就能确认不存在低于 17 分的分配。作为谜题的答案，要 17 分步骤的存在性与 16 分以下的不可能性两样都齐了，才能断言“最短 17 分钟”，我觉得这一点也是很好的教材。

五人以上该怎么想

基本方针相同，候选是“把最快的两人固定为往返司机，其余按慢到快每两人一对送过去”的形态，以及它与最快班车的混合。每一轮比较“把最慢一对整体送过去的成本（a＋2b＋慢的那位）”与“用班车送两人的成本”，选便宜的那个，如此反复就能搭出最优解。人数增加，“让慢的彼此叠起来”的原理也不变，这正是这个手筋的漂亮之处。