数学建模——过河问题一（人狼羊草）
数 学 建 模
——题目：过河问题一（人狼羊草）
1 / 15
数学建模——过河问题一（人狼羊草）
摘要 ........................................................................................... 3 一、问题的提出 ............................................................................... 3 二、问题分析及假设 ........................................................................ 4 三、模型的参数及符号 .................................................................... 5 四、模型及解 ................................................................................... 5 五、计算机编程法（C语言） ....................................................... 10 六、参考文献 ................................................................................. 14
2 / 15
数学建模——过河问题一（人狼羊草）
摘要
在本次数学建模中，我们主要讨论的是人狼羊草问题：一位渔民带了狼、羊、草，准备过河。可是小船每次只能容下渔民和一件物品。渔民不在时，狼会吃羊、羊会吃草。要求我们设计一个方案，使农夫可以无损失的过河。此过河问题可以视为一个多步决策过程，确定每一步的决策，达到过河的目标。而且，我们假设人不在时，狼或羊在农夫不在时不会自己跑掉或被人牵走且农夫会划船。于是我们得到一下集中状态：狼羊草人/， /狼羊草人， 狼羊人/草， 草/狼羊人， 狼草人/羊， 羊/狼草人， 羊草人/狼， 狼/羊草人， 羊人/狼草， 狼草/羊人。题目要求找出“狼羊草人/”到“/狼羊草人”的路径，本论文根据题目要求而讨论了人、狼、羊、草怎样安全过河的模型。提出了算法和计算机编程法两种解决问题的方法，并且通过计算机编程法得出了一种方法。
一、问题的提出
人、狼、羊、草均需过河，船需要人划，最多载一物。人不在时，狼吃羊、羊吃草，问如何过河？
这个问题可以简单的解释为：一位渔民带了狼、羊、草，准备过河。可是小船每次只能容下渔民和一件物品。另有一条件为，渔民不在时，狼会吃羊、羊会吃草。也就是说，狼与羊、羊与草、或狼羊草不能单独在一起。现要求为过河人提出某种过河的方法，使人、狼、羊、草都安全度过河且方法最简单为宜
3 / 15
数学建模——过河问题一（人狼羊草）
二、问题分析及假设
过河问题相当于状态的转移。初状态是人，狼，羊，草均在此岸，目标终状态是人，狼，羊，草均在对岸。
（此岸）状态向量：用四维向量（人，狼，羊，草）表示人，狼，羊，草各自的状态，记“在此岸”时各分量为“1”，否则记为“0”。例如：（1，1，1，1）表示人，狼，羊，草均在此岸，（0，0，0，0）表示人，狼，羊，草均在对岸。
允许状态向量：满足系统限定条件的状态向量。穷举所有允许状态向量如下：（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，1），（1，0，1，0），（0，1，0，1），（0，0，0，1），（0，0，1，0）（0，1，0，0），（0，0，0，0）。
运载状态向量：用四维向量（人，狼，羊，草）表示他们各自被运载的情况，记“被运载”时各分量为“1”，否则记为“0”。例如：（1，1，0，0）表示被运载的是人和狼，又如（1，0，1，0）表示被运载的是人和羊。
允许运载向量：满足系统限定条件下的运载向量。穷举所有允许运载向量如下：（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，1）。
转移：一允许状态向量逻辑加以允许运载向量。 状态转移方程：原状态⊕运载=现状态 运算规则：1+1=0，1+0=1，0+1=1，0+0=0。
允许运载方式：若可取状态向量 + 可取运载向量 = 可取状态向量，
4 / 15
数学建模——过河问题一（人狼羊草）
则此运载为可取运载方式，其中“+”为按上述运算规则定义的运算符。
三、模型的参数及符号
（1）S：表示所有允许状态向量的集合
S={（1，1，1，1），（1，1，1，0），（1，1，0，1），（1，0，1，
1），（1，0，1，0），（0，1，0，1），（0，0，0，1），（0，0，1，0），（0，1，0，0），（0，0，0，0）}
（2）D：表示所有允许运载向量
D={（1，0，0，0），（1，1，0，0），（1，0，1，0），（1，0，0，
1）}
（3）Sk：表示第K步允许状态向量 （4）Dk：表示第K步允许运载向量 （5）k：表示第几步，k=1,2,3…n
四、模型及解
模型：在计算规则“1+1=0，1+0=1，0+1=1，0+0=0”下， 且满足Sk + Dk = Sk+1，问题：（1）求Dk属于D，使得Sk+1属于S;（2）求最优的n。其中：初始条件S=（1，1，1，1），最终状态Sn+1=（0，0，0，0）
解法（1）：算法
5 / 15