经典问题重温——过桥问题！

herrrabbit

兔子引言：过桥问题，有的时候也理解成果和问题，在数学问题上最经典的当然还是过桥时间最短问题，怎么样能够尽快的过河。在我们研究这个经典问题之前先回顾一个过河问题的衍生，舒舒筋骨，也就是如何过河问题。

1.有一个农民带着一棵白菜，一只羊，一只狼去集市，途经一条小河，河里飘着一只小木船，限定了，每次从河的一段到达另一端的时候，农夫身边只能带着一个东西；问题是三个东西相互制约，没有农民在场，狼会吃羊，羊会吃白菜。问题的提出，如果选择过河方式？

2.有一座桥，桥中间有一个哨所，哨所每两个小时换班一次，一次幻般的时间是2分钟，而一个人过桥的时间是4分钟，两分钟以内人只可能走到哨所处；规定使人只可以从桥的一头走到另外一头，哨兵会认识过桥的人，也就是说人过了桥一次却不返回来走第二次；第二个前提是，哨兵每次看到人过桥都会告知这一情况，警告人们是否真的过桥，士兵警告后路人可以改变主意。请问如果一个人要第二次过桥怎么办？

当然上面所说得不过就是两个小游戏而已，答案大家也不用怎么费脑子得到，下面在废话之后进入正题，经典的过桥问题是这样提出的。


在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，四人所需要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这四人尽快过桥。



假设这四人分别为A、B、C、D。很明显，开始两人拿着手电筒过桥后，手电筒就在桥的另一边了，此时需要已经过桥的那两人中的一个再把手电筒送回桥这边。送手电筒回来过桥也要化时间，所以要选一个跑得比较快的。一个很自然的想法就是，每次让跑得最快的A陪着另一个过桥，然后A快速地跑回来，再陪下一位过去，最后所有人就都可以过桥了。



　　让我们来算一下这要多长时间。为了方便起见，我们把旅行者出发的桥的这一边称为“此岸”，而把旅行者想要到达的那边叫“彼岸”。在表达一个过桥方案时，我们用“←”来表示从彼岸到此岸的移动，用“→”表示从此岸到彼岸的移动。前面“A护送大家过河”的方案就可以写成：（右边数字为完成此步骤所需时间）




　　　　　　　　　　A　B　→　2

　　　　　　　　　　　 A　←　1

　　　　　　　　　　A　C　→　5

　　　　　　　　　　　 A　←　1

　　　　　　　　　　A　D　→　8



一共就是2+1+5+1+8=17分钟。



　　但其实有更快的办法：





　　　　　　　　　　A　B　→　2

　　　　　　　　　　　 A　←　1

　　　　　　　　　　C　D　→　8

　　　　　　　　　　　 B　←　2

　　　　　　　　　　A　B　→　2






一共是2+1+8+2+2=15分钟。这个办法的聪明之处在于让两个走得最慢的人同时过桥，这样花去的时间只是走得最慢的那个人花的时间，而走得次慢的那位就不用另花时间过桥了。可以把所有可能的方案都列举一遍，就会发现这是最快的方案了。



　　现在我们把这个问题推广到N(N≥4)个人过桥的情况：如果有N个旅行者，假设他们有各自所需的过桥时间（正实数）。在只有一只手电筒的情况下，要过上述的一条桥，怎样才能找到最快的过桥方案？



　　假设最快地把N个旅行者从此岸移动到彼岸需要f分钟时间，那么我们把所有在f分钟时间内把N个旅行者从此岸移动到彼岸的方案称为“最佳方案”。最佳方案很有可能不止一个，我们的目的是要找到一个最佳方案，但是并不需要把所有的最佳方案全都找出来。

herrrabbit

为了讨论的方便起见，这一节我们要说明的是，事实上我们可以假设每个旅行者的速度都是不一样的。这样当我们说一些人中“最快的那个”，“次慢的那一个”时，都不会有歧义了，因为每个人的速度都是独一无二的。这个假设在讨论中并非必要，只是为了在证明的叙述过程中避免不断地啰嗦类似“我们让两人中最快的那个过桥，如果两人一样快，那就随便选一人”、“我们选在彼岸最快的那个人回来，如果上一步刚从此岸到彼岸的人中，其中有一个是现在彼岸走得最快的之一，我们就特别选择让他回来”之类的话。



