2012-03-21-数学建模B实验题目人猫鸡米.docVIP

人、猫、鸡、米安全过河问题 摘??? 要? 研究目的：本文主要对数学建模基础模型跟“商人过河”类似简单问题：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。试设计一个过河方案，建立数学模型，并使渡河次数尽量地少？模仿“商人过河”的模型设计出新的数学模型。 方法：用穷举法算出，用图形表述出过程及结果。 一、问题的提出 模仿”商人过河”模型，做下面游戏：人带着猫、鸡、米过河，船除需要人划之外，至多能载猫、鸡、米三者之一，而当人不在场时猫要吃鸡、鸡要吃米。设计一个过河方案，建立数学模型，并使渡河次数尽量地少。? 二、问题的分析 因为这是个简单问题，研究对象少所以可以用穷举法，简单运算和图论即可解题。 从状态（1,1,1,1）经过奇数次运算变为状态（0,0,0,0）的状态转移过程为什么是奇数次？我们注意到过河有两种，奇数次的为从南岸到北岸，而偶数次的为北岸回到南岸，因此得到下述转移方程，所以最后应该是事件结束时状态转移数为奇数次。 三、基本假设： 3,1假设船，划船的人外至多能载猫、鸡、米三者之一。 3,2当人不在场时，猫一定会吃鸡、鸡一定会吃米。 ? 四、定义符号说明： 我们将人，狗，鸡，米依次用四维向量中的分量表示，当一物在此岸时，相应分 量记为1，在彼岸时记为0.如向量（1,0,1,0）表示人和鸡在此案，狗和米在彼岸，并将这些向量称为状态向量。 五、模型的建立： 我们将人，狗，鸡，米依次用四维向量中的分量表示，！即（人,?狗,?鸡,?米）。 5.1 状态向量：各分量取1表示南岸的状态，例如（1，1，1，1）表示它们都在南岸，（0，1，1，0）表示狗，鸡在南岸，人，米在北岸；由于问题中的限制条件，有些状态是允许的，有些状态是不允许的。凡问题可以允许存在的状态称为可取状态。对本问题来说，可取状态向量可以用穷举法列出来： （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）. 5.2 运算向量：将船的一次运载也可用向量表示，即运算向量。当一物在船上时相应分量记为1，否则记为0，如（1,1,0,0）表示人和狗在船上，即人带狗过河。本问题的运算向量共有四个： （1,?1,?0,?0），（1,?0,?1,?0），（1,?0,?0,?1），（1,?0,?0,?0） ??? 5.3 简单运算：一次过河就是一状态向量和运算向量的加法，在加法运算中对每 一分量采用二进制，即：0+0=0,1+0=0+1=1,1+1=0（如令D为允许决策集合，D={?(1,?x,?y,?z)?:??x+y+z=0?或?1}）?于是，人，狗，鸡，米过河问题就转化为：找出从状态（1,1,1,1）经过奇数次运算变为状态（0,0,0,0）的状态转移过程。 5.4 用图论方法解决这个问题，我们把这十个可取状态，当且仅当某个可取状态经过运算向量而仍为可取状态，就连一条线，从而构成图一所示。经过数次互相转换后出现（0,0,0,0）.于是，问题变为在图中找一条从顶点（1,1,1,1）到（0,0,0,0）的路径，每条路径就是一个解，从图二可知有二解，它们是等优的。 六、模型的求解： （1,1,1,1）???????????????（0,0,0,0） （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） ????? ?图1：个状态的可取转 （0，0，0，1）?????????? （1，0，1，1） ?（1，1，1，1）? ???????（0，1，0，1）???? ???（1，1，0，1）??????????? ???????????????（0，0，1，0）?????? ?（1，0，1，0）?????? ???（0，0，0，0） ?（0，1，0，0）??????????????????? （1，1，1，0）????????????????? 图2：解决问题的必须路径图 ? 七、结果分析 从图看出有二解，分别是经过（0,0,0,1）到（0,0,0,0）和经过（0,1,0,0）到（0,0,0,0）而它们是等优的。 八、模型的评价与改进： 本算法将研究对象用四维向量中的分量表示运用穷举法找出所有可取状态向量再用一些基础运算方法将结果列出来再以图形表示出来。整个过程易懂合理。 这里用的是图论方法解题。可以用别的方法试试！ 致??? 谢