最佳方案构造法：以下是构造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个旅行者的情形，从而递归解决之。

• Re:一点思路，转的…… (10) 1100012760 2012-08-03 18:27:36