　　为什么我们可以假设每个旅行者的速度都是不一样的？原理就在于，我们可以把原来过桥时间相同的旅行者的过桥时间分别加上一个不同的但是非常非常小的量，这样就能保证旅行者的速度是不一样的了。但是因为加上去的量都非常小，所以对最终总的过桥时间的影响也非常小。所以这样改动过后得到的最佳方案在原来的条件下实施的话，也该是原来条件下的最佳方案。



　　如果你对上面的说明满意了，就完全可以跳过这一节直接看第三节。这一节后面啰哩叭嗦的都是为了向一些对严格性要求比较高的朋友解释上面所说的方法的确可行。



　　首先对于任何一组N个旅行者，假定他们过桥所需的时间分别为a1、a2、……、aN，它们都是大于零的实数。假设这个序列已经从小到大排列了（当然不排除其中有数相等）。每次都由第一个旅行者陪同一个人过桥，然后第一个旅行者回来，这样一个方案所需要的时间是：



　　　　S = (N-2)*a1+a2+……+an



（第一个旅行者要返回N-2次）。所以最佳方案所需要的时间一定不会比S大。



　　我们把一个过桥方案中让一个或者两个人拿着手电筒从桥的一边走到另一边的一次移动叫做这个方案中的一次移动或者“一步”，就是前面解四个人的题中使用“→”或“←”来表示的一个步骤。因为一次移动所需要的最少的时间是a1分钟，所以最佳方案中所需的移动步数一定不会多于K=[S/a1]步，这里"[]"是取整运算。



　　让我们考虑一下所有在K步以内完成的方案。上面的例子表明这样的方案至少有一个，而且这样的方案显然只有有限多个，假设一共有M个。我们又设这些方案执行时要花的时间是



　　　　t1、t2、……、tM



我们还可以假设上面这些时间已经从小到大排列了，t1就是最佳方案所需要的时间。



　　现在是关键的步骤。我们要选取一个很小的正实数ε＞0。它有多小呢？它必须满足下面的条件：



1) 对于任何两个过桥时间不同的旅行者（假设他们的过桥时间是a和b分钟），必须满足ε＜|a-b|/N。换句话说，Nε要小于不同的旅行者过桥时间之间的差别。



2) 对于任何两个所需的完成时间不同的K步以内的方案（假设它们的所需时间是t和s分钟），必须满足ε＜|t-s|/K。换句话说，Kε要小于不同的方案完成时间之间的差别。



因为旅行者的数目和方案的数目都是有限的，所以我们必然可以选取这样一个ε。至于这两个条件有什么用，我们马上就可以看到。



　　假设若干个旅行者过桥的时间都是一样的a分钟，我们就把题目改一下，使得他们的过桥时间分别为



　　　　a、a+ε/N、a+2ε/N、a+3ε/N……



如果有其他的旅行者过桥时间相互一样，也按照同样方式修改题目。这时在修改后的题目中，如果原来两个旅行者所需的过桥时间相同，那么现在就变得不同，差一个非常小的量（不会超过ε）；如果原来两个旅行者所需的过桥时间不同，那么根据上面的条件1)，现在还是不同，而且原来谁比较快，现在仍旧是他比较快。



　　我们看看这个修改后的题目的最佳方案和原来的题目的最佳方案有什么联系。



　　假设我们已经有一个关于修改后的题目的最佳方案，那么它所需要的时间必定是这个模样的：



　　　　a + bε



我们知道bε部分是修改时把旅行者过桥时间“微调”了以后造成的，而且每走一步这部分的改变不会超过ε，所以我们有0＜b＜K=[S/a1]。



　　如果我们把这个最佳移动方案照搬到原来的题目中去，所需要的时间就是a分钟。这个方案应该同样是原来题目中的最佳方案。否则的话，假设我们有另一个方案，所需时间为a'，而且a'＜a。根据上面取ε时候的条件2)，我们有



