用图论解决四人过桥问题

1、用图论解决四人过桥问题问题：有一天晚上，有四个人需要通过架在山谷间的危桥，任意时刻最多只能有两个人在桥上，过桥需要一盏闪光灯，这些人只有一盏闪光灯。如果单独过桥他们分别需要10、5、2、1分钟，如果两人同时过桥则所需时间是较慢者所需的时间。18分钟后，沿山谷滚滚而下的山洪将把这座桥冲毁。这四个人能及时过桥吗？不用图论知识，证明你的结论；并说明如何用图论知识获得答案。过桥问题说的是4个人在晚上过一座小桥，过桥时必须要用到手电筒，只有一枚手电筒，每次最多只可以有两人通过， 4个人的过桥速度分别为1分钟、2分钟、5分钟、10分钟，试问最少需要多长时间4人才可以全部通过小桥？这个问题如果用图论来建模的

2、话，就可以以4个人在桥两端的状态来作为节点来构造一个有向图，如下图所示，以已经过桥了的人的状态作为图的节点，初始时没有人过桥，所以以空表示，第一轮有两个人过桥，有6种可能的组合，(1，2)（1，5）（1，10）（2，5）（2，10）（5，10），从空的状态转换到这些状态的需要的时间分别为2，5，10，5，10，10分钟，时间就作为有向边的权值。当有两个人过桥后，需要一个人拿手电筒回去接其他人，这时有四种可能的情况，分别是1，2，5，10中的一人留在了河的对岸，（1，2）这种状态只能转换到（1）（2）两种状态，对应的边的权值分别为2，1分钟，（1，2）转换到（1）时也就是2返回了，返回需要耗时2

3、分钟，以此类推可以建立以下的图论模型。要求出最少需要多长时间4人全部通过小桥实际上就是在图中求出（空）节点到（1，2，5，10）节点间的最短路径。根据Dijkstra最短路径算法很容易求出其最短路径，如图中的粗线所示。这样总时间为21102217分钟所以能够活学图论的话，这类智力问题就变成了图论的入门级的问题。现在如果让一个测试人员来回答这个问题的话，是不是也象上述一样回答就可以了呢？如果能在很短时间内象上面一样回答问题，当然说明你人比较聪明，但是如果作为测试人员的话，需要的不是简单的结果，而是要全面分析问题，仅仅回答出最短时间为17分钟的答案是达不到测试人员的要求的。作为一个测试人员，首先得

4、对问题中的许多未知因素提出疑问，下面一些问题也许是测试人员所想知道的：这4个人为什么要在晚上过这座桥，他们是在正常回家的路上还是野外探险迷路还是被人追杀？如果是被人追杀会不会有2人过去后独自逃走不回来接剩下的2人？这四个人过桥的时间为什么差距这么大，最大最小时间差了10倍？进而可以提出疑问，这4个人到底是什么样的人？他们的年龄分别多大？他们是否有人是残疾人或是小孩？如果有小孩或残疾人的话，那么是不是残疾人和小孩不能同时过桥？（也就是说5和10不能同时过桥）既然最多只有2人可以同时过桥，那么桥的最大承重能力是多少？是不是两个最重的人也可以同时过桥？手电筒是不是好的，手电筒里的电是不是用完了，或者

5、手电筒的电还能用多久？或者过桥的过程中手电筒会不会掉到桥下去或摔坏？当时的天气是什么样的？有没有刮风下雨、打雷或下暴雪，会不会有人在过桥过程中被风刮下桥去，或者被打雷声吓得掉下桥去。或者过桥时天气变坏使得他们过桥需要的时间增加了。当时的气温是多少度？如果温度低于0度的话，桥上是不是结冰了，过桥时会不会滑下去？过桥的过程中对面是不是有救援人员来了，比如1、2过去后就碰到救援人员等在对岸，那么1也许可以拿救援人员的电筒过去接剩下的两个人，这样最少只要14分钟就可以过桥了。过桥的过程中是否有山洪爆发或水突然涨高将桥淹没？会不会在过桥过程中有野兽嚎叫等因素影响他们的过桥速度？桥下面是什么？是水溪还是无

6、水的沟谷还是很深的悬崖？人掉下去后能不能爬上来？桥旁边有没有其他的捷径可以过去。1分钟的人是否可以背上10分钟的人过桥？如果可以的话需要多长时间？桥有多长？手电筒能照多远？是否过去的人在桥的另外一头就可以用手电筒照亮桥让未过去的人过桥？这些问题的确定对过桥需要的最短时间都会有影响，在不同的情况下过桥所需要的最短时间是不同的。以上只是写出了一些问题，还有更多的问题读者可以自己去发掘，如果能在上面的基础上再发掘出2个以上的新问题的话，那么相信你已经具备了测试人员全面分析问题的素养了。不过即使你不能发现新的问题，并且上面的那些问题你很多都没有想到，也没有任何关系，当学完后面第3章的测试用例设计方法后

7、再来重新分析这个问题，也许你会惊喜地发现你已经有能力发现很多新的问题了。当然初学者也许会觉得有些问题像是在钻牛角尖，但作为测试人员来讲，要的就是这种钻牛角尖的精神。旅行者出发桥的这一边A B C D的状态为（1,1,1,1），“”表示桥的这一边的下一状态，直到状态变为（0,0,0,0）A B C D ：(1,1,1,1)（1,1,0,0）（1,1,0,1）（1,0,0,0）（1,0,0,1）（0,0,0,0）时间（分钟）： 2 1 5 1 10一共就是2+1+5+1+10=19分钟。此方法的时间大于18分钟，故不能及时过河。但有另外更快的方法是他们及时过桥：A B C D ：(1,1,1,1)（1,1,0,0）（1,1,0,1）（0,0,0,1）（0,0,1,1）（0,0,0,0）时间（分钟）： 2 1 10 2 2一共是