人猫鸡米渡河问题的数学模型.doc

. .人猫鸡米渡河问题的数学模型摘要：人带着猫、鸡、米过河,从左岸到右岸,船除了需要人划之外〔船除了要载人外,只能载猫、鸡、米三者之一,而当人不在场时猫要吃鸡、鸡要吃米本文将设计一个安全过河方案,使渡河次数尽量地少模仿"商人过河"的模型设计出新的数学模型关键字：穷举法,Matlab运算求解一、问题的提出课本P19.T5:模仿"商人过河"模型,做下面游戏：人带着猫、鸡、米过河,船除需要人划之外,至多能载猫、鸡、米三者之一,而当人不在场时猫要吃鸡、鸡要吃米设计一个过河方案,建立数学模型,并使渡河次数尽量地少二、问题的分析因为这是个简单问题,研究对象少,所以可以用穷举法,简单运算即可解题此问题是从状态向量A〔1,1,1,1经过奇数次运算向量B变为状态向量A〔0,0,0,0的状态转移过程为什么是奇数次？我们注意到过河有两种,奇数次的为从左岸到右岸,而偶数的为右岸回到左岸,因此得到下述转移过程,所以最后应该是过河完成时状态转移数为奇数次三、问题的假设1.1：假设船除了载人之外,至多只能载猫、鸡、米三者之一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、可取运算：规定与相加时对每一分量按二进制法则〔异或运算进行这样,一次渡河就是一个可取状态向量与一个可取运载向量相加,可取状态经过加法运算仍是一个可取状态,这种运算称为可取运算在上述规定下,问题转化为：从初始状态至少经过多少次〔奇数次可取运算才能转化为状态。

六、模型的求解如果一个状态是可取的就打,否则就打,虽然可取但已重复就打,于是问题可用穷举法解答如下：1〔2〔3〔4 〔4〔5 〔5〔6 〔7第7步已经出现了状态,说明经7次运载即可,其过程为：因此,该问题的最优方案有2种：1、人先带鸡过河,然后人再回来,把米带过河,然后把鸡运回河岸,人再把猫带过河,最后人回来把鸡带过去2、人先带鸡过河,然后人再回来,把猫带过河,然后把鸡运回河岸,人再把米带过河,最后人回来把鸡带过去七、模型的评价7.1、优点：本算法将研究对象用四维向量中的分量用0,1表示,运用穷举法找出所有可取状态向量再用一些基础可取运算方法将结果列出来再以图形表示出来模型简单,切合实际,易于理解,整个过程易懂合理 7.2、缺点：由于问题的求解没有使用LINGO,LINDO或MATLAB软件,当状态和决策过多时,采用上述方法求解显得繁琐,容易出错,所以下面给出此问题的matlab求解过程7．3、推广：正如课本上的商人们安全过河问题,当商人和随从人数增加或小船的容量加大时,靠逻辑思考就有些困难了,而适当地设置状态和决策,确定状态转移率,建立多步决策模型,仍可方便有效地求解此类型问题。

八、mathlab求解过程8.1、 模型假设与建立：8.1.1、由上可知,可取状态向量共有10个,即：8.1.2、 可取运载B有4个 ：〔1,1,0,0、 〔1,0,1,0、 〔1,0,0,1、 〔1,0,0,08.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是否是可取状态,如果是,则打印并将C与初始矩阵合并成新矩阵,继续调用duhe.m函数8.2.2.2、fuhe函数：判断和矩阵C是否属于矩阵M,如果是,则返回1,否则返回0.8.2.2.3、Panduan〔S函数：判断S矩阵中是否有两个相同的状态,即行向量如果有,则返回0,否则返回1.8.2.2.4、print函数：打印相应的状态。

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;8.3.2、duhe.m文件：function duhe;[h,l]=size;for k=s:h for i=1:4 C=mod+B,2>; if C==[0,0,0,0] print,C,s>; fprintf<'渡河成功\n\n'>; break; else if fuhe==1 print,C,s>; S=[L;C]; if Panduan==1 duhe; else fprintf<'此渡河方案不可行\n\n'>; end end end endend8.3.3、fuhe.m文件：function y=fuhey=0;for i=1:8 if> y=1; break; endend8.3.4、Panduan.m文件：function z=Panduanz=1;[m,n]=size;for p=1:m for q=:m if S-S==[0,0,0,0] z=0; break; end endend8.3.5、print.m文件：function printfprintf<'第%d次渡河:',s>;if K<1>==1 fprintf<'人, '>;endif K<2>==1 fprintf<'猫, '>;endif K<3>==1 fprintf<'鸡, '>;endif K<4>==1 fprintf<'米, '>;endif C<1>==0 fprintf<'从左岸到达右岸\n'>;else fprintf<'从右岸回到左岸\n'>;end8.4、模型结论在matlab中运行,结果如下：从运行结果可以看出,共有两种运送方案：1、 人先带鸡过河,然后人再回来,把米带过河,然后把鸡运回河岸,人再把猫带过河,最后人回来把鸡带过去。