Science 版 (精华区)

发信人: qpcwth (独翅鸟), 信区: Science
标  题: 过桥问题5
发信站: 哈工大紫丁香 (2002年04月14日22:32:09 星期天), 站内信件

过桥问题——经典智力题推而广之五 异调  　
五、过桥的模式　　结论七是非常强大的，事实上它描述了除了最快和次快以外所有其
他旅行者的过桥模式。任取一个满足结论七的最佳方案。　　假设A为最快，B为次快，
而Z是任意一个其他旅行者。根据结论七，他只过一次桥，然后就留在彼岸再不回来。考
虑一下和他同行的另一位旅行者，这里有两种可能性：1) 另一位旅行者还会回到此岸来
。那么根据结论六，另一位一定是A。所以Z过河的模式是这样的；　　　　　　　　　
　……　　　　　　　　　A Z →　　　　　　　　　　A ←　　　　　　　　　　…
…也就是“由A护送到对岸，A返回”，称作“模式一”。2) 另一位旅行者也不回来了。
假设这两位旅行者过桥是在第n步。　　如果方案一共就是到第n步结束，那么根据结论
四，在未执行第n步时，A应该在此岸，而在执行完第n步时，所有人都到了彼岸，所以那
另一个旅行者就是A。所以如果出现这种情况，Z过桥的模式实质上和1)中相同，“由A护
送到对岸”，只不过A不用再返回而已。　　如果方案中还有第n+1步，我们考虑一下第
n+1步是什么。根据结论七，这步应该是A或者B回到此岸。但是根据结论四，我们知道在
第n步时A在此岸，所以第n+1不步可能是A回来，所以只能是B回来。但是B在彼岸说明第
n步前已经有一步使得B过了桥。根据结论六和结论三，那一步一定是A和B同行，然后A回
来。我们就可以写出Z的过桥模式（设另一位旅行者是Y，他必不同于A和B）：　　　　
　　　　　　……　　　　　　　　　 A B →　　　　　　　　　　 A ←　　　　　
　　　　　……　　　第n步：　　　Y Z →　　第n+1步：　　　　B ←　　　　　　
　　　　……同结论七中的证明一样，我们可以修改这个方案为　　　　　　　　　　
……　　　　　　　　　　……　　第n-2步：　　　A B →　　　第n-1步：　　　　
A ←　　　　第n步：　　　Y Z →　　第n+1步：　　　　B ←　　　　　　　　　　
……看了这个方案片断大家也许会有似曾相识的感觉。事实上，这就是本文开始四位旅
行者问题中需时5分钟和8分钟的旅行者过桥的模式。这个模式是“由A和B护送到对岸，
A和B返回”，称作“模式二”。结论八：一定有这样一种符合结论二—七的最佳方案，
在这个方案里，所有除了最快和次快的旅行者都以上面两个模式过桥，并且再不回来。
  
--
心事浩茫连广宇,于无声处听惊雷

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.229.154]