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

数学建模——过河问题一（人狼羊草）1/15数学建模——题目：过河问题一（人狼羊草）数学建模——过河问题一（人狼羊草）2/15摘要...........................................................................................3一、问题的提出...............................................................................3二、问题分析及假设........................................................................4三、模型的参数及符号....................................................................5四、模型及解...................................................................................5五、计算机编程法（C语言）.......................................................10六、参考文献.................................................................................14数学建模——过河问题一（人狼羊草）3/15摘要在本次数学建模中，我们主要讨论的是人狼羊草问题：一位渔民带了狼、羊、草，准备过河。可是小船每次只能容下渔民和一件物品。渔民不在时，狼会吃羊、羊会吃草。要求我们设计一个方案，使农夫可以无损失的过河。此过河问题可以视为一个多步决策过程，确定每一步的决策，达到过河的目标。而且，我们假设人不在时，狼或羊在农夫不在时不会自己跑掉或被人牵走且农夫会划船。于是我们得到一下集中状态：狼羊草人/，/狼羊草人，狼羊人/草，草/狼羊人，狼草人/羊，羊/狼草人，羊草人/狼，狼/羊草人，羊人/狼草，狼草/羊人。题目要求找出“狼羊草人/”到“/狼羊草人”的路径，本论文根据题目要求而讨论了人、狼、羊、草怎样安全过河的模型。提出了算法和计算机编程法两种解决问题的方法，并且通过计算机编程法得出了一种方法。一、问题的提出人、狼、羊、草均需过河，船需要人划，最多载一物。人不在时，狼吃羊、羊吃草，问如何过河？这个问题可以简单的解释为：一位渔民带了狼、羊、草，准备过河。可是小船每次只能容下渔民和一件物品。另有一条件为，渔民不在时，狼会吃羊、羊会吃草。也就是说，狼与羊、羊与草、或狼羊草不能单独在一起。现要求为过河人提出某种过河的方法，使人、狼、羊、草都安全度过河且方法最简单为宜数学建模——过河问题一（人狼羊草）4/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。允许运载方式：若可取状态向量+可取运载向量=可取状态向量，数学建模——过河问题一（人狼羊草）5/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）：算法数学建模——过河问题一（人狼羊草）6/154.1（0，1，0，1）与上述第二步重复，必定不是最优解，故不用进行下去。4.2.1（1，1，0，1）与上述第3步重复，必定不是最优解，不用进行下去（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.2（0，0，0，1）+=（1，1，0，1）√=（1，0，1，1）√=（1，0，0，0）×=（1，0，0，1）×（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）3.（1，1，0，1）+=（0，0，0，1）√=（0，1，1，1）×=（0，1，0，0）√=（0，1，0，1）√（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）2.（0，1，0，1）+=（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）1.（1，1，1，1）+=（0，0，1，1）×=（0，1，0，1）√=（0，1，1，0）×=（0，1，1，1）×数学建模——过河问题一（人狼羊草）7/154.2.2.1（0，0，0，1）与上述4.2重复，必定不是最优解，不用进行下去4.2.2.2.1（1，0，1，1）与上述4.2.2重复，必定不是最优解，不用进行下去已得最终状态向量（0，0，0，0），过程无重复，此即为最优解。（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.3（0，1，0，0）+=（1，0，0，0）×=（1，1，1，0）√=（1，1，0，1）√=（1，1，0，0）×（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.2.2.2.1（1，0，1，0）+=（0，1，1，0）×=（0，0，0，0）√=（0，0，1，1）×=（0，0，1，0）√（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.2.2.2（0，0，1，0）+=（1，1，1，0）√=（1，0，0，0）×=（1，0，1，1）√=（1，0，1，0）√（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.2.2（1，0，1，1）+=（0，1，1，1）×=（0，0，0，1）√=（0，0，1，0）√=（0，0，1，1）×数学建模——过河问题一（人狼羊草）8/154.3.1（1，1，0，1）与上述第3步重复，必定不是最优解，不用进行下去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）（1，1，0，0）（1，0，1，0）（1，0，0，1）（1，0，0，0）4.3.2（1，1，1，0）+=（0，0，1，0）√=（0，1，0，0）√=（0，1，1，1）×=（0，1，1，0）×数学建模——过河问题一（人狼羊草）9/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）（1，1，0，1）（1，0，1，1）（1，1，1，0）（0，0，0，0）（0，0，0，1）（0，0，1，0）（0，1，0，0）（0，1，0，1）数学建模——过河问题一（人狼羊草）10/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。由于每次过河与返回都要考虑狼能否吃羊或羊能否吃草；则需要一个函数来判断每次选择是否满足条件。源代码：数学建模——过河问题一（人狼羊草）11/15#includestdio.htypedefstructnode{intn;}node;intp(node*a)inti,j=1;if(a-n==1){for(i=1;i3;i++)if((a+i)-n==0&&(a+i+1)-n==0){j=0;break;}}if(a-n==0){for(i=1;i3;i++)if((a+i)-n&&(a+i+1)-n){j=0;break;}}returnj;}intmain(){数学建模——过河问题一（人狼羊草）12/15inti,k=0,m=0,l,j=0,q;charstr[4][7]={人,狼,羊,草};nodea[4];for(i=0;i4;i++)(a+i)-n=0;while(1){a[0].n=1;for(l=1;l4;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(%s,%s过河;,str[m],str[l]);数学建模——过河问题一（人狼羊草）13/15for(q=0;q4;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;j4;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;}}}数学建模——过河问题一（人狼羊草）14/15if(k){printf(%s,%s返回