人狼羊草过河问题数学建模

数学建模——过河问题一（人狼羊草）

数 学 建 模

——题目：过河问题一（人狼羊草）

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

数学建模——过河问题一（人狼羊草）

1. （1，1，1，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，1，1） × =（0，1，0，1） √ =（0，1，1，0） × =（0，1，1，1） ×

2. （0，1，0，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，0，0，1） × =（1，1，1，1） × =（1，1，0，0） × =（1，1，0，1） √

（1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，0，1） √ =（0，1，1，1） × =（0，1，0，0） √ =（0，1，0，1） √ 3. （1，1，0，1） +

4.1 （0，1，0，1）与上述第二步重复，必定不是最优解，故不用进行下去。

4.2 （0，0，0，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，1，0，1） √ =（1，0，1，1） √ =（1，0，0，0） × =（1，0，0，1） ×

4.2.1 （ 1，1，0，1 ）与上述第3步重复，必定不是最优解，不用进行下去

6 / 15

数学建模——过河问题一（人狼羊草）

4.2.2 （1，0，1，1） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，1，1，1） × =（0，0，0，1） √ =（0，0，1，0） √ =（0，0，1，1） ×

4.2.2.1 （0，0，0，1）与上述4.2重复，必定不是最优解，不用进行下去

4.2.2.2 （0，0，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，1，1，0） √ =（1，0，0，0） × =（1，0，1，1） √ =（1，0，1，0） √

4.2.2.2.1 （1，0，1，1）与上述4.2.2重复，必定不是最优解，不用进行下去

4.2.2.2.1 （1，0，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，1，1，0） × =（0，0，0，0） √ =（0，0，1，1） × =（0，0，1，0） √

已得最终状态向量（0，0，0，0），过程无重复，此即为最优解。

（1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（1，0，0，0） × =（1，1，1，0） √ =（1，1，0，1） √ =（1，1，0，0） × 4.3 （0，1，0，0） +

7 / 15

数学建模——过河问题一（人狼羊草）

4.3.1 （ 1，1，0，1 ）与上述第3步重复，必定不是最优解，不用进行下去

4.3.2 （1，1，1，0） + （1，1，0，0） （1，0，1，0） （1，0，0，1） （1，0，0，0） =（0，0，1，0） √ =（0，1，0，0） √ =（0，1，1，1） × =（0，1，1，0） ×

4.3.2.1 （0，1，0，0）与上述4.3重复，必定不是最优解，不用进行下去

4.3.2.2 （ 0，0，1，0 ）与按上述4.2.2.2步骤进行即可得相同的最优解 模型的解 最终结果：

解一： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，1，0，0）→D5（ 1，1，1，0 ）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0）

8 / 15

数学建模——过河问题一（人狼羊草）

解二： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，0，0，1）→D5（1，0，1，1）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0） n=7 解法(2):图解法

绘图要求：（1）连线两端必须是允许状态向量；

（2）相邻两点（通过一次运载得到的点）相连； （3）从（1，1，1，1）至（0，0，0，0）结束。 连线如下：

（1，1，1，1） （1，0，1，0） （0，0，0，0） （0，0，0，1） （1，1，0，1） （0，0，1，0） （1，0，1，1） （1，1，1，0） （0，1，0，0） （0，1，0，1）

最终结果：

9 / 15

数学建模——过河问题一（人狼羊草）

模型的解

解一： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，1，0，0）→D5（ 1，1，1，0 ）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0）

解二： D1（1，1，1，1）→D2（0，1，0，1）→D3（ 1，1，0，1 ）→D4（0，0，0，1）→D5（1，0，1，1）→D6（ 0，0，1，0 ）→D7（1，0，1，0）→D8（0，0，0，0） n=7

与解法（1）解相同

五、计算机编程法（C语言）

要解决这个问题就要使过河时载两个过河，返回时尽量只有一个回来。用一个字符串数组来存人，狼，羊，草；下标依次为0，1，2，3；但他们都有河这边和那边两种状态；为方便则定义一个结构，只含一个int型变量n；当在河这边时n设为0；在河那边时n设为1。由于每次过河与返回都要考虑狼能否吃羊或羊能否吃草；则需要一个函数来判断每次选择是否满足条件。 源代码：

10 / 15

数学建模——过河问题一（人狼羊草）

#include\typedef struct node {int n; }node;

int p(node *a)

int i,j=1; if(a->n==1) {for(i=1;i<3;i++)

if((a+i)->n==0&&(a+i+1)->n==0) {j=0;break;} }

if(a->n==0) {for(i=1;i<3;i++)

if((a+i)->n&&(a+i+1)->n) {j=0;break;} }

return j; }

int main() {

11 / 15

数学建模——过河问题一（人狼羊草）

int i,k=0,m=0,l,j=0,q;

char str[4][7]={\人\狼\羊\草\node a[4]; for(i=0;i<4;i++) (a+i)->n=0; while(1) {

a[0].n=1; for(l=1;l<4;l++) {

if(l==j) {j=0;continue;} if((a+l)->n==0) {

(a+l)->n=1; if(p(a)) break; else (a+l)->n=0; } }

printf(\过河; \

12 / 15

数学建模——过河问题一（人狼羊草）

for(q=0;q<4;q++) if((a+q)->n) m=1; else {m=0;break;} if(m) break; a->n=0; if(p(a)==0) { k=1;

for(j=1;j<4;j++) {

if(j==l) {l=0;continue;} if((a+j)->n==1) {

(a+j)->n=0; if(p(a)) break; else (a+j)->n=1; } } }

13 / 15

数学建模——过河问题一（人狼羊草）

if(k) {printf(\返回\\n\else printf(\返回\\n\}

printf(\return 0; }

图为计算机运行结果

六、参考文献

1、数学建模精讲精练，哈尔滨工程大学出版社，沈继红主编，2007 2、数学建模，哈尔滨工业大学出版社，白凤山等主编，2003

14 / 15

数学建模——过河问题一（人狼羊草）

3，数学模型，高等教育出版社，姜启源主编，1993 4、C语言程序设计教程，电子工业出版社，凌云主编，2008 5、数学建模，浙江大学出版社，杨启帆主编，1999 6、数学建模导论，北京邮电大学出版社，陈理荣主编，2000

15 / 15

本文来源：https://www.bwwdw.com/article/o077.html