　　　　a' ＜ a + Kε



把这个耗时a'的方案搬到改动过的题目里去的话，所需的时间就会是



　　　　a' + b'ε



其中0＜b'＜K。所以根据a'＜a+Kε



　　　　a' + b'ε ＜ a + bε



这就和a+bε是改动后题目的最佳方案所需的时间矛盾了。



　　所以只要找到一个修改过的题目中的最佳方案，我们就得到了原来题目中的一个最佳方案，于是我们只要考虑所有旅行者的速度都不同的题目就可以了。

herrrabbit

编个计算机程序，把所有步数少于上一节中所计算的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) 如果被移动旅行者都不在此岸，那么情况要稍微复杂点。如果在第一种局面中经过这步移动后就变为完结局面，那么这意味着第二种局面中所有人早已到达彼岸，而这是不可能的，此时第二种局面中手电筒不可能在此岸。所以在第一种局面中经过这步移动后，还会有接下去的一步，把某个（或某两个）旅行者从彼岸移动到此岸。我们很容易看到，第二种局面无需任何耗费时间的移动，要优于第一种局面经过两次移动后演变得到的结果！因为经过两步移动后，第一种局面里在彼岸多出来的旅行者，在第二种局面里早已都在彼岸。



　　假设第一种局面的方案中的第一步是要把某个（或某两个）旅行者从彼岸移动到此岸（这时手电筒开始一定在彼岸），那么这就很简单，在第二种局面里这个（或这两个）旅行者一定也在彼岸，所以我们用相同的一步移动，花费一样的时间，把这个（或这两个）旅行者移动到此岸。这样得到的结果还是第二种局面要优于第一种局面。



　　于是总而言之，无论第一种局面中采取什么样的移动，我们总可以采取花费同样多的时间（甚至更少或者根本不花费时间）的移动，使得第二种局面或者变为和第一种局面相同，或者仍旧优于第一种局面。于是当第一种局面演变为完结局面时，第二种局面也一定演变为完结局面了，而花费的时间不会多于第一种局面所需的时间。



　　于是我们得到了很显然的结论：



结论一：如果有两种局面，第二种局面优于第一种局面，那么我们总可以用少于解决第一种局面的时间来解决第二种局面。



　　这说明“优于”这个词的使用是合理的。

herrrabbit

通过结论一我们立刻得到：



结论二：一定有这样一种最佳方案，在这个方案里，所有从彼岸到此岸的移动只需一个人。



　　如果最佳方案中有一步中需要两个人从彼岸移动到此岸，那么我们可以把这一步改为只移动比较快的那个人。在这一步后，我们花费了最多和原来相同的时间，得到的局面却优于按原先方案执行完这一步后的局面，所以剩下的解决步骤不会比原方案花费更多的时间，所以必定是个最佳方案。



　　现在我们知道，我们可以要求在最佳方案中，每次只回来一个人。在下面我们要得出另一个结论：



结论三：一定有这样一种符合结论二的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的。



　　假设在所有满足结论二的最佳方案中，都没有符合结论三的方案，也就是说，任何一个最佳方案中，总有某一步从彼岸到此岸的移动中，回来的那个人不是当时在彼岸所有人中速度最快的。那么我们在这些最佳方案中选取一个这样的“坏”步骤最晚出现的方案。假设这个步骤首先出现在第n步。



　　我们特别假设在这第n步中回来的这个人是B，他的过桥所需的时间为b分钟，而当时在彼岸所有人中速度最快的是A，他的过桥所需的时间为a分钟。现在我们开始把第n步“让B回来”改为“让A回来”。



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　　B ←　　　　　　　　　　A ←



现在两种局面的唯一区别在于，前一种是A在彼岸B在此岸，而后一种是B在彼岸A在此岸。但是前一种局面要比后一种局面多耗时b-a分钟。



　　在第n步后面接下去的移动步骤中，只要不牵涉A或B，那么可以在原来方案中进行的移动仍旧可以在改变了的方案中进行。而第n步后第一次牵涉到A或B的在原方案中的行动（我们假设它是第n+i步）只能是：



