《人猫鸡米渡河问题的matlab求解法》由会员分享，可在线阅读，更多相关《人猫鸡米渡河问题的matlab求解法（7页珍藏版）》请在金锄头文库上搜索。
1、摘要：摘要：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米，试通过数学建模，运用计算机给出一个安全渡河方案，并使渡河次数尽量少。一、问题分析：一、问题分析：此问题是从状态向量 A（1,1,1,1）经过奇数次运算向量 B 变为状态向量A（0,0,0,0）的状态。转移过程为什么是奇数次？我们注意到过河有两种，奇数次的为从左岸到右岸，而偶数的为右岸回到左岸，因此得到下述转移过程，所以最后应该是过河完成时状态转移数为奇数次。二、模型假设：二、模型假设：1假设船除了载人之外，至多只能载猫、鸡、米三者之一。 2当人不在场时，猫一定会吃鸡、鸡一定会吃米。
2、我们将人，猫，鸡，米依次用四维向量中的分量表示，当一物在左岸时，相应的分量记为 1，在右岸时记为 0.如向量（1,0,1,0）表示人和鸡在左岸，猫和米在右岸，并将这些向量称为状态向量。例如（1,1,1,1）表示它们都在左岸， （0,1,1,0）表示猫，鸡在左岸，人，米在右岸；由于问题中的限制条件，有些状态是允许的，有些状态是不允许的。凡问题可以允许存在的状态称为可取状态。A 向量定义为状态变量。比如是一个可取状态向量，但11,0,1,0A是一个不可取状态向量。此外，B 向量定义为运载变量。把每运载20,0,1,1A一次也用一个四维向量来表示。如表示人和猫在船上，而鸡和米不11,1,0,0B在船
3、上，这自然是可取的运载，因为船可载两物，而则是不可取运21,0,1,1B载，依此规律类推。三、模型建立：三、模型建立：由上可知，可取状态向量共有 10 个，即：A1,1,1,10,0,0,01,1,1,00,0,0,11,1,0,10,0,1,01,0,1,10,1,0,01,0,1,00,1,0,1可取运载 B 有 4 个 ：（1,1,0,0） 、 （1,0,1,0） 、 （1,0,0,1） 、 （1,0,0,0） 。四、算法设计：四、算法设计：1 1、规定 A 和 B 的每一分量相加时按二进制法则进行，这样一次渡河就是一个可取状态和一个可取运载相加，在判断和向量是否属于可取状态即可。2 2
4、、可以将可取状态及可取运载分别编成矩阵。共分为五个 m 文件，一个主文件 xduhe.m 数，四个子文件分别为：2.12.1、duhe（L,B,M,s）函数：用来实现渡河总思路。思路为：将起始矩阵 A 分别与可取运载相加（使用二进制法则） ，判断相加后的矩阵 C 是否是（0，0，0，0） ，如果是，则渡河成功。否则，用 fuhe(C,M) 函数判断 C 是否是可取状态，如果是，则打印并将 C与初始矩阵合并成新矩阵，继续调用 duhe.m 函数。2.22.2、fuhe(C,M)函数：判断和矩阵 C 是否属于矩阵 M，如果是，则返回 1，否则返回 0.2.32.3、Panduan（S）函数：判断
5、S 矩阵中是否有两个相同的状态，即行向量。如果有，则返回 0，否则返回 1.2.42.4、print(K,C,s)函数：打印相应的状态。五、程序：五、程序：1、xduhe.m 文件：clear;clc;A=1,1,1,1;B=1,0,1,0;1,1,0,0;1,0,0,1;1,0,0,0;M=1,1,1,0;0,0,0,1;1,1,0,1;0,0,1,0;1,0,1,1;0,1,0,0;1,0,1,0;0,1,0,1;duhe(A,B,M,1);2、duhe.m 文件：function duhe(L,B,M,s);h,l=size(L);for k=s:hfor i=1:4C=mod(L(k,
6、:)+B(i,:),2);if C=0,0,0,0print(B(i,:),C,s);fprintf(渡河成功nn);break;else if fuhe(C,M)=1print(B(i,:),C,s); S=L;C; if Panduan(S)=1duhe(S,B,M,s+1);elsefprintf(此渡河方案不可行nn);endendendendend3、fuhe.m 文件：function y=fuhe(C,M)y=0;for i=1:8if(C=M(i,:)y=1;break;endend4、Panduan.m 文件：function z=Panduan(S)z=1;m,n=size
7、(S);for p=1:mfor q=(p+1):mif S(p,:)-S(q,:)=0,0,0,0z=0;break;endendend5、print.m 文件：function print(K,C,s)fprintf(第%d 次渡河:,s);if K(1)=1fprintf(人, );endif K(2)=1fprintf(猫, );endif K(3)=1fprintf(鸡, );endif K(4)=1fprintf(米, );endif C(1)=0fprintf(从左岸到达右岸n);elsefprintf(从右岸回到左岸n);end六、计算结果：六、计算结果：在 matlab 中运行，结果如下：七、结果分析：七、结果分析：从运行结果可以看出，共有两种运送方案：人先带鸡过河，然后人再回来，把米带过河，然后把鸡运回河岸，人再把猫带过河，最后人回来把鸡带过去。人先带鸡过河，然后人再回来，把猫带过河，然后把鸡运回河岸，人再把米带过河，最后人回来把鸡带过去。八、结论：八、结论：1、人带鸡过河，然后人回来，把米带过河，把鸡运回河岸，人再把猫带过河，最后人回来把鸡带过去。2、人带鸡过河，然后人回来，把猫带过河，把鸡运回河岸，人再把米带过河，最后人回来把鸡带过去。
