过桥问题

过桥问题：

问题描述：4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？

Morewindows的方法（以下参考blog: http://blog.csdn.net/MoreWindows/article/details/7481851）

Morewindows君通过观察发现，要么是最快者将最慢的2个送过桥，要么是最快的2个将最慢的2个送过桥。即将过桥的人按其过桥的时间从小到大排列，设为A，B，…… Y，Z。其中A和B是最快的二个，Y和Z是最慢的二个。那么就有二种方案：

方案一 最快者将最慢的2个送过桥

第一步：A和Z过桥，花费Z分钟。

第二步：A回来，花费A分钟。

第三步：A和Y过桥，花费Y分钟。

第四步：A回来，花费A分钟。

这四步后总人数就减小2个，花费时间为A + A + Y + Z分钟。

方案二 最快的2个将最慢的2个送过桥

第一步：A和B过桥，花费B分钟。

第二步：A回来，花费A分钟。

第三步：Y和Z过桥，花费Z分钟。

第四步：B回来，花费B分钟。

这四步后总人数同样减小2个，花费时间为A + B + B + Z分钟。

这样，每次比较一下这二种方案就能将总人数减小2。然后我们再考虑一些边界情况：

有三个人过桥设为A，B，C（已经排好序，下同）。应该花费A + B + C分钟。

有二个人过桥设为A，B。那么肯定是花费B分钟。

有一个人过桥设为A。肯定花费A分钟。

上述方法并没有证明其正确性，只不过在实际中可用。

接着自己实现代码如下：

解决上述问题有两种方法：
1.  Dijkstra单源最短路径。
如果用Dijkstra来解上面的问题，单源最短路径是求源到所有端点的路径，而我们只要求到满节点的路径，故我们会有许多无用的计算。
2.  动态规划。
看出来，上面的图是分阶段了，可以用动态规划。
 
编程实践：
节点数：节点为N的所有子集，有2^N个节点；还得要有退回后的中间节点，我们总共要生成这2^（N+1）个节点。
有向边数：我们只看偶数阶段的节点。每个节点入度为N(N-1)/2的边,即选取两个退回到上一步；出度为N个，即选一个回去。最后每个节点相关N(N+1)/2条边。总共也就是N(N+1)*2^N条边。
 
时间复杂度：
初始化节点和边O(2^（N+1)),O(N^2*2^N);
Dijstra遍历,这时的节点数是2^（N+1）,那么即为 O(2^(2N+2));
动态规划遍历，经过所有的边，O(N^2*2^N)。
不管哪种方法，时间复杂度貌似都高的吓人，程序我还是不编了。
 
通过上面的方法，用计算机解决的暂时看来是morewindows君的方法可以实践。
本人水平有限，太菜的地方请高手指正。
 

1楼han_miao昨天 21:11
很全面，虽然我看不大懂...