1) 把A从彼岸移动到此岸。此时我们在改造方案中的移动就是：把B从彼岸移动到此岸。这时局面就变成和原来的完全一样了，上一次由于用A来换B节省的b-a分钟也在这步中耗费掉了。接下去我们使用原方案完成其他移动。所以改造后的方案同样是个最佳方案：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　　B ←　　　　　　　　　　A ←

　　　　　　　　　……　　　　　　　　　　　……

　　第n+i步：　　　A ←　　　　　　　　　　B ←

　　　　　　　　　……　　　　　　　　　　　……



省略号部分表示此部分两个方案相同。



2) 把B从此岸移动到彼岸（可能还有另一个过桥时间为c分钟的C和他一起移动）。这就比较简单，第n+i步我们在改造后的方案中还是用A来代替B，然后局面就恢复到原来的情况，接下去我们使用原方案完成其他移动：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　　B ←　　　　　　　　　　A ←

　　　　　　　　　……　　　　　　　　　　　……

　　第n+i步：　B (C) →　　　　　　　　A (C) →

　　　　　　　　　……　　　　　　　　　　　……



这里括号内的C表示有可能另有旅行者C同行，省略号部分表示此部分两个方案相同。但我们发现这个移动所花费的时间一定要比原来的少：第n步修改后的方案就已经要比原方案耗时少，而第n+i步中，如果c比a和b都大的话，修改后的方案和原方案耗时相同；否则的话修改后的方案照样比原方案耗时少。所以我们得到了一个比“最佳方案”还要“佳”的方案，所以这种情况其实是不会发生的。



　　现在我们得到了一个修改过的方案，它仍旧是个最佳方案。虽然我们并不能保证它是满足结论三的方案，但是这并不是关键——关键在于它一直到第n步还是满足结论三的要求，这就和我们开始的假设，即被选取的这个方案是“这样的步骤最晚出现的方案”矛盾。所以我们的原先“假设在所有满足结论二的最佳方案中，都没有符合结论三的方案”是错误的。这样我们就得到了结论三。



　　在这里我要插一句题外话。上面的推理方法在数学中被称为“变分方法”，这是最重要的数学方法中的一种，我们可以在所有的数学分支中看见它的应用。它一般被用来证明存在一个具有某种特点的对象。首先我们选取一个使得某个特征（或者函数）达到最大或者最小的对象，然后用反证法证明这样的对象就是我们要找的对象：我们假设如果它不是我们要找的对象，那么我们总是还能把这个对象修改，使得这个特征（或者函数）更大或更小，这就和原来最大或最小的假设矛盾。



　　下面我们会不断地用到这种方法来得出许多结论：一定存在某一个最佳解法，符合如此这般的性质。一旦我们知道有一个最佳解法满足一些非常具体的性质以后，这个解法也就很容易被具体写出来了。



　　根据结论三我们立刻推出



结论四：一定有这样一种符合结论二—三的最佳方案，在这个方案里，每当出现手电筒在此岸的局面时，速度最快的那个人总是在此岸。



　　如果是初始局面，所有人都在此岸，当然没什么好说的。如果是手电筒在此岸的中间局面，那么根据结论三，前一步有一个彼岸最快的人刚过来。如果这个人不是所有人中最快的，那么说明最快的原来就已经在此岸了；如果这个人是所有人中最快的，那么他刚刚过来，现在也已经在此岸了。所以结论四成立。



　　如果在符合结论四的最佳方案方案中，有一步是只有一个人B从此岸走到彼岸，我们会有什么推论？如果在此岸另有一个A，他的速度比B快，那么A完全可以跟着B一起到彼岸去，这样就在耗费相同时间的情况下，得到了一个优于原先局面的局面，根据结论一，这也是最佳方案；如果B是此岸最快的，根据结论四，他也是所有人中最快的，过到彼岸后，根据结论三，他马上一个人又要回来，这就使这两步移动毫无意义，徒费时间。所以我们得到：



