摆渡过河和四人过桥

1.摆渡过河：一只狼、一头山羊和一箩卷心菜在河的同侧。一个摆渡人要将它们运过河去，但由于船小，他一次只能运三者之一过河。显然，不管是狼和山羊，还是山羊和卷心菜，都不能在无人监视的情况下留在一起。问摆渡人应怎样把它们运过河去？分析：由于摆渡人每次只能运载狼、山羊和卷心菜中的一样，那么必然有两样物品要同时留在岸上。但是狼和山羊，山羊和卷心菜之间分别存在捕食关系，不能同时留在岸上。所以摆渡人在第一次渡河时应先运羊过河，留狼和卷心菜在岸上；将羊放在对岸后，摆渡人空船返回。第二次渡河时运狼（或卷心菜），到达河对岸后放下狼（或卷心菜），将山羊运回。第三次渡河时将卷心菜（或狼）运到对岸，空船返回。第四次渡河时再将山羊运到对岸，即完成了渡河任务。2.四人过桥：有一天晚上，有四个人需要通过架在山谷间的危桥，任意时刻最多只能有两个人在桥上，过桥需要一盏闪光灯，这些人只有一盏闪光灯。如果单独过桥他们分别需要10、5、2、1分钟，如果两人同时过桥则所需时间是较慢者所需的时间。18分钟后，沿山谷滚滚而下的山洪将把这座桥冲毁。这四个人能及时过桥吗？不用图论知识，证明你的结论；并说明如何用图论知识获得答案。分析及证明：由于这座桥最多只能有两个人同时通过，并且过桥需要一盏闪光灯，但是四个人只有一盏闪光灯，那么唯一的办法就是让其中的2个人一起过桥，然后让其中的1个人再返回来送闪光灯。将四人按照其单独过桥时所花费时间由短到长编号为A、B、C、D。当两个人一起过桥时所花时间是两个人中最慢的人的单独过桥时间。无论谁和D一起过桥都要花费10分钟，为了尽量节省时间，D和C肯定需要一起过桥，并且不能由C或D回来送闪光灯。因此，首先应该让A和B先过桥（2分钟）；然后再让A回来送灯，让C和D过桥（1+10分钟）；最后让B回来，A和B一起过桥（2+2分钟）。总共用时是：2+1+10+2+2=17分钟＜18分钟，所以说这四个人在18分钟内能及时过桥。用图论知识说明：以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分钟，以此类推可以建立图论模型。要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出（空）节点到（1,2，5，10）节点间的最短路径。最后可用Dijkstra算法求出最短路径。

空集,0255222101丁5'21055521010分?5■1010)5.0510502,5210)510)2,10)空集,0255222101丁5'21055521010分?5■1010)5.0510