微软过桥问题

U2合唱团在17分钟内得赶到演唱会场，途中必须跨过一座桥，4个人从桥的同一端出发，我们得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。4个人的步行速度各不同，若两人同行则以较慢者的速度为准。Bono需花1分钟过桥，Edge需花2分钟过桥，Adam需花5分钟过桥，Larry需花10分钟过桥。他们要如何在17分钟内过桥呢？

这个问题如果用图论来建模（基于系统状态转换模型），就可以以4个人在桥两端的状态来作为节点来构造一个有向图。以已经过桥了的人的状态作为图的节点，初始时没有人过桥，所以以空表示，第一轮有两个人过桥，有6种可能的组合，（1，2）（1，5）（1，10）（2，5）（2，10）（5，10），从空的状态转换到这些状态的需要的时间分别为2，5，10，5，10，10分钟，时间就作为有向边的权值。当有两个人过桥后，需要一个人拿手电筒回去接其他人，这时有四种可能的情况，分别是1，2，5，10中的一人留在了河的对岸，（1，2）这种状态只能转换到（1）（2）两种状态，对应的边的权值分别为2，1分钟，（1，2）转换到（1）时也就是2返回了，返回需要耗时2分钟，依此类推可以建立如图7-6所示的图论模型。

 

 

要求出最少需要多长时间4人全部通过小桥，实际上就是在图中求出（空）节点到（1，2，5，10）节点间的最短路径。根据Dijkstra最短路径算法很容易求出其最短路径：这样总时间为2＋1＋10＋2＋2＝17分钟。