人带猫鸡米过河问题.doc

人带猫,鸡,米过河问题?
姓名:刘浩
学号:0504100105
专业:统计学
1,问题的提出
模仿”商人过河”模型,做下面游戏:人带着猫、鸡、米过河,船除需要人划之外,至多能载猫、鸡、米三者之一,而当人不在场时猫要吃鸡、鸡要吃米。设计一个过河方案,建立数学模型,并使渡河次数尽量地少。 
2问题的分析
因为这是个简单问题,研究对象少所以可以用穷举法,简单运算和图论即可解题。
从状态(1,1,1,1)经过奇数次运算变为状态(0,0,0,0)的状态转移过程为什么是奇数次?我们注意到过河有两种,奇数次的为从南岸到北岸,而偶数次的为北岸回到南岸,因此得到下述转移方程,所以最后应该是事件结束时状态转移数为奇数次。
3基本假设:
3,1假设船,划船的人外至多能载猫、鸡、米三者之一。
3,2当人不在场时,猫一定会吃鸡、鸡一定会吃米。
4定义符号说明:
我们将人,狗,鸡,米依次用四维向量中的分量表示,当一物在此岸时,相应分
量记为1,(1,0,1,0)表示人和鸡在此案,狗和米在彼岸,并将这些向量称为状态向量。
5 模型的建立:
我们将人,狗,鸡,米依次用四维向量中的分量表示,!即(人, 狗, 鸡, 米)。
状态向量:各分量取1表示南岸的状态,例如(1,1,1,1)表示它们都在南岸,(0,1,1,0)表示狗,鸡在南岸,人,米在北岸;由于问题中的限制条件,有些状态是允许的,有些状态是不允许的。凡问题可以允许存在的状态称为可取状态。对本问题来说,可取状态向量可以用穷举法列出来:
(1, 1, 1, 1),(1, 1, 1, 0),(1, 1, 0, 1),(1, 0, 1,