人猫鸡米渡河问题的数学模型Word文档格式.docx
《人猫鸡米渡河问题的数学模型Word文档格式.docx》由会员分享，可在线阅读，更多相关《人猫鸡米渡河问题的数学模型Word文档格式.docx（14页珍藏版）》请在冰点文库上搜索。
1.2：
当人不在场时，猫一定会吃鸡、鸡一定会吃米。
四、定义符号说明：
我们将人，猫，鸡，米依次用四维向量中的分量表示，当一物在左岸时，相应的分量记为1，在右岸时记为0.如向量（1,0,1,0）表示人和鸡在左岸，猫和米在右岸，并将这些向量称为状态向量。
例如（1,1,1,1）表示它们都在左岸，（0,1,1,0）表示猫，鸡在左岸，人，米在右岸；
由于问题中的限制条件，有些状态是允许的，有些状态是不允许的。
凡问题可以允许存在的状态称为可取状态。
A向量定义为状态变量。
比如
是一个可取状态向量，但
是一个不可取状态向量。
此外，B向量定义为运载变量。
把每运载一次也用一个四维向量来表示。
如
表示人和猫在船上，而鸡和米不在船上，这自然是可取的运载，因为船可载两物，而
则是不可取运载，依此规律类推。
五、模型的建立
对于这个问题我们用穷举的方法来解决，首先将此问题化为状态转移问题来解决。
对本问题来说：
5.1、可取状态向量
共有10个，可以用穷举法列出来：
右边5个正好是左边5个的相反状态。
5.2、可取运载
共有4个：
5.3、可取运算：
规定
与
相加时对每一分量按二进制法则（异或运算）进行
。
这样，一次渡河就是一个可取状态向量与一个可取运载向量相加，可取状态经过加法运算仍是一个可取状态，这种运算称为可取运算。
在上述规定下，问题转化为：
从初始状态
至少经过多少次（奇数次）可取运算才能转化为状态
8.2、算法设计：
8.2.1、规定A和B的每一分量相加时按二进制法则进行，这样一次渡河就是一个可取状态和一个可取运载相加，在判断和向量是否属于可取状态即可。
8.2.2、可以将可取状态及可取运载分别编成矩阵。
共分为五个m文件，一个主文件xduhe.m数，四个子文件分别为：
8.2.2.1、duhe（L,B,M,s）函数：
用来实现渡河总思路。
思路为：
将起始矩阵A分别与可取运载相加（使用二进制法则），判断相加后的矩阵C是否是（0，0，0，0），如果是，则渡河成功。
否则，用fuhe（C,M）函数判断C是否是可取状态，如果是，则打印并将C与初始矩阵合并成新矩阵，继续调用duhe.m函数。
8.2.2.2、fuhe（C,M）函数：
判断和矩阵C是否属于矩阵M，如果是，则返回1，否则返回0.
8.2.2.3、Panduan（S）函数：
判断S矩阵中是否有两个相同的状态，即行向量。
如果有，则返回0，否则返回1.
8.2.2.4、print（K,C,s）函数：
打印相应的状态。
8.3、程序代码：
8.3.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）;
8.3.2、duhe.m文件：
functionduhe（L,B,M,s）;
[h,l]=size（L）;
fork=s:
h
fori=1:
4
C=mod（L（k,:
）+B（i,:
）,2）;
ifC==[0,0,0,0]
print（B（i,:
）,C,s）;
fprintf（'
渡河成功\n\n'
）;
break;
elseiffuhe（C,M）==1
S=[L;
C];
ifPanduan（S）==1
duhe（S,B,M,s+1）;
else
此渡河方案不可行\n\n'
end
end
8.3.3、fuhe.m文件：
functiony=fuhe（C,M）
y=0;
fori=1:
8
if（C==M（i,:
））
y=1;
8.3.4、Panduan.m文件：
functionz=Panduan（S）
z=1;
[m,n]=size（S）;
forp=1:
m
forq=（p+1）:
ifS（p,:
）-S（q,:
）==[0,0,0,0]
z=0;
8.3.5、print.m文件：
functionprint（K,C,s）
fprintf（'
第%d次渡河:
'
s）;
ifK
（1）==1
人,'
ifK
（2）==1
猫,'
ifK（3）==1
鸡,'
ifK（4）==1
米,'
ifC
（1）==0
从左岸到达右岸\n'
else
从右岸回到左岸\n'
8.4、模型结论
在matlab中运行，结果如下：
从运行结果可以看出，共有两种运送方案：
1、人先带鸡过河，然后人再回来，把米带过河，然后把鸡运回河岸，人再把猫带过河，最后人回来把鸡带过去。
2、人先带鸡过河，然后人再回来，把猫带过河，然后把鸡运回河岸，人再把米带过河，最后人回来把鸡带过去。
8.5、收获与不足：
复习和加深了对matlab的学习，见识了MATLAB7.10.0（R2010a）的厉害，引发了我对数学建模的强大兴趣。
而且，利用MATLAB可以非常容易而且很直观地得出问题的解决方案，从而在不断深化对问题认识的同时，把问题普遍化。
但是这个问题的求解过程是请教了师姐才得以完成的。
九、“商人过河”的算法步骤和matlab求解过程
另外，由于本次数学建模的启发，我们组根据老师上课讲的“商人过河”的算法步骤，用matlab编程出程序，求解过程如下：
9.1、模型建立：
此问题可视为一个
多步决策
多步决策:
决策过程难以一次完成，而要分步优化，最后获取一个全局最优方案的决策方法称为多步决策。
问题：
每一步就是一次渡河，每次渡河就是一次状态转移。
用三维变量
表示状态：
------商人数
的取值范围：
{0，1，2，3}；
------随从数
------船
{0,1}。
那么安全状态（可取向量）可表示为：
安全状态：
商人们安全是指在两岸都安全，故当x=0,3时，y=0,1,2,3，而当x=1,2时,此岸要求x≥y,对岸要求3-x≥3-y,综合即x=y；
（3,3,1）
（3,2,1）
（3,1,1）
（2,2,1）
（3,0,1）
（0,3,1）
（0,2,1）
（1,1,1）
（0,1,1）
（3,2,0）
（3,1,0）
（2,2,0）
（3,0,0）
（0,3,0）
（0,2,0）
（1,1,0）
（0,1,0）
（0,0,0）
这就是此问题的数学模型。
9.2、模型求解：
这样问题要求由（3，3，1）变到（0，0，0）的一条道路。
根据题意，状态转移时要满足一定的规则：
1.Z从1变为0与从0变为1交替进行；
2.当Z从1变为0时，即船从此岸到对岸，此岸人数减少1或2个；
即（x,y,1）→（u,v,0）时,u≤x,v≤y,u+v=x+y-1oru+v=x+y-2；
3.当Z从0变为1时，即船从对岸到此岸，此岸人数增加1或2个；
即（x,y,0）→（u,v,1）时,u≥x,v≥y,u+v=x+y+1oru+v=x+y+2；
4.
不重复已出现过的状态，如（3,3,1）→（3,1,0）→（3,3,1）；
9.3、matlab求解：
输入下面的语句将出现结果：
（运行结果和预期结果一样）
……
十、参考文献：
10.1、周义仓、赫孝良《数学建模实验》，西安交通大学出版社。
10.2、姜启源、谢金星、叶俊《数学模型》（第四版），高等教育出版社。
10.3、刘锋
《数学建模
》
南京大学出版社
2005年9月等。
升级会员 