渡河问题20160430.doc

一、渡河问题 1、问题描述 有一个人带着一只狼、一只羊和一筐菜来到河边（假设狼不吃人），河边有一小船，每次只允许他带走一样东西；另外，如果他不在的时候，狼要吃羊，羊要吃菜。他应该采取什么样的方案，才能把狼、羊、菜都安全地带到河对岸？ 2、规模分析 问题中共有5个事物：人、狼、羊、菜、船。但由于只有人能够划船，故船的位置必然和人相同，状态独立的事物只有4个。每个事物有两种独立的状态：在此岸或在彼岸。所有可能出现的状态共计24=16种。 3、不安全状态分析 将每个事物在此岸（未过河）的状态标记为0，在彼岸（已过河）的状态标记为1，则不安全的状态有两类： （1）人≠狼 且 狼=羊 （2）人≠羊 且 羊=菜 4、状态转换（不安全状态不予考虑） 能够从某个状态转直接换到另外一个状态的判据是同时满足以下所有条件： （1）人的位置发生改变； （2）最多两者发生位置改变且改变方向都与人相同。 若满足状态转换条件，则在状态转换图中相应的两个结点之间添加一条边。 根据以上条件，可以列出状态转换图为 图中红色底色为不安全状态。两个状态之间有线相连表示这两个状态之间可以一次转换到位。图中粗线条表示必经之路。 5、问题求解 渡河问题的求解即是在状态转换图中寻找从起始结点(0,0,0,0)到终止结点(1,1,1,1)之间的最短路径。该最短路径可能不止一条，每条最短路径都是该问题的最佳可行解。 该问题的全部的两个最佳可行解为： 人 狼 羊 菜 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 人 狼 羊 菜 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 整个过程至少需要7步（划船7次，3.5个来回）才能完成。具体过程可以有两种： （1）将羊带过河，自己返回；将狼带过河，将羊带回；将菜带过河，自己返回；将羊带过河。 （2）将羊带过河，自己返回；将菜带过河，将羊带回；将狼带过河，自己返回；将羊带过河。 上述两者的区别仅仅是狼和菜的位置互换。 二、扩展渡河问题 1、问题描述 有一个猎人带着一只狼、一对夫妻带着他们的孩子A和B需要过河，其中能够划船的只有猎人和那对夫妻三个人。当猎人不在的时候，狼会杀害孩子A和孩子B；当丈夫不在的时候，妻子会杀害孩子A；当妻子不在的时候，丈夫会杀害孩子B。船上一次只能有两个。应该采取什么样的方案，才能让猎人、夫妻、狼和两个孩子都安全过河？ 2、规模分析 问题中共有7个事物：猎人、丈夫、妻子、狼、孩子A、孩子B、船。由于有三个人能够划船，故船的位置可认为是独立的。每个事物有两种独立的状态：在此岸或在彼岸。所有可能出现的状态共计27=128种。 3、不安全状态分析 将每个事物在此岸（未过河）的状态标记为0，在彼岸（已过河）的状态标记为1，则不安全的状态有两类： （1）猎人与狼不在一起 且 狼和某个孩子在一起 （2）男人与女人不在一起 且 其中某人和其要杀害的孩子在一起 4、状态转换（不安全状态不予考虑） 能够从某个状态转直接换到另外一个状态的判据是同时满足以下所有条件： （1）小船位置发生改变； （2）最多两者发生位置改变且改变方向都与小船航向相同； （3）至少一个能够划船者的位置发生变化。 若满足状态转换条件，则在状态转换图中相应的两个结点之间添加一条边。 5、问题求解 渡河问题的求解即是在状态转换图中寻找从起始结点(0,0,0,0,0,0,0)到终止结点(1,1,1,1,1,1,1)之间的最短路径。该最短路径可能不止一条，每条最短路径都是该问题的最佳可行解。 该问题规模较大（128个结点），可以考虑使用计算机编程求解。程序输出的一个最佳可行解为： 猎人 丈夫 妻子 狼 孩子A 孩子B 船 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 总计需要9个步骤。具体步骤为：妻子带孩子B过河，妻子返回；丈夫和妻子过河，丈夫返回；猎人带狼过河，妻子返回；丈夫和妻子过河，丈夫返回；丈夫带孩子A过河。 显然，将上述步骤中的丈夫和妻子位置互换、孩子A和孩子B的位置互换，则可以得到另外一个最佳可行解，即：丈夫带孩子A过河，丈夫返回；丈夫和妻子过河，妻子返回；猎人带狼过河，丈夫返回；丈夫和妻子过河，妻子返回；妻子带孩子B过河。 三、最佳可行解的总数 状态转换图是由各个状态结点和联接结点的边构成的拓扑结