渡河问题20160430

1、一、渡河问题1、问题描述有一个人带着一只狼、一只羊和一筐菜来到河边（假设狼不吃人），河边有一小船，每次只允许他带走一样东西；另外，如果他不在的时候，狼要吃羊，羊要吃菜。他应该采取什么样的方案，才能把狼、羊、菜都安全地带到河对岸？2、规模分析问题中共有5个事物：人、狼、羊、菜、船。但由于只有人能够划船，故船的位置必然和人相同，状态独立的事物只有4个。每个事物有两种独立的状态：在此岸或在彼岸。所有可能出现的状态共计24=16种。3、不安全状态分析将每个事物在此岸（未过河）的状态标记为0，在彼岸（已过河）的状态标记为1，则不安全的状态有两类：（1）人狼 且 狼=羊（2）人羊 且 羊=菜4、状态转换（

2、不安全状态不予考虑）能够从某个状态转直接换到另外一个状态的判据是同时满足以下所有条件：（1）人的位置发生改变；（2）最多两者发生位置改变且改变方向都与人相同。若满足状态转换条件，则在状态转换图中相应的两个结点之间添加一条边。根据以上条件，可以列出状态转换图为图中红色底色为不安全状态。两个状态之间有线相连表示这两个状态之间可以一次转换到位。图中粗线条表示必经之路。5、问题求解渡河问题的求解即是在状态转换图中寻找从起始结点(0,0,0,0)到终止结点(1,1,1,1)之间的最短路径。该最短路径可能不止一条，每条最短路径都是该问题的最佳可行解。该问题的全部的两个最佳可行解为：人狼羊菜00001010

3、001011100100110101011111人狼羊菜00001010001010110001110101011111整个过程至少需要7步（划船7次，3.5个来回）才能完成。具体过程可以有两种：（1）将羊带过河，自己返回；将狼带过河，将羊带回；将菜带过河，自己返回；将羊带过河。（2）将羊带过河，自己返回；将菜带过河，将羊带回；将狼带过河，自己返回；将羊带过河。上述两者的区别仅仅是狼和菜的位置互换。二、扩展渡河问题1、问题描述有一个猎人带着一只狼、一对夫妻带着他们的孩子A和B需要过河，其中能够划船的只有猎人和那对夫妻三个人。当猎人不在的时候，狼会杀害孩子A和孩子B；当丈夫不在的时候，妻子会杀害

4、孩子A；当妻子不在的时候，丈夫会杀害孩子B。船上一次只能有两个。应该采取什么样的方案，才能让猎人、夫妻、狼和两个孩子都安全过河？2、规模分析问题中共有7个事物：猎人、丈夫、妻子、狼、孩子A、孩子B、船。由于有三个人能够划船，故船的位置可认为是独立的。每个事物有两种独立的状态：在此岸或在彼岸。所有可能出现的状态共计27=128种。3、不安全状态分析将每个事物在此岸（未过河）的状态标记为0，在彼岸（已过河）的状态标记为1，则不安全的状态有两类：（1）猎人与狼不在一起 且 狼和某个孩子在一起（2）男人与女人不在一起 且 其中某人和其要杀害的孩子在一起4、状态转换（不安全状态不予考虑）能够从某个状态转

5、直接换到另外一个状态的判据是同时满足以下所有条件：（1）小船位置发生改变；（2）最多两者发生位置改变且改变方向都与小船航向相同；（3）至少一个能够划船者的位置发生变化。若满足状态转换条件，则在状态转换图中相应的两个结点之间添加一条边。5、问题求解渡河问题的求解即是在状态转换图中寻找从起始结点(0,0,0,0,0,0,0)到终止结点(1,1,1,1,1,1,1)之间的最短路径。该最短路径可能不止一条，每条最短路径都是该问题的最佳可行解。该问题规模较大（128个结点），可以考虑使用计算机编程求解。程序输出的一个最佳可行解为：猎人丈夫妻子狼孩子A孩子B船00000000010011000001001

6、10011001001010110111001010111101110110101111111总计需要9个步骤。具体步骤为：妻子带孩子B过河，妻子返回；丈夫和妻子过河，丈夫返回；猎人带狼过河，妻子返回；丈夫和妻子过河，丈夫返回；丈夫带孩子A过河。显然，将上述步骤中的丈夫和妻子位置互换、孩子A和孩子B的位置互换，则可以得到另外一个最佳可行解，即：丈夫带孩子A过河，丈夫返回；丈夫和妻子过河，妻子返回；猎人带狼过河，丈夫返回；丈夫和妻子过河，妻子返回；妻子带孩子B过河。三、最佳可行解的总数状态转换图是由各个状态结点和联接结点的边构成的拓扑结构。求最佳可行解就是在状态转换图中寻找从起始结点到终止结点的

7、最短路径。在所有边的权重都相同（即长度都相等）的情况下，最短路径的长度就是路径上边的总数。从上述两个例子中可以发现，这种最短路径很可能不止一条。设状态转换图对应的邻接矩阵为C，这是一个对称的n阶方阵，n为结点总数。C的元素C(i,j)=1当且仅当从结点i到结点j有边；其余情况下C(i,j)=0。令P=C+C2+C3+Cx，则P(i,j)=t表示在x步之内，从结点i到结点j存在t条不同的路径。若将x指定为已知的最短路径的长度，即在上述第二个问题中x=9，则P(1,128)=2，即只有两个不同的最佳可行解。四、时间复杂度分析对于有n种状态的问题，1、建立状态空间：将十进制自然数n转换成二进制所需步

