posts - 100,  comments - 15,  trackbacks - 0

结论一:?哪去了?

结论二:
一定有这样一种最佳方案,在这个方案里,所有从彼岸到此岸的移动只需一个人。  如果最佳方案中有一步中需要两个人从彼岸移动到此岸,那么我们可以把这一步改为只移动比较快的那个人。

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

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


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


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


结论七:
一定有这样一种符合结论二—六的最佳方案,在这个方案里,所有从彼岸到此岸的移动中,回来的这个人一定是当时在彼岸所有人中速度最快的,而且他只能是所有人中最快的或者次快的。 
换句话说,所有返回此岸的任务都可以只由跑得最快和跑得次快的人来担当,所有其他人一旦到达彼岸,就留在那里,再也不回来。

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


假设A为最快,B为次快,而Z是任意一个其他旅行者。
模式一:由A护送到Z对岸,A返回
模式二:AB->,A<-,YZ->,B<-

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

结论 
 如果给定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分钟的方案必定是最佳的。

posted on 2009-07-08 22:38 wyiu 阅读(697) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理