Science 版 (精华区)

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

过桥问题——经典智力题推而广之五 异调  　
三、一个“很显然”的结论　　编个计算机程序，把所有步数少于上一节中所计算的K=
[S/a1]的可能的过桥方案都列举一遍，然后找出最快的，当然是一种方法，这理论上也
是可行的，因为少于K步的方案只有有限多个，计算机程序必定能够将它们全部列举出来
。只是当人数N增大时，过桥方案数会增加得很快。事实上，如果我们只考虑“每次过去
两个人，然后这两个人中其中一个人回来”这类方案的数目的数量就已经远远超过N!个
了，想像一下如果N=1000的话所需要的计算量！况且还有更多数量的其他类型方案。特
别是，我们是在做智力题，不是在学编程。当然你还可以说，如果人多的话，所需要的
时间超过了12小时，那时天已经亮了，不再需要手电筒，大家可以直接过桥——唉！我
们是在做智力题，不是在做抬杠式的脑筋急转弯——我们可以假设是在有漫长极夜的极
地嘛，要不然，这桥是在一个黑暗山洞里，就象电影《指环王》中的那样……　　但是
如果不用列举法的话，我们有一个重要的任务要做，就是不仅要说明如何找到一个我们
自以为最快的方案，而且还要证明这样的方法的确给出了一个最佳方案。　　在我们的
直觉当中，最快的方案必然有这样一个特征：每次过桥去彼岸的一定是两个人，然后一
定只有一个人把手电筒送回此岸（当然要除去最后一次过桥的情况，那时就不需有人把
手电筒送回来了）。但是为什么一定是这样的呢？为什么不可能有一个意想不到的巧妙
方案，在那里有某一步居然需要一个人单独过到彼岸去，或者需要有两个人把手电筒送
回此岸来？这是个看起来很显而易见但是我们不能支吾不回答的问题。　　在讨论中我
们经常需要说明，在某一时刻，桥的两边分别有哪些人，手电筒又在哪一边。这样的说
明称为一个“局面”。当然，一个局面必须是合理的。比如说，不能够所有人都在桥的
一边，而手电筒却在桥的另一边；一个人必须处在桥的某一边，而且只能处在桥的某一
边。　　比如说，在四个旅行者的问题里，如果某一个时刻A、B和C在此岸，而D在彼岸
，手电筒也在彼岸，这就给出了一个局面（这个局面看起来有点奇怪，大概是D拿着手电
筒一个人跑过桥去了，接下去除了他再拿着手电筒回来别无它法）。所有人和手电筒都
在此岸，就是一个特殊的局面，叫作初始局面；而所有人和手电筒都在彼岸，也是一个
特殊的局面，叫完结局面；所有其他的局面我们称为中间局面。　　想像一下现在有两
种局面。在两种局面中，手电筒都在桥的同一边（都在此岸或都在彼岸）；而且在第一
种局面里所有在彼岸的旅行者，在第二种局面里也都在彼岸，而且有这样的旅行者，在
第一种局面中他在此岸，而第二种局面中他在彼岸。那么我们就说第二种局面“优于”
第一种局面。　　比如说，在四个旅行者的问题里，第一种局面是A、B和C在此岸，而D
在彼岸，手电筒也在彼岸；第二种局面是A和B在此岸，C和D在彼岸，手电筒也在彼岸。
那么第二种局面就优于第一种局面。很显然，除了初始局面以外，所有手电筒在此岸的
局面都优于初始局面；除了完结局面本身外，完结局面要优于所有手电筒在彼岸的局面
。但是要注意的是，并不是任意给两个局面都能比较哪个优于哪个，比如说初始局面和
完结局面，谁都不优于谁。　　如果现在有两个局面，第二种局面要优于第一种局面。
假设现在我已经有了一个方案，从第一种局面开始，通过符合题目要求的方法来移动旅
行者（最多只能同时移动两个旅行者，手电筒必须和他们一起移动），在t分钟内能够使
所有旅行者到达彼岸（也就是说转变成完结局面，或者说“解决”了这种局面），那么
我们可以保证我们同样也有了一个方案，从第二种局面开始，在不多于t分钟内使它转变
成完结局面。　　为什么呢？　　假设第一种局面的方案中的第一步是要把某个（或某
两个）旅行者从此岸移动到彼岸（这时手电筒开始一定在此岸）。1) 如果被移动的这个
（或这两个）旅行者，在第二种局面里也在此岸，那么我们同样把他们从此岸移动到彼
岸。这时两个局面化了同样多的时间转化成另两个局面，而且仍旧是第二种局面优于第
一种局面。（严格说来应该是“从第二种局面演化来的局面要优于从第一种局面演化来
的局面”，不过这样也太拗口了，所以在下面我都用前面那种虽然不严格但是比较简明
的方法来叙述。）2) 如果被移动的有两个旅行者，但是只有一个在第二种局面里是在此
岸，那么我们把他从此岸移动到彼岸。如果这个旅行者是两个中跑得比较快的，那么这
一步所化时间会比第一种局面要少；如果他是跑得比较慢的那个，那么这一步所化时间
就和第一种局面一样。而且经过这一步转化后，第二种局面或者和第一种局面一样，或
者仍旧优于第一种局面。3) 如果被移动旅行者都不在此岸，那么情况要稍微复杂点。如
果在第一种局面中经过这步移动后就变为完结局面，那么这意味着第二种局面中所有人
早已到达彼岸，而这是不可能的，此时第二种局面中手电筒不可能在此岸。所以在第一
种局面中经过这步移动后，还会有接下去的一步，把某个（或某两个）旅行者从彼岸移
动到此岸。我们很容易看到，第二种局面无需任何耗费时间的移动，要优于第一种局面
经过两次移动后演变得到的结果！因为经过两步移动后，第一种局面里在彼岸多出来的
旅行者，在第二种局面里早已都在彼岸。　　假设第一种局面的方案中的第一步是要把
某个（或某两个）旅行者从彼岸移动到此岸（这时手电筒开始一定在彼岸），那么这就
很简单，在第二种局面里这个（或这两个）旅行者一定也在彼岸，所以我们用相同的一
步移动，花费一样的时间，把这个（或这两个）旅行者移动到此岸。这样得到的结果还
是第二种局面要优于第一种局面。　　于是总而言之，无论第一种局面中采取什么样的
移动，我们总可以采取花费同样多的时间（甚至更少或者根本不花费时间）的移动，使
得第二种局面或者变为和第一种局面相同，或者仍旧优于第一种局面。于是当第一种局
面演变为完结局面时，第二种局面也一定演变为完结局面了，而花费的时间不会多于第
一种局面所需的时间。　　于是我们得到了很显然的结论：结论一：如果有两种局面，
第二种局面优于第一种局面，那么我们总可以用少于解决第一种局面的时间来解决第二
种局面。　　这说明“优于”这个词的使用是合理的。 
--
心事浩茫连广宇,于无声处听惊雷

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