《人带猫鸡米过河问题》由会员分享，可在线阅读，更多相关《人带猫鸡米过河问题（2页珍藏版）》请在金锄头文库上搜索。
1、人带猫，鸡，米过河问题？姓名：刘浩学号：0504100105专业：统计学1，问题的提出模仿”商人过河”模型，做下面游戏：人带着猫、鸡、米过河，船除需要人 划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃 米。设计一个过河方案，建立数学模型，并使渡河次数尽量地少。2 问题的分析因为这是个简单问题，研究对象少所以可以用穷举法，简单运算和图论即可 解题。从状态（1,1,1,1）经过奇数次运算变为状态（0,0,0,0）的状态转移过程为 什么是奇数次？我们注意到过河有两种，奇数次的为从南岸到北岸，而偶数次的 为北岸回到南岸，因此得到下述转移方程，所以最后应该是事件结束时状态转移 数为奇
2、数次。3 基本假设：3,1 假设船，划船的人外至多能载猫、鸡、米三者之一。3,2 当人不在场时，猫一定会吃鸡、鸡一定会吃米。4 定义符号说明：我们将人，狗，鸡，米依次用四维向量中的分量表示，当一物在此岸时，相 应分量记为 1，在彼岸时记为 0.如向量（1,0,1,0）表示人和鸡在此案，狗和米在彼 岸，并将这些向量称为状态向量。5 模型的建立：我们将人，狗，鸡，米依次用四维向量中的分量表示，！即（人, 狗, 鸡, 米）。状态向量：各分量取1 表示南岸的状态，例如（1，1，1，1）表示它们都在 南岸，（0，1，1，0）表示狗，鸡在南岸，人，米在北岸；由于问题中的限制条 件，有些状态是允许的，有些状
3、态是不允许的。凡问题可以允许存在的状态称为 可取状态。对本问题来说，可取状态向量可以用穷举法列出来：(1, 1, 1, 1)，(1, 1, 1, 0)，(1, 1, 0, 1)，(1, 0, 1, 1)，(1, 0, 1, 0) (,0, 0, 0, 0)，(0, 0, 0, 1)，(0, 0, 1, 0)，(0, 1, 0, 0),(0,1,0,1).6 模型的求解：经过连线求解可以知道有以下图形：G(Q0)E咽(1 j 0F(0 * 0 0 G)A-* J-* C-* G-* D-* H-* E-*F ；上图又可以简化为： 既：7 结果分析从图看出有二解，分别是经过(0,0,0,1)到(0,0,0,0)和经过(0,1,0,0) 到(0,0,0,0)而它们是等优的。8 模型的评价与改进：本算法将研究对象用四维向量中的分量表示运用穷举法找出所有可取状态向 量再用一些基础运算方法将结果列出来再以图形表示出来。整个过程易懂合理。这里用的是图论方法解题。可以用别的方法试试！