8、骤数量（时间代价）为log(n)（这里的对数以2为底数，下同），将1到n全部转换为二进制，所需时间代价不高于n*log(n)，用O(n*log(n)表示。2、判断不安全状态：对每个结点分别判断其安全性，所需时间代价为O(n)。3、建立状态转换图：判断每两个结点之间能否建立转换关系，所需时间代价为O(n2)。4、求最短路径：边权为任意正数时，Dijkstra算法所需时间代价为O(m)+O(n2)，Ford算法所需时间代价为O(mn)；边权均为1时，改进的Dijkstra算法所需时间代价可降为O(m)。这里的m代表状态转换图中边的数量。5、还原路径：若最短路径长度为L，则从状态转换图中还原路径所需

9、代价为O(L)。6、确定最佳可行解的个数：每次矩阵乘法运算的时间代价为O(n3)，矩阵加法运算的时间代价为O(n2)，共需进行L次，总时间代价为O(Ln3)。五、引申内容在第二个问题中，若加入不同人划船速度不同，而最终要求解总时间最短的方案，则可以在状态转换图中将边赋予不同的权值，该权值即为船上所有可以划船者的最短时间。其余可以扩展的部分，欢迎大家继续开脑洞附录A：十进制自然数转换为二进制的MATLAB程序function Y = Dec2Bin(n) if n=0 Y=0;else Y=;end; while n=0 if mod(n,2)=0 Y=0,Y; else Y=1,Y; end;

10、 n=floor(n/2);end;附录B：求最短路径的MATLAB程序（Floyd-Warshall算法）function LEN,PATH=ShortestPath(C,I,J)%=%相关概念：% 1、正权图G中，若P(i,j)是是从i到j的最短路，且结点k属于P(i,j)，则P(i,k)是i到%k的最短路；% 2、正权图中任意一条最短路径的长度大于其局部路径的长度。%=%实际意义：% 最短路径问题：任意两个结点之间的最短路径。%=%算法及步骤：% 使用Floyd-Warshall算法求图中任意两点之间的最短路径。% 时间复杂度为O(n3)。% step1：将未直接相连的两个结点之间的路径

11、长度设置为无穷大。% step2：若从结点i经结点k到结点j的路径长度小于从结点i到结点j的现有路径长度，则% 记录k和较短路径的长度。% step3：根据记录的中间结点矩阵，还原出所需要的路径。%=%函数的使用：% 输入：% （1）权矩阵C；% （2）道路首结点I；% （3）道路尾节点J。% 输出：% （1）路径长度LEN；% （2）路径中的各个结点编号集PATH。%= n=max(size(C);C1=C;through=zeros(n,n); %记录两个结点之间的最短路径上的中间结点 for i=1:n for j=1:n if i=j & C1(i,j)=0 C1(i,j)=i

12、nf; end; end;end; for k=1:n for i=1:n for j=1:n if C1(i,j)>C1(i,k)+C1(k,j); C1(i,j)=C1(i,k)+C1(k,j); %从i到j的最短路径经过结点k through(i,j)=k; end; end; end;end; %还原路径LEN=C1(I,J);PATH=I,J;i=1;while 1 if through(PATH(i),PATH(i+1)=0 PATH=PATH(1:i),through(PATH(i),PATH(i+1),PATH(i+1):length(PATH); continue; e

13、lse i=i+1; end; if i=length(PATH) break; end;end;附录C：求解第二个问题的程序%位置标记：猎人,男,女,狼,子A,子B,船，0代表未过河，1代表已过河 %建立状态空间=for n=1:128 %转二进制 x=Dec2Bin(n-1); space(n,:)=zeros(1,7-length(x),x;end; %判断不安全状态= unsafe=zeros(1,128); %标记不安全状态for n=1:128 %第一种不安全状态：猎人与狼不在一起且狼和某个孩子在一起 if space(n,1)=space(n,4)&&(space

14、(n,4)=space(n,5)|space(n,4)=space(n,6) unsafe(n)=1; end; %第二种不安全状态：男人与女人不在一起且其中某人和其要杀害的孩子在一起 if space(n,2)=space(n,3)&&(space(n,3)=space(n,5)|space(n,2)=space(n,6) unsafe(n)=1; end;end; %建立状态转换图=for x=1:127 if unsafe(x)=1; continue; %不安全状态不予考虑 end; for y=(x+1):128 if unsafe(y)=1 continue; %不安全状态不予考虑 end; %可以一步转换的条件 if space(x,7)=space(y,7) %小船位置发生改变 delta=space(y,1:6)-space(x,1:6); %最多两者发生位置改变且改变方向都与小船航向相同 if sum(abs(delta)=abs(sum(delta)&&sum(delta)*(space(y,7)-space(x,7)<=2 %至少一个能够划船者的位置发生变化 if sum(abs(delta(1:3)=abs(sum(delta(1:3)&&sum(