图1
直接看TED Ed原汁原味的演讲，或者看下面我编写的文章，因为除了我理解视频主要内容，更加入了自己的一些体会和想法，还请各位老师和朋友多多指教和交流讨论。
视频1
一、僵尸被你释放出来了
你深山实验室实习，只是好奇心作祟，而拉下一个画着骷髅头的控制杆，结果放出来了囚禁在实验室里的一群僵尸。但现在可不是后悔的时候，因为你和你的同事们得赶紧摆脱这群夺门而出僵尸。
与你逃亡的还有：门卫、助理和老教授，一共4人。
图2
你们暂时甩开了僵尸，但前方只有一条路横跨大峡谷的吊桥。
图3
二、如果能及时过桥
你过桥需要1分钟，助理需要2分钟，门卫慢一点，需要5分钟教授需要整整10分钟，因为他每走一步都紧紧抓住绳索。
图4
教授计算出来仅仅在17分钟之后，僵尸就会追上你们，所以只有这么多时间让所有人过桥并剪断绳索。
图5
但问题是，吊桥只能承载2个人的重量，更糟糕的是已经是深夜一片漆黑，眼前伸手不见五指，而你们一路提着的只有一盏灯，仅仅也只能照亮面前的一小块地方。
图6
你能想出一个方案，让所有人及时逃脱吗？请记住下面解决过桥问题的要求：
1 吊桥每次只能承载最多2个人的重量；
2 任何人在桥上时必须提着灯，否则就掉落深渊；
3 任何人都可在峡谷两侧的黑暗中安全等待其他人；
4 最重要的是，所有人必须在僵尸到达之前安全通过吊桥，否则，当僵尸走上桥时，如果有人还在上面最后，桥可承受不了这重量。
5 这里不能使用任何花招——不能荡过去，不能把桥用作木筏，不能和僵尸做朋友。
如果你想尝试解决问题找出答案的话，请马上暂停往下翻。
图7
三、问题的答案
答案揭晓：起初似乎无论怎么安排都得超出1~2分钟，但可行的方案是存在的。
最关键的想法是缩短最慢的两个人所花费的时间，这可通过让他们一起过桥来实现。同时因为需要有人提着灯返回，所以必须让速度最快的人来完成这个任务。
图8（4人过桥所花费时间，用ABCD从左往右分别表示）
综上，首先助理(A)和你(B)提着灯快跑过桥，虽然你必须为她而放慢一点脚步，但2分钟后，你俩还都能过桥。然后速度最快的你花了1分钟提着灯跑回去，来回仅仅花了3分钟时间。
图9
目前为止，一切顺利。现在最耗时的部分来了，门卫(C)和教授(D)接过灯一起过桥，因为门卫必须为教授放慢脚步，所以这得用10分钟的时间。
图10
现在已经过去3+10=13分钟了。
现在僵尸只距离你4分钟的路程了，可你仍呆在危险的一侧，不过助理在另一侧已经等候多时了，她可是在四人中速度排名第二。
所以她从门卫手中接过灯，花2分钟跑过桥，回到你那侧的时候，时间只剩2分钟，刚好够你俩最后一并过桥的时间。
图11
当你一踏上峡谷的另一侧就立即剪断绳索，摧毁身后的吊桥，这样时间刚刚好过去17分钟。
图12
解决此类过桥问题的最佳方案，解决思路是必须安排最快的分到一组，最慢的分到一组，这样分类下来才会达到最优解。
或者可以将此类问题转成图论问题来解决，用 Dijkstra算法很容易求出其最短路径，感兴趣的朋友可以再考虑一下。
根据有关TED Ed视频及维基百科编写。完整视频与字幕，微信后台回复关键字[TED]得到国内云盘下载地址。更多TED Ed视频见下图或未来继续推出的文章。
图13
声明：文章转自【遇见数学】微信公众号，版权归原作者所有，转载仅供学习使用，不用于任何商业用途，如有侵权请联系删除，谢谢。
