当前位置：文档之家 › 人样狼草过河数学建模

人样狼草过河数学建模

  • 格式：doc
  • 大小：84.00 KB
  • 文档页数：8
queue[rear]=Status; rear=(rear+1)%16;//入队
while(front!=rear){
Status=queue[front];front=(front+1)%16;//出队
visited[Status]=1; //访问
for(j=0;j<4;j++){
nextStatus=Status^choice[j]; //从curStatus状态到下一状态nextStatus
人然后是B状态，B状态表示用船渡河过程中表示船内运载的状况，当一物在船上时用1表示，不再船上则用0表示，当满足问题条件的运载称为可取运载，当不满足条件的运载则是不可取运载，如B1（1，1，0，0）表示人狼崽船上，但它不是可取状态，同样B2（1，0，1，1）也不是可取状态，应为船不能载三物。
我们可以通过穷举法得到可取状态向量：
(7)1 (1 , 1 ,0 , 0 )=(1,0,0,1 ) !
(0,1,0,1 ) + (1, 0, 1, 0）=(1,1,1,1) +
(1, 0 , 0 , 1）=(1,1,0,0) !
(1 , 0 ,0 ,0 )=(1,1,0,1) *
取（1，0，1，1）计算：
(4)2 (1 , 1 ,0 , 0 )=(0,1,1,1) !
三解法
1.穷举法
注：在得到的状态后面的标示符中，“！”表示该状态不可取，“+”表示该状态可取，“*”表示该状态已经出现过，为重复状态。
（1）（1，1，0，0）=（1,1,0,0）!
(0,0,0,0) +（1，0，1，0）=（1,0,1,0）+
（1，0，0，1）=（1,0,0,1）!
(1, 0, 0, 0) =（1,0,0,0）!
建模
状态转移方程：原状态㈩运载＝现状态
一可取状态向量㈩可取运载向量，称之为过河。
其中㈩运算方式为“1+1＝0，1+0＝1，0+1＝1，0+0＝0”。
二、模型
在规则“1+1＝0，1+0＝1，0+1＝1，0+0＝0”下，
试求从最初可取状态向量（0，0，0，0）经过N步到最终状态向量（1，1，1，1）的可取转移方式。
课程设计报告
课程名称：数学建模
设计题目：人狼羊草过河问题
姓名学号：马高松（）
易文辉（）
陈邦生（）
指导老师：李沐春
完成时间：2010年5月8日
问题的提出
在河的一岸，人、狼、羊、草、均要过河，船需人划，而且最多载一物，当人不在时，狼会吃羊，羊会吃草；试安排人狼羊草安全渡河。
一问题的分析
人带着狼、羊和草，身处河的一岸。他要把这些东西全部运到彼岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外船必须有人划。而且，因为狼能吃羊，而羊爱吃草，所以人不能留下羊和草或者狼和羊单独在河的一边。以下是解决方案：
return 1;//1表示安全，0表示不安全
}
//过河，使用广度优深算法遍历
int crossRiver(int result[]){
int Status,nextStatus,choice[]={8,9,10,12};//农夫从某一状态出发，有4种走法
int queue[16],front,rear;//定义循环队列
(1, 0 , 0 , 1）=(1,0,0,0) !
(1 , 0 ,0 ,0 )=(1,0,0,1) !
得到的可取状态和（5）1步骤一样，故运算（6）2、（7）2应该和（6）1、（7）1一样。所以总共可以通过七步运算使得人、狼、羊、草安全过河。
2.图解法
四、算法实现
1.问题分析
完成了上面的准备工作，要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示人狼羊草的位置。例如用0表示人或者某物在河的南岸，1表示在河的北岸。因此整数3(其二进制表示为0011)表示人和狼在河的南岸，而羊和草在河的北岸。
整个过程中我们把该过程分为两种状态A和B，在各状态中，将人羊狼草用一个四维向量表示，A状态表示人羊狼草在河的左右岸的状态，当一物在左岸时，用分量0表示，当一物在右岸时，用分量1表示，例如状态A1(1,1,0,1)表示人羊草在河的右岸，狼崽河左岸，根据题中的要求，有些状态时允许的，有些状态是不允许的，这就牵涉到该方案的安全性，于是我们规定由条件允许存在的状态我们称之为可取状态，比如A1(0,1,0,1)是一个可取状态，而A2(0,0,1,1)则是一个不可取状态，因为他表示羊草在河的右岸，是不可取的；
for(i=0,j=0;j<16;j++){
if(result[j]>=0){
cout<<"第"<<i<<"步:\t"<<name[result[j]]<<endl;
现在的问题变成：
从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态通过人（可以带一样东西）划船过河的动作到达。
2.算法选择
求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。
五、程序代码
#include<iostream>
using namespace std;
int man(int n){
return (0!=(n & 8));//判断农夫在不在，如果返回1，则表示农夫在。
}
int wolf(int n){
return (0!=(n & 4));
}
int sheep(int n){
if(visited[nextStatus]==0 && isSafe(nextStatus)){
queue[rear]=nextStatus; rear=(rear+1)%16;//入队
route[nextStatus]=Status;//仅表示从Sattus可以走到nextStatus
//如route[10]=0,意即从0000有路可走到1010
(0,0 ,1,0 ) + (1, 0, 1, 0）=(1,0,0,0) !
(1, 0 , 0 , 1）=(1,0,1,1) +
(1 , 0 ,0 ,0 )=(1,0,1,0) *
第三步中得到的结果有两个可取状态，故应分别计算
先取（1，1，1，0）计算：
(4)1 (1 , 1 ,0 , 0 )=(0,0,1,0) *
广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。
要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里。由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。
}
}
}
//处理路径表:从路径表中反推（从最终步-->开始步）
i=15;//最后一步
if(route[i]==-1) { //若没有方法可以走到1111，则任务失败。
cout<<"过河失败!"<<endl;
return 0;
}
for(j=15;route[i]!=-1 && i>=0;j--){ //route[i]!=-1相当于那一步走不通，那就不用选取了
1人不在时： 三个全不在的 （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）
一共有10种状态。
(1,1 ,1,0 ) +(1, 0, 1, 0）=(0,1,0,0) +
(1, 0 , 0 , 1）=(0,1,1,1) !
(1 , 0 ,0 ,0 )=(0,1,1,0) !
(5)1 (1 , 1 ,0 , 0 )=(1,0,0,0) !
(0,1,0,0 ) +(1, 0, 1, 0）=(1,1,1,0) *
深度优先搜索亦称为纵向搜索。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。所以，深度优先搜索策略是不完备的。另外，应用此策略得到的解不一定是最佳解（最短路径）。
深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。
"人狼草\t\t\t羊", "人狼\t\t\t羊草",
"人羊草\t\t\t狼", "人羊\t\t\t狼草",
"人草\t\t\t狼羊", "人\t\t\t狼羊草",
"狼羊草\t\t人", "狼羊\t\t\t人草",
"狼草\t\t\t人羊", "狼\t\t\t人羊草",
"羊草\t\t\t人狼", "羊\t\t\t人狼草",

合集下载

人狼羊菜过河问题的解法及代码

人狼羊菜过河问题的解法及代码

⼈狼⽺菜过河问题的解法及代码⼈狼⽺菜问题是计算机领域中的经典问题。

之所以经典，⼀⽅⾯这是编译原理等课程中的⼀个建模及编码问题，另⼀⽅⾯也经常被作为智⼒题⽤在⾯试中。

本⽂讨论的是怎么建模、编码的问题。

问题描述：⼀个农夫有⼀条船，和狼、⽺、菜，农夫要把这3样东西运到河到另⼀边，农夫每次最多只能通过这个船运⼀样东西，要防⽌狼吃⽺、⽺吃⽩菜（即不能在没有农夫在的情况下同时在同⼀岸边），该怎么过？该问题的解决分为2个阶段，第⼀阶段是对状态建模，第⼆阶段是⽤⼴度遍历来找到问题的解。

其中⼴度遍历阶段和“量⽔问题”的⼴度遍历解法类似。

问题抽象：建⽴⼀个struct型的state，其中包括4个bool型的变量a1 a2 a3 a4分别对应⼈、狼、⽺、菜的状态，值为true代表在起始的河岸边，false代表在对岸，起始时4个分量都为true。

农夫每过⼀次河⽣成⼀个新的state。

根据题⽬可知，农夫过⼀次河a1取反，且a2 a3 a4值与a1相同的分量也可以分别取反分别⽣成⼀个新的state代表被农夫运到河的对岸的各种选择。

只有a1取反⽽a2 a3 a4都没取反⽣成的新状态代表农夫⾃⼰过河没有带东西。

每次⽣成⼀个新状态后，⾸先要检查是否达到了终⽌状态（a1 a2 a3 a4都为false），其次要检查是否是合法状态（要同时考虑⼀个state对应的河两岸是否有狼吃⽺、⽺吃⽩菜的情况出现），如果状态合法、没到终⽌状态且没有在⼴度遍历队列中出现过，则将状态插⼊⼴度遍历队列，否则将该状态丢弃。

在此过程中我们没有考虑正在渡河的情况，因为每次过河船上总是有⼈，不会出现冲突，视其为不稳定状态直接忽略。

代码如下：#include<iostream>using namespace std;#define MAX 500struct state{bool a1,a2,a3,a4;int parentId;//⽤于回溯输出解决步骤state(){a1 = a2 = a3 = a4 = true;//true表⽰在A地（起始岸边）parentId=-1;}};bool equal(state& astate,state& bstate){if(astate.a1==bstate.a1&&astate.a2==bstate.a2&&astate.a3==bstate.a3&&astate.a4==bstate.a4){return true;}return false;}void assign(state& astate,state& bstate){astate.a1=bstate.a1;astate.a2=bstate.a2;astate.a3=bstate.a3;astate.a4=bstate.a4;astate.parentId = bstate.parentId;}state currentState;state sQueue[MAX];int startPos = 0;int endPos = 1;bool isInQueue(state& newState){for(int i=0;i<endPos;i++){if(equal(newState,sQueue[i])){return true;}}return false;}bool isValidState(state& newState){//总共可能有16种状态。

狼羊过河模型

狼羊过河模型

大学生数学建模承诺书我们仔细阅读了数学建模的规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。

如有违反竞赛规则的行为，我们将受到严肃处理。

所属班级（请填写完整的全名）：队员(打印并签名) ：1.2.3.4.5.小组负责人(打印并签名)：日期：2012 年3月30日教师评阅：人、狼、羊、白菜过河模型一人摆渡希望用一条船将一只狼，一只羊，一篮白菜从河岸一边带到河岸对面，由于船的限制，一次只能带一样东西过河，绝不能在无人看守的情况下将狼和羊放在一起；羊和白菜放在一起，怎样才能将它们安全的带到河对岸去？一、问题分析：在正常情况下，一般要求在渡河过程中不能损失任何物品，但在某些情况下，有时候会从时间和经济考虑，可能会舍弃一些对自己不重要的，现在我们只考虑正常情况下的。

人狼羊白菜安全渡河问题可以看做是一个多步决策过程。

每一步要让船从此岸驶向彼岸或从彼岸返回此岸，都不能使得它们有损失，要对狼羊白菜作出决策，在保证安全的前提下，在有限步内全部安全通过，用图可以找出决策变化的规律，确定每一步的决策来达到安全渡河的目标。

二、模型构建：用二维向量S k=(x,y) 定义为状态. ，k=1,2,3,4,5,6,7设A,B,C,D分别为人带狼，人带羊，人带白菜,人不带任何。

安全渡河条件下的集合记为可行状态集合S，记S k={ (x,y)|x =D，y=A,B,C，D }其中当k为奇数的时候表示船从此岸驶向彼岸，偶数的时候表示船从彼岸驶向此岸，（x,y）表示x带着y.例如：S1=（D,B）表示人带着羊从此岸驶向彼岸；S2= (D,D) 表示人不带物从彼岸驶向此岸。

数学建模：研究商人过河问题

数学建模：研究商人过河问题

数学建模试验一陈述 【1 】试验标题：研讨商人过河问题一.试验目标：编写一个程序（可所以C,C++或Mathlab ）实现商人安然过河问题.二.试验情形：Turbo c 2.0..Matlab 6.0以上三.试验请求：请求该程序不但能找出一组安然过河的可行筹划,还可以得到所有的安然过河可行筹划.并且该程序具有必定的可扩大性,即不但可以实现3个商人,3个侍从的过河问题.还应能实现n 个商人,n 个侍从的过河问题以及n 个不合对象且每个对象有m 个元素问题(解释：对于3个商人,3个侍从问题分离对应于n=2,m=3)的过河问题.从而给出课后习题5（n=4,m=1）的全部安然过河筹划.四.试验步调：第一步：问题剖析.这是一个多步决议计划进程,涉及到每一次船上的人员以及要斟酌此岸和此岸上残剩的商人数和侍从数,在安然的前提下（两岸的侍从数不比商人多）,经有限步使全部人员过河.第二步：剖析模子的组成.记第k 次渡河前此岸的商人数为k x ,侍从数为k y , 2,1=k ,n y x k k 2,1,=,（具有可扩大性）,将）（k k y x ,界说为状况,状况聚集成为许可状况聚集（S ）.S={2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（}记第k 次渡船的商人数为k u ,侍从数为k v ,决议计划为),(k k v u ,安然渡河前提下,决议计划的聚集为许可决议计划聚集.许可决议计划聚集记作D,所以D={2,1,0,,21|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为k 为奇数时船从此岸驶向此岸,k 为偶数时船由此岸驶向此岸,所以状况k s 随决议计划k d 变更的纪律是k k k k d s s )1(1-+=-,此式为状况转移律.制订安然渡河筹划归结为如下的多步决议计划模子：求决议计划)2,1(n k D d k =∈,使状况S s k ∈按照转移律,由初始状况)3,3(1=s 经有限n 步到达)0,0(1=+n s第三步：模子求解.#include "stdio.h"#include "string.h"#include <memory>#include <stdlib.h>#include <iostream>using namespace std;#include "conio.h"FILE *fp;/*设立文件指针,以便将它用于其他函数中*/struct a{long m,s;struct a *next;};/*数组类型a ：记载各类情形下船上的商人和家丁数,m ：代表商人数 s ：代表家丁数*/ struct a *jj,head;/*head 为头指针的链表单元（船上的人数的各类情形的链表）*/ int n,total=0,js=0;/*total 暗示船上各类情形总数*/struct aim {long m1,s1,m2,s2;int n;struct aim *back,*next;};/*用于树立双向的指针链表,记入相符的情形,m1,s1暗示要过岸的商人数和家丁数;m2,s2暗示过岸了的商人数和家丁数,n暗示往返的次数*/ int k1,k2;void freeit(struct aim *p){struct aim *p1=p;p1=p->back;free(p);if(p1!=NULL)p1->next=NULL;return;}/*释放该单元格,并将其上的单元格的next指针还原*/int determ(struct aim *p){ struct aim *p1=p;if(p->s1>k2)return -1;/*家丁数不克不及超出总家丁数*/if(p->m1>k1)return -1;/*商人数不克不及超出总商人数*/if(p->s2>k2)return -1;/*对岸,同上*/if(p->m2>k1)return -1;/*对岸,同上*/if(p->s1<0)return -1;/*家丁数不克不及为负*/if(p->s2<0)return -1;/*商人数不克不及为负*/if(p->m1<0)return -1;/*对岸,同上*/if(p->m2<0)return -1;/*对岸,同上*/if(p->m1!=0)if(p->s1>p->m1)return -1;if(p->m2!=0)if(p->s2>p->m2)return -1;/*两岸商人数均不克不及小于家丁数*/while(p1!=NULL){p1=p1->back;if(p1!=NULL)if(p1->n%2==p->n%2)if(p1->s1==p->s1)if(p1->s2==p->s2)if(p1->m1==p->m1)if(p1->m2==p->m2)return -1;}/*用于解决反复,算法思惟：即将每次算出的链表单元与以前的比拟较,若反复,则暗示消失轮回*/if(p->s1==0&&p->m1==0)if(p->n%2==0)return 1;else return -1;/*显然假如达到前提就解释ok了*/return 0;}/*断定函数*/int sign(int n){if(n%2==0)return -1;return 1;}/*符号函数*/void copyit(struct aim *p3,struct aim *p){p3->s1=p->s1;p3->s2=p->s2;p3->m1=p->m1;p3->m2=p->m2;p3->n=p->n+1;p3->back=p;p3->next=NULL;}/*复制内容函数,将p中的内容写入p3所指向的链表单元中*/ void print(struct aim *p3){struct aim *p=p3;js++;while(p->back){p=p->back;}printf("\n第%d种办法:\n",js);fprintf(fp,"\n第%d种办法:\n",js);int count=0;while(p){ printf("%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2); fprintf(fp,"%ld,%ld::%ld,%ld\t",p->m1,p->s1,p->m2,p->s2);p=p->next;count++;}cout<<"一共有"<<count<<"步完成"<<endl;}/*打印函数,将p3所指的内容打印出来*/void trans(struct aim *p){struct aim *p3;/*p3为申请的构造体指针*/struct a *fla;int i,j,f;fla=&head;p3=(struct aim *)malloc(sizeof(struct aim));f=sign(p->n);for(i=0;i<total;i++){copyit(p3,p);p3->s1-=fla->m*f;p3->m1-=fla->s*f;p3->s2+=fla->m*f;p3->m2+=fla->s*f;/*运算进程,即过河进程*/ j=determ(p3);/*断定,j记载断定成果*/if(j==-1){if(i<total-1){continue;}else{freeit(p3);break;}}int count1=0;if(j==1){if(i<total-1){print(p3);count1++;continue;}else{print(p3);freeit(p3);break;}//cout<<cout1<<endl;printf("%d",count1);printf("\n");}if(j==0)trans(p3);}return;}/*转移函数,即将人转移过河*//*n=0*/void main(){ struct aim *p,*p1;int j,a,e,f;struct a *flag;/*flag是用与记载头指针*/FILE*fpt;if((fpt=fopen("c:result.dat","w+"))==0){printf("can't creat it\n");exit(0);}fp=fpt;system("cls");printf("问题描写：三个商人各带一个侍从乘船过河,一只划子只能容纳X人,由他们本身荡舟.三个商人窃听到侍从们谋害,在河的随意率性一岸上,只要侍从的人数比上人多,就杀失落商人.但是若何乘船渡河的决议计划权在商人手里,商人们若何安插渡河筹划确保自身安然？\n");printf("\n");p=(struct aim *)malloc(sizeof(struct aim));p->back=NULL;p->next=NULL;p->s2=0;p->m2=0;p->n=1;/*设立初始头指针*/printf("please input the total of people on the board\n");fprintf(fp,"\n请输入船上的人数\n");scanf("%d",&n);fprintf(fp,"\n%d\n",n);flag=&head;for(e=0;e<=n;e++)for(f=0;f<=n;f++)if(e+f>0&&e+f<=n){ total++;jj=(struct a*)malloc(sizeof(struct a));jj->m=e;jj->s=f;flag->next=jj;jj->next=NULL;flag=jj;}/*********************************/printf("please input the total of merchant and salvent as follow: mechant,salvent;\n"); fprintf(fp,"\nplease input the total of merchant and salvent as follow: mechant,salvent;\n"); scanf("%ld,%ld",&p->m1,&p->s1);fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1);/**********************************/k1=p->m1;k2=p->s1;trans(p);fclose(fpt);getch();}第一步：三个商人,三个侍从的模子求解答案为：运行后的成果为：第1 种筹划：(3,3) 到(0,0).(3,1) 到(0,2).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(0,2) 到 (3,1).(0,0) 到 (3,3)第2 种筹划：(3,3) 到(0,0).(3,1) 到(0,2).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(1,1) 到 (2,2).(0,0) 到 (3,3)第3 种筹划：(3,3) 到(0,0).(2,2) 到(1,1).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2)(.0,2) 到 (3,1).(0,0) 到 (3,3)第4 种筹划：(3,3) 到(0,0).(2,2) 到(1,1).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(1,1) 到 (2,2)(0,0) 到 (3,3)第二步：四个商人三个侍从,其成果为：第1种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第2种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第3种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第4种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第5种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第6种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第7种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第8种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第9种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第10种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第11种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第12种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第13种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第14种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第15种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第16种办法:2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第17种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第18种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第19种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第20种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第21种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第22种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,10,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第23种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,20,0::4,3 一共有16步完成第24种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第25种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第26种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第27种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,10,0::4,3 一共有16步完成第28种办法:4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第29种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第30种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,20,0::4,3 一共有16步完成第31种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第32种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第33种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第34种办法:2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,10,0::4,3 一共有16步完成第35种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第36种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第37种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第38种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第39种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第40种办法:2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第41种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第42种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第43种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第44种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第45种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第46种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,21,1::3,2 0,0::4,3 一共有12步完成第47种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第48种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第49种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成。

人狼羊菜渡河问题(含Matlab程序)

人狼羊菜渡河问题(含Matlab程序)

人、狼、羊、菜安全渡河问题安全渡河问题又称作“人狼羊菜”问题，其具体描述为：一个人带着一条狼、一只羊、一筐白菜过河但由于船太小，人一次只能带一样东西乘船过河。

狼和羊、羊和白菜不能单独留在同岸，否则羊或白菜会被吃掉。

该问题可使用图论中的最短路算法进行求解。

问题分析根据题意，人不在场时，狼要吃羊，羊要吃菜，因此，人不在场时，不能将狼与羊、羊与菜留在河的任一岸。

可用四维向量v=（m，n，p，q）来表示状态，m表示人，n代表狼，p代表羊，q代表白菜，且m,n,p,q ∈{0,1},0代表在对岸，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,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）。

可行状态共有十种。

每一次的渡河行为改变现有的状态。

现构造赋权图G=(V,E,W),其中顶点集V={v1,…, v10}中的顶点（按照上面的顺序编号）分别表示上述１０个可行状态，当且仅当对应的两个可行状态之间存在一个可行转移时两顶点之间才有边连接，并且对应的权重取为１，当两个顶点之间不存在可行转移时，可以把相应的权重取为∞。

因此问题变为在图Ｇ中寻找一条由初始状态（１,１,１,１）出发，经最小次数转移到达最终状态（０,０,０,０）的转移过程，即求从状态（１,１,１,１）到状态（０,０,０,０）的最短路径。

该问题难点在于计算邻接矩阵，由于摆渡一次就改变现有状态，为此再引入一个四维状态转移向量，用它来反映摆渡情况。

用１表示过河，０表示未过河。

例如，（１,１,０,０）表示人带狼过河。

状态转移只有四种情况，用如下向量表示：（１,０,０,０），（１,１,０,０），（１,０,１,０），（１,０,０,１）现在规定状态向量与转移向量之间的运算为0+0=0,1+0=1,0+1=1,1+1=0通过上面的定义，如果某一个可行状态加上转移向量得到的新向量还属于可行状态，则这两个可行状态对应的顶点之间就存在一条边。