人狼羊菜 带源程序
- 格式：doc
- 大小：31.00 KB
- 文档页数：3
人狼羊菜实验报告
————第一次作业
题目：一个摆渡人F希望用一条小船把一只狼W，一头羊G 和一篮白菜C 从一条河的左岸渡到右岸去，而船小只能容纳F、W、G、C 中的两个，决不能在无人看守的情况下，留下狼和羊在一起，羊和白菜在一起，应怎样渡河才能将狼、羊、白菜都运过去?
模型构成：用状态转移解决。
构造四维向量，表示人狼羊菜分别的位置。
用0表示不在此岸,1表示在此岸。
则允许状态集合A包含：(1,1,1,1)，(0,0,0,0)，
(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)。
船上元素即运载状态允许的集合B为：(1,1,0,0), (1,0,1,0),
(1,0,0,1), (1,0,0,0)。
在上述规定下，问题转化为：从初始状态(1,1,1,1)经过多少次可取运算才能转化为化为(0,0,0,0)并且在过程中状态总在允许状态集合A中。
注：集合A、B中的两状态相加时按2进制进行。
用Matlab进行编程，主文件
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);
将可取状态及可取运载分别编成矩阵，调用duhe（L,B,M,s）函数
将起始矩阵A分别与可取运载相加（使用二进制法则），判断相加后的矩阵C是否是【0，0，0，0】，如果是，则渡河成功。
function duhe(L,B,M,s);
[h,l]=size(L);
for k=s:h
for i=1:4
C=mod(L(k,:)+B(i,:),2);
if C==[0,0,0,0]
print(B(i,:),C,s);
fprintf('渡河成功\n\n');
break;
else if fuhe(C,M)==1
print(B(i,:),C,s);
S=[L;C];
if Panduan(S)==1
duhe(S,B,M,s+1);
else
fprintf('此渡河方案不可行\n\n');
end
end
end
end
end
否则，用fuhe(C,M) 函数（判断和矩阵C是否属于矩阵M，如果是，则返回1，否则返回0）.判断C是否是可取状态，如果是，则打印并将C与初始矩阵合并成新矩阵，继续调用duhe.m 函数。
function y=fuhe(C,M)
y=0;
for i=1:8
if(C==M(i,:))
y=1;
break;
end
end
再调用Panduan(S)函数（判断S矩阵中是否有两个相同的状态，即行向量。
如果有，则返回0，否则返回1.）
function z=Panduan(S)
z=1;
[m,n]=size(S);
for p=1:m
for q=(p+1):m
if S(p,:)-S(q,:)==[0,0,0,0]
z=0;
break;
end
end
end
最后调用print(K,C,s)函数。
打印相应的状态。
function print(K,C,s)
fprintf('第%d次渡河:',s);
if K(1)==1
fprintf('人, ');
end
if K(2)==1
fprintf('狼, ');
end
if K(3)==1
fprintf('羊, ');
end
if K(4)==1
fprintf('菜, ');
end
if C(1)==0
fprintf('从左岸到达右岸\n');
else
fprintf('从右岸回到左岸\n');
end
运行即可。
将上述五个程序分别保存为文件，分别命名为：xduhe.m
duhe.m
fuhe.m
panduan.m
print.m。