结论五：一定有这样一种符合结论二—四的最佳方案，在这个方案里，所有从此岸到彼岸的移动都需两个人。



　　下面我们要给出一个不那么显然的结论。



结论六：一定有这样一种符合结论二—五的最佳方案，在这个方案里，每次从此岸到彼岸移动两人，要么这两人里有一个是所有人中最快的那个，要么这两人到达彼岸后都再也不回来。



　　上面这个结论的意思是，在这个方案里不会出现这样的情况：有一步两个人跑到彼岸去，但两人都不是跑得最快的，但是后来其中一个（或者两个都）又跑回此岸来。



　　仍旧使用变分法。假设在所有满足结论二—五的最佳方案中，都没有符合结论六的方案，也就是说，其中的每个最佳方案，总都有某一步从此岸到彼岸的移动中，被移动的那两个人没有一个是最快的，而且其中一个在后面的步骤中又回到此岸来。那么我们在这些最佳方案中选取一个这样的步骤最晚出现的方案。假设这个步骤首先出现在第n步。



　　我们假设在这第n步中过去的两个人是Y和Z，他们过桥所需时间分别是y和z分钟，而在后面的第n+i步中，Y又回到此岸来了。设A是走得最快的那个人，过桥所需时间为a分钟。由结论四知道，他当时一定同Y和Z一起在此岸。



　　现在我们开始修改这个方案，把第n步“让Y和Z过去”改为“让A和Z过去”：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　Y Z →　　　　　　　　　　A Z →



如果y＜z，那么改过的步骤消耗的时间和原来的一样；如果z＜y，那么修改后的步骤消耗的时间还会更少。现在两种局面的唯一区别在于，前一种是A在此岸Y在彼岸，而后一种恰好相反。而且我们看到，经过这样修改的第n步现在符合“两人里有一个是所有人中最快的那个”这个结论六中的要求。剩下的工作就是要理顺后面的步骤，使得修改过的方案仍旧是一个最佳方案，那时我们就用变分法推出了矛盾，从而证明结论六。



　　下面我们的技巧和前面所用过的略微不同，我们要修改的不是一个移动而是一串移动。



　　假设原来的第n+1步是“让Y1回来”，其中Y1是在彼岸的某人，他是在彼岸最快的。我们把这第n+1步改为“让A回来”：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　Y Z →　　　　　　　　　　A Z →

　　第n+1步：　　 Y1 ←　　　　　　　　　　　A ←



这样修改后的步骤消耗的时间少于原先方案，因为Y1必定跑得比A慢。如果Y1恰好就是Y自己（也就是说i=1），那么从这步以后修改前后两种情况的局面又恢复成一样了。如果i≠1，也就是说Y1和Y不同，那么执行第n+1步后，原先的局面和修改过后的局面的唯一差别在于前一种是Y1在此岸Y在彼岸，而后一种恰好相反。我们注意到，根据结论三，Y1一定走得比Y快，更一般地，任何一个在n+1步到n+i步之间从彼岸回此岸来的人都比Y要走得快。



　　如果原先方案中从n+2步一直到n+i步里的移动都不牵涉到Y1，那么我们只要把第n+i步的“Y回来”改成“Y1回来”，就理顺了所有的步骤：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　Y Z →　　　　　　　　　　A Z →

　　第n+1步：　　 Y1 ←　　　　　　　　　　　A ←

　　　　　　　　　……　　　　　　　　　　　……

第n+i步：　　 Y ←　　　　　　　　　　　Y1 ←



修改后的步骤消耗的时间少于原先所需的，因为Y1走得比Y快。



　　如果不幸地在原先方案中的第n+j步(j＜i)Y1又要和某个人M一起到彼岸去，而第n+j+1步是“Y2回此岸来”，那么我们把第n+j步改为“A和M一起到彼岸”去，而把第n+k+1步改为“A回此岸来”：



　　　　　　　　原来的方案　　　　　　　修改后的方案

　　　　　　　　　……　　　　　　　　　　　……

　　　第n步：　　Y Z →　　　　　　　　　　A Z →

