MATLAB解决人猫鸡米渡河数学建模

声明：本文章参考了参考资料（点击即可访问）
)

一、问题描述

人带着猫、鸡、米过河，除需要人划船之外，船至多能载猫、鸡、米 三者之一，而当人不在场时猫要吃鸡、鸡要吃米，试设计一个安全过河方案，并使渡河次数尽量地少。

二、模型假设

1. 假设船除了载人之外，至多只能载猫、鸡、米三者之一
2. 假设当人不在场时，猫一定会吃鸡、鸡一定会吃米。
   将人、猫、鸡、米依次用四维向量中的分量表示，在左岸记为 1，在右岸记为 0。在船上记为1，不在船上记为0.
   A向量为状态向量，B向量为运载向量。
   A（1 0 1 0）表示人、鸡在左岸，猫、米在右岸，这种情况是允许的，而 A（1 1 0 0）表示人、猫在左岸，鸡、米在右岸，这种情况是不允许的。
   B（1 0 0 1）表示人、米在船上，鸡、猫不在船上，这种情况是允许的，而 B（1 0 1 1）表示人、鸡、米都在船上，猫不在船上，这种情况是不允许的。

三、模型建立

易知，可取的状态向量 A 共有 10 个，即：
（1 1 1 1） （1 0 1 1）（1 1 0 1）（1 1 1 0） （1 0 1 0）（0 1 0 1） （0 1 0 0）（0 0 0 1）（0 0 1 0） （0 0 0 0）
可取的运载向量 B 共有四个，即：（1 0 0 0）（1 1 0 0）（1 0 0 1）（1 0 1 0）

四、算法设计

1. 规定 A 和 B 向量的每一分量相加时按照二进制法则进行，故可将每次渡 河转换成两个向量相加，只需判断和向量是否属于可取状态即可。
2. 初始时可将可取状态和可取运载状态分别放入矩阵，共代码分五个文件， 一个主文件，四个子文件
   2.1、duhe(L,B,M,s)函数： 实现渡河总思路。将初始矩阵 A 分别与可取运载矩阵 B 相加，判断 和矩阵是否为[0 0 0 0],若是，渡河成功，否则用 fuhe(C,M)判断 C 是否 可取，若可取则打印并将 C 于初始矩阵合并成新矩阵，继续调用 duhe 函 数。
   2.2、fuhe(C,M)函数 判断矩阵 C 是否属于矩阵 M，若是，返回 1，否则返回 0。
   2.3、Panduan(S)函数
   判断 S 矩阵中是否有两个相同的状态向量，若有，返回 0，否则返回 1。
   2.4、print(K,C,s)函数 返回当前渡河情况（字符串形式），在 duhe 函数中显示。

五、代码实现

1.ZDuhe.m 文件

clc,clear,close all; 
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];%8 种可能的中间状态 
duhe(A,B,M,1);

2.duhe.m 文件

function duhe(L,B,M,s)%result 用来存放渡河的步骤 
[h,~] = size(L); 
for k = s:h 
    for i = 1:4 
        C = mod(L(k,:)+B(i,:),2);%二进制加法，得到渡河后 状态 
        if C == [0 0 0 0]%若此时全部到达右岸说明渡河成功
            disp(print(B(i,:),C,s)); 
            fprintf('渡河成功\n\n'); 
            break; 
        else if fuhe(C,M) == 1 %如果状态合理，输出这一步渡河的具体情况 
            disp(print(B(i,:),C,s)); 
            S = [L;C];%将渡河后的状态加入到初始状态矩阵，原来是一行，加入后就是两行 
            if Panduan(S) == 1%若没有重复的向量，则从新加入的状态开始继续渡河 
            duhe(S,B,M,s+1);%s+1表示取新加入的状态，即更新状态 
        else 
           fprintf('此渡河方案不可行\n\n');%若有重复的状态说明过程进入了循环，此路不通 
            end 
        end
    end
end 
end

3. fuhe.m 文件

function y=fuhe(C,M)%判断渡河一次后的状态是否允许，若允许返回1，否则返回0 
y=0; 
for i = 1:8 
    if(C==M(i,:)) 
        y=1; 
        break; 
    end 
end

4. Panduan.m 文件

function z = Panduan(S) z=1; 
[m,n]=size(S);%获取 S 的尺寸 
for p = 1:m 
    for q = (p+1):m 
        if S(p,:)-S(q,:)==[0 0 0 0]%若有重复的向量则返回0，否则返回1 
            z=0; 
            break; 
        end 
    end 
end

5. print.m 文件

function msg=print(K,C,s)%函数用于输出每一步的渡河过程, 返回一个字符串 
msg = ' '; 
msg = strcat(msg,'第',num2str(s),'次渡河:'); i
f K(1) == 1
    msg = strcat(msg,'人,'); 
end
if K(2)==1
    msg = strcat(msg,'猫,');
end
if K(3)==1
msg = strcat(msg,'鸡,');
end
if K(4)==1
msg = strcat(msg,'米,');
end
if C(1)==0%C(1)表示人的位置，0 表示渡河后在右岸，则应该是 从左岸到右岸
    msg = strcat(msg,'从左岸到达右岸');
else 
    msg = strcat(msg,'从右岸到达左岸');
end

六、运行结果

第 1 次渡河:人,鸡,从左岸到达右岸
第 2 次渡河:人,从右岸到达左岸
第 3 次渡河:人,猫,从左岸到达右岸
第 4 次渡河:人,鸡,从右岸到达左岸
第 5 次渡河:人,鸡,从左岸到达右岸
此渡河方案不可行

第 5 次渡河:人,米,从左岸到达右岸
第 6 次渡河:人,猫,从右岸到达左岸
第 7 次渡河:人,鸡,从左岸到达右岸
第 8 次渡河:人,鸡,从右岸到达左岸
此渡河方案不可行

第 8 次渡河:人,米,从右岸到达左岸
此渡河方案不可行

第 7 次渡河:人,猫,从左岸到达右岸
此渡河方案不可行

第 6 次渡河:人,米,从右岸到达左岸
此渡河方案不可行

第 6 次渡河:人,从右岸到达左岸
第 7 次渡河:人,鸡,从左岸到达右岸
渡河成功

第 4 次渡河:人,猫,从右岸到达左岸
此渡河方案不可行

第 3 次渡河:人,米,从左岸到达右岸
第 4 次渡河:人,鸡,从右岸到达左岸
第 5 次渡河:人,鸡,从左岸到达右岸
此渡河方案不可行

第 5 次渡河:人,猫,从左岸到达右岸
第 6 次渡河:人,猫,从右岸到达左岸
此渡河方案不可行

第 6 次渡河:人,米,从右岸到达左岸
第 7 次渡河:人,鸡,从左岸到达右岸
第 8 次渡河:人,鸡,从右岸到达左岸
此渡河方案不可行

第 8 次渡河:人,猫,从右岸到达左岸
此渡河方案不可行

第 7 次渡河:人,米,从左岸到达右岸
此渡河方案不可行

第 6 次渡河:人,从右岸到达左岸
第 7 次渡河:人,鸡,从左岸到达右岸
渡河成功

第 4 次渡河:人,米,从右岸到达左岸
此渡河方案不可行

第 3 次渡河:人,从左岸到达右岸
此渡河方案不可行

七、结论

根据运行结果，共有两种方案：

1. 人带鸡过河，人回来，人带米过河，人带鸡回来，人带猫过河，人回来，人带鸡过河。
2. 人带鸡过河，人回来，人带猫过河，人带鸡回来，人带米过河，人回来，人带鸡过河。