过桥问题.docx
- 文档编号:570208
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:23
- 大小:28.10KB
过桥问题.docx
《过桥问题.docx》由会员分享,可在线阅读,更多相关《过桥问题.docx(23页珍藏版)》请在冰点文库上搜索。
过桥问题
过桥问题--经典智力题
一、问题
在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。
如果不借助手电筒的话,大家是无论如何也不敢过桥去的。
不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时过。
如果各自单独过桥的话,四人所需要的时间分别是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个旅行者从此岸移动到彼岸的方案称为“最佳方案”。
最佳方案很有可能不止一个,我们的目的是要找到一个最佳方案,但是并不需要把所有的最佳方案全都找出来。
二、一个合理的假设
为了讨论的方便起见,这一节我们要说明的是,事实上我们可以假设每个旅行者的速度都是不一样的。
这样当我们说一些人中“最快的那个”,“次慢的那一个”时,都不会有歧义了,因为每个人的速度都是独一无二的。
这个假设在讨论中并非必要,只是为了在证明的叙述过程中避免不断地啰嗦类似“我们让两人中最快的那个过桥,如果两人一样快,那就随便选一人”、“我们选在彼岸最快的那个人回来,如果上一步刚从此岸到彼岸的人中,其中有一个是现在彼岸走得最快的之一,我们就特别选择让他回来”之类的话。
为什么我们可以假设每个旅行者的速度都是不一样的?
原理就在于,我们可以把原来过桥时间相同的旅行者的过桥时间分别加上一个不同的但是非常非常小的量,这样就能保证旅行者的速度是不一样的了。
但是因为加上去的量都非常小,所以对最终总的过桥时间的影响也非常小。
所以这样改动过后得到的最佳方案在原来的条件下实施的话,也该是原来条件下的最佳方案。
如果你对上面的说明满意了,就完全可以跳过这一节直接看第三节。
这一节后面啰哩叭嗦的都是为了向一些对严格性要求比较高的朋友解释上面所说的方法的确可行。
首先对于任何一组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ε是改动后题目的最佳方案所需的时间矛盾了。
所以只要找到一个修改过的题目中的最佳方案,我们就得到了原来题目中的一个最佳方案,于是我们只要考虑所有旅行者的速度都不同的题目就可以了。
三、一个“很显然”的结论
编个计算机程序,把所有步数少于上一节中所计算的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)如果被移动旅行者都不在此岸,那么情况要稍微复杂点。
如果在第一种局面中经过这步移动后就变为完结局面,那么这意味着第二种局面中所有人早已到达彼岸,而这是不可能的,此时第二种局面中手电筒不可能在此岸。
所以在第一种局面中经过这步移动后,还会有接下去的一步,把某个(或某两个)旅行者从彼岸移动到此岸。
我们很容易看到,第二种局面无需任何耗费时间的移动,要优于第一种局面经过两次移动后演变得到的结果!
因为经过两步移动后,第一种局面里在彼岸多出来的旅行者,在第二种局面里早已都在彼岸。
假设第一种局面的方案中的第一步是要把某个(或某两个)旅行者从彼岸移动到此岸(这时手电筒开始一定在彼岸),那么这就很简单,在第二种局面里这个(或这两个)旅行者一定也在彼岸,所以我们用相同的一步移动,花费一样的时间,把这个(或这两个)旅行者移动到此岸。
这样得到的结果还是第二种局面要优于第一种局面。
于是总而言之,无论第一种局面中采取什么样的移动,我们总可以采取花费同样多的时间(甚至更少或者根本不花费时间)的移动,使得第二种局面或者变为和第一种局面相同,或者仍旧优于第一种局面。
于是当第一种局面演变为完结局面时,第二种局面也一定演变为完结局面了,而花费的时间不会多于第一种局面所需的时间。
于是我们得到了很显然的结论:
结论一:
如果有两种局面,第二种局面优于第一种局面,那么我们总可以用少于解决第一种局面的时间来解决第二种局面。
四、更多的结论
通过结论一我们立刻得到:
结论二:
一定有这样一种最佳方案,在这个方案里,所有从彼岸到此岸的移动只需一个人。
如果最佳方案中有一步中需要两个人从彼岸移动到此岸,那么我们可以把这一步改为只移动比较快的那个人。
在这一步后,我们花费了最多和原来相同的时间,得到的局面却优于按原先方案执行完这一步后的局面,所以剩下的解决步骤不会比原方案花费更多的时间,所以必定是个最佳方案。
现在我们知道,我们可以要求在最佳方案中,每次只回来一个人。
在下面我们要得出另一个结论:
结论三:
一定有这样一种符合结论二的最佳方案,在这个方案里,所有从彼岸到此岸的移动中,回来的这个人一定是当时在彼岸所有人中速度最快的。
假设在所有满足结论二的最佳方案中,都没有符合结论三的方案,也就是说,任何一个最佳方案中,总有某一步从彼岸到此岸的移动中,回来的那个人不是当时在彼岸所有人中速度最快的。
那么我们在这些最佳方案中选取一个这样的“坏”步骤最晚出现的方案。
假设这个步骤首先出现在第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步:
YZ→ AZ→
如果y<z,那么改过的步骤消耗的时间和原来的一样;如果z<y,那么修改后的步骤消耗的时间还会更少。
现在两种局面的唯一区别在于,前一种是A在此岸Y在彼岸,而后一种恰好相反。
而且我们看到,经过这样修改的第n步现在符合“两人里有一个是所有人中最快的那个”这个结论六中的要求。
剩下的工作就是要理顺后面的步骤,使得修改过的方案仍旧是一个最佳方案,那时我们就用变分法推出了矛盾,从而证明结论六。
下面我们的技巧和前面所用过的略微不同,我们要修改的不是一个移动而是一串移动。
假设原来的第n+1步是“让Y1回来”,其中Y1是在彼岸的某人,他是在彼岸最快的。
我们把这第n+1步改为“让A回来”:
原来的方案 修改后的方案
…… ……
第n步:
YZ→ AZ→
第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步:
YZ→ AZ→
第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步:
YZ→ AZ→
第n+1步:
Y1← A←
…… ……
第n+j步:
Y1M→ AM→
第n+j+1步:
Y2← A←
这样修改后的步骤
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 过桥 问题