　　第n+1步：　　 Y1 ←　　　　　　　　　　　A ←

　　　　　　　　　……　　　　　　　　　　　……

　　第n+j步：　 Y1 M →　　　　　　　　　　A M →

　第n+j+1步：　　 Y2 ←　　　　　　　　　　　A ←



这样修改后的步骤消耗的时间也要比原先的少，因为A是最快的。如果Y2恰好就是Y自己（也就是说m=k+1），那么从这步以后修改前后两种情况的局面就恢复成一样了。如果m≠k+1，也就是说Y2和Y不同，那么执行第n+k+1步后，原先的局面和修改过后的局面的唯一差别在于前一种是Y2在此岸Y在彼岸，而后一种恰好相反。



　　这样我们有一个序列Y1，Y2，……，依次修改下去，每次修改后的步骤消耗的时间不会多于原先所需的，经过最多[m/2]次修改，总会有一刻某个Yt和Y相同，结束我们的这串修改。



　　这样我们就得到了修改后的最佳方案，它的第n步也是符合结论六的要求的。所以和我们的反证假设矛盾，和结论三的证明方式相同，我们证明了结论六。



　　在本节的结尾我们给出一个不那么显然的结论三的加强版。



结论七：一定有这样一种符合结论二—六的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的这个人一定是当时在彼岸所有人中速度最快的，而且他只能是所有人中最快的或者次快的。



　　换句话说，所有返回此岸的任务都可以只由跑得最快和跑得次快的人来担当，所有其他人一旦到达彼岸，就留在那里，再也不回来。



　　我们还是使用变分法。假设结论七是错的，所有（满足结论二—六的）最佳方案中，都必须至少有一次需要一个跑得不是最快或次快的人回来，那么我们选取一个这样的事情发生得最晚的最佳方案。假设在第n步，有一个C从彼岸跑回了此岸，但他不是跑得最快或次快的人。



　　我们假设A是跑得最快的人，他所需过桥时间为a分钟，B是跑得次快的人，他需要b分钟，而C需要c分钟。我们有a＜b＜c。因为在第n步C从彼岸跑回了此岸，所以在那之前一定有一步，C从此岸到达彼岸，而且根据结论六，那一步一定是A和C同行，我们假设此步为第n-i步。又根据结论三，接下去一步是A回到此岸。在第n-i步和第n步间，没有有关于C的移动。考虑第n-1步：根据结论五，这一步必定有两人从此岸移动到彼岸；这两人中没有A或B，否则根据结论三，第n步回此岸来的就该是比较快的A或B；另外这两人中也没有C，因为在在第n-i步和第n步间，C不移动。所以我们根据上面的分析可以写出方案中的有关步骤：

　　　　　　　　　原来的方案

　　　　　　　　　　……

　　第n-i步：　　　A C →

　第n-i+1步：　　　　A ←

　　　　　　　　　　……

　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、B或C）

　　　第n步：　　　　C ←

　　　　　　　　　　……



因为第n-i步和第n步之间没有关于C的移动，而第n-1步时A和B一定在此岸（否则根据结论三，第n步回此岸来的就该是比较快的A或B），所以我们可以把第n-i步和第n-i+1步移到第n-1步前，方案仍旧可以合理进行（换句话说，第n-i和第n-i+1步的唯一作用就是把C运送到了彼岸，但是直到第n步之前这个C并不起什么作用，所以我们可以把这次运送搬到第n-1步前而不影响其他步骤）：



　　　　　　　　修改后的方案

　　　　　　　　　　……　（原来第n-i步前的步骤）

　　　　　　　　　　……　（原来处于第n-i+1和第n步间的步骤）

　　第n-3步：　　　A C →　（原来第n-i步）

　　第n-2步：　　　　A ←　（原来第n-i+1步）

　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、B或C）

　　　第n步：　　　　C ←

　　　　　　　　　　……



现在有问题的步骤都聚在了一起，所以我们可以用B来代替C，进一步修改方案：



　　　　　　　进一步修改后的方案

　　　　　　　　　　……　（原来第n-i步前的步骤）

