人猫鸡米过河问题.doc

重庆交通大学学生实验报告实验课程名称数学模型开课实验室双福校区计算机中心学院河海学院 12级地信专业班 1班学生姓名刘静学号 631203080128 开课时间 201 3至 201 4 学年第 2 学期综合评分依据实验成绩实验到课情况论文表述的清晰度和结构的完整性所构建数学模型及其求解方法的正确性数学建模的创新性实验指导教师官礼和人猫鸡米过河问题(1) 摘要文中参考教材中商人过河问题及相关网络资源详细探讨了人猫鸡米过河问题,运用初等数学建模的方法通过穷举法、图解法、四维向量运算等方法求得了两种等优的最优渡河方案。(2) 问题重述模仿 节“商人过河”问题中的状态转移模型,做下面这个众所周知的游戏: 人带着猫、鸡、米过河,船除需要人划之外,至多能载猫、鸡、米三者之一,而当人不在场时猫要吃鸡、鸡要吃米。设计一个过河方案,建立数学模型,并使渡河次数尽量地少。(3) 基本假设及符号说明基本假设 ,至多能载猫、鸡、米三者之一; ; 、猫、鸡、米只能通过船从此岸到达彼岸; :人必须靠自己划船过河,也没有其它人可以帮助人照看这三样东西; 5. 当人不在场时猫要吃鸡、鸡要吃米,猫不会因为胃口不好等原因而不吃鸡, 鸡也不会因为生病等原因而不吃米。符号说明 x=(a1,a2,a3,a4 )分别表示人猫鸡米的状态, ai=0 表示对应对象在此岸 or1表示对应对象在彼岸; y=(b1,b2,b3,b4 )分别表示人猫鸡米是否在船上转移中 bi=0 表示对应对象不在船上 or1表示对应对象在船上(4) 模型的建立向量 x、y需满足的条件: 因为当人不在场时猫要吃鸡、鸡要吃米, 所以当a1+a2+a3+a4=1 时 a3=1 ; 当a1+a2+a3+a4=2 时 a2不等于 a3, a3不等于 a4; 当a1+a2+a3+a4=3 时 a1不等于 0; 因为只有人会划船,且人至多只能带一种东西在船上所以 b1=1, b1+b2+b3+b4<=2 用穷举法求出所有满足以上条件的 x A(0,0,0,0),F(1,1,1,1), B(0,1,0,1),G(1,0,1,0), C(0,0,0,1),H(1,1,1,0), D(1,0,1,1),I(0,1,0,0), E(1,1,0,1),J(0,0,1,0) ; 其中( 0,0,0,0 )为初始状态,(1,1,1,1 )为目标状态及满足条件的 y(1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1) 通过 x与y向量的运算,使 x由初始状态 A(0,0,0,0 ) 通过允许状态 B(0,1,0,1),G(1,0,1,0), C(0,0,0,1),H(1,1,1,0), D(1,0,1,1),I(0,1,0,0), E(1,1,0,1),J(0,0,1,0) 达到目标状态 F(1,1,1,1 )(5) 模型的求解运算法则: 人猫鸡米如果通过一次转移之后都将到达对岸,通过两次转移后都将回到原来的位置,先忽略其它元素,以猫 a2代替 x,b2代替 y为例: 很明显,初始 a2=0 ,b2=0 ; 当b2=1 时通过运算 a2=a2+b2=1 ,即 0+1=1 通过一次转移猫到达彼岸再次进