　　　　　　　　　　……　（原来处于第n-i+1和第n步间的步骤）

　　第n-3步：　　　A B →　

　　第n-2步：　　　　A ←　

　　第n-1步：　　　Y Z →　（Y和Z未知，但非A、B或C）

　　　第n步：　　　　B ←　　　　　　　　　　……



这个修改是可行的，因为根据上面的分析，进行第n-3步前B在此岸。这样得到的方案不但直到第n步还符合结论七，而且所需要的时间也比原方案短，明显违反了假设，所以我们得到矛盾，也就是说，满足结论七的最佳方案是存在的。于是结论七成立

herrrabbit

结论七是非常强大的，事实上它描述了除了最快和次快以外所有其他旅行者的过桥模式。任取一个满足结论七的最佳方案。



　　假设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返回”，称作“模式二”。



结论八：一定有这样一种符合结论二—七的最佳方案，在这个方案里，所有除了最快和次快的旅行者都以上面两个模式过桥，并且再不回来。

herrrabbit

现在我们来考虑走得最慢和走得次慢的人是如何过桥的。假设走得最慢的是Z，需时z；走得次慢的是Y，需时y。我们要证明：



结论九：所有符合结论八的最佳方案中，最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那么他们一定在一起过河。



　　特别地，无论他们以什么模式过河，我们总可以在开始的4步里将他们移动到彼岸。



1) 假设Z以模式一过河，但是Y却以模式二过河（步骤旁为此步所需时间）：



　　　　　　　　　　……

　　　　　　A Z →　　z

　　　　　　　A ←　　a

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　X Y →　　y　（X是另一不为A或B的旅行者，需时x）

　　　　　　　B ←　　b

　　　　　　　……



我们可以把X和Z对换，变成



　　　　　　　　　　……

　　　　　　A X →　　x　（X是另一不为A或B的旅行者，需时x）

　　　　　　　A ←　　a

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　Z Y →　　z

　　　　　　　B ←　　b

　　　　　　　……



这时修改过的方案比原先的耗时短y-x分钟，和原先的“最佳方案”假定矛盾。



2) 假设Z以模式二过河，但是Y却以模式一过河（步骤旁为此步所需时间）：



　　　　　　　　　　……

　　　　　　A Y →　　y

　　　　　　　A ←　　a

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　X Z →　　z　（X是另一不为A或B的旅行者，需时x）

　　　　　　　B ←　　b

　　　　　　　……



我们可以把X和Y对换，变成



　　　　　　　　　　……

　　　　　　A X →　　x　（X是另一不为A或B的旅行者，需时x）

　　　　　　　A ←　　a

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　Y Z →　　z

　　　　　　　B ←　　b

　　　　　　　……



这时修改过的方案比原先的耗时短y-x分钟，和原先的“最佳方案”假

定矛盾。



　　所以Z和Y必定用同一模式过河。假设他们都以模式二过河，却不在一起：



　　　　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　W Y →　　y　（W是另一不为A或B的旅行者，需时w）

　　　　　　　B ←　　b

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　X Z →　　z　（X是另一不为A或B的旅行者，需时x）

　　　　　　　B ←　　b

　　　　　　　……



我们可以把X和Y对换，变成



　　　　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　W X →　　t　（t是w和x中比较大的那一个）

　　　　　　　B ←　　b

　　　　　　　……

　　　　　　A B →　　b

　　　　　　　A ←　　a

　　　　　　Y Z →　　z

　　　　　　　B ←　　b

　　　　　　　……



这时修改过的方案比原先的耗时短y-t分钟（Y是跑得次慢的，所以y比w和t都要大），和原先的“最佳方案”假定矛盾。



　　于是最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那么他们一定在一起过河。现在我们来考虑在方案的前4步就将他们移动到彼岸。这非常简单。



　　如果两人都是以模式一过河：



　　　　　　　　　　……

　　　　　　　　　 A Z →　　z

　　　　　　　　　　 A ←　　a

　　　　　　　　　　……

　　　　　　　　　 A Y →　　y

　　　　　　　　　　 A ←　　a

　　　　　　　　　　……



我们可以把这几步挪到最开始而不改变其他步骤：



第1步：　　　　　　A Z →　　z

第2步：　　　　　　　A ←　　a

第3步：　　　　　　A Y →　　y

第4步：　　　　　　　A ←　　a

　　　　　　　　　　……



　　如果两人以模式二一起过河：



　　　　　　　　　　……

　　

herrrabbit

如果给定N个（速度不同）的旅行者，根据结论九我们知道有一个最佳方案，在最初的4步里用模式一或模式二把最慢的两个旅行者移动到彼岸，于是问题被约化成N-2个旅行者的形式。问题在于应该选择哪一种模式。继续假设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。



　　在第六节中我们发现使用模式一移动Z和Y到彼岸所需的时间为：



　　　　z + a + y + a



使用模式二移动Z和Y到彼岸所需的时间为：



　　　　b + a + z + b



所以，

　　　　当2b＞a+y时，应该使用模式一；

　　　　当2b＜a+y时，应该使用模式二；

　　　　当2b＝a+y时，使用模式一或二都可以。



　　上面的讨论都是在N≥4时进行的，那时最快、次快、最慢和次慢是四个不同的人。所以我们还要稍微讨论一下N=1、2、3的情况。



　　N=1、2是不用动脑子的，直接通通过桥就是了。



　　N=3也很简单，用穷举法可以发现由最快的人往返一次把其他两人送过河是最快的方法。



　　于是我们得到了最终结论：



最佳方案构造法：以下是构造N个人(N≥1)过桥最佳方案的方法：



　　1) 如果N=1、2，所有人直接过桥。

　　2) 如果N=3，由最快的人往返一次把其他两人送过河。

　　3) 如果N≥4，设A、B为走得最快和次快的旅行者，过桥所需时间分别为a、b；而Z、Y为走得最慢和次慢的旅行者，过桥所需时间分别为z、y。那么

　　　　当2b＞a+y时，使用模式一将Z和Y移动过桥；

　　　　当2b＜a+y时，使用模式二将Z和Y移动过桥；

　　　　当2b＝a+y时，使用模式一将Z和Y移动过桥。

这样就使问题转变为N-2个旅行者的情形，从而递归解决之。



　　最后当然我们要举一个具体的例子：七个旅行者，所需过桥时间分别是1、4、5、5、5、8、9分钟。



　　我们假设他们顺次为A、B、C、D、E、F、G，我们注意到C、D、E的速度一样，用第二节的方法太正规也太麻烦，我们可以人为规定C速度稍稍大于D，D速度又稍稍大于E。



采用结论十的方法，最快和次快的是A、B，时间为1和4；最慢和次慢的是G和F，时间为9和8。现在2*4＜1+9，所以用模式二：



第1步：　　　　　　A B →　　4

第2步：　　　　　　　A ←　　1

第3步：　　　　　　F G →　　9

第4步：　　　　　　　B ←　　4



现在剩下A、B、C、D、E在此岸，最快和次快的是A、B，时间为1和4；最慢和次慢的是E和D，时间为5和5。现在2*4＞1+5，所以用模式一：



第5步：　　　　　　A E →　　5

第6步：　　　　　　　A ←　　1

第7步：　　　　　　A D →　　5

第8步：　　　　　　　A ←　　1



现在剩下A、B、C在此岸，用N=3的办法结束：



第9步：　　　　　　A C →　　5

第10步：　　　　　　 A ←　　1

第11步：　　　　　 A B →　　4



总的时间为



　　　　4+1+9+4+5+1+5+1+5+1+4 = 40分钟



虽然我一个其他的方案都没列举，我知道这个40分钟的方案必定是最佳的。

apan

兔子，你不学info，是info界的损失啊。

herrrabbit

Originally posted by apan at 31-7-2005 20:27:
兔子，你不学info，是info界的损失啊。

有了你infor界就有了希望，两虎相争必有一伤的，再说了，我觉得机械也挺不错的，我会有所发展的！:D

郁闷的西葫芦

我以为是七桥问题  -_-;
最近眼神越来越差了