商仆过河问题-数学建模

数学建模论文-PAGE5-商仆过河问题作者：*学院**班***************号2014年12月4日摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。关键词：多步决策计算机求解状态转移律图解法MATLAB程序一、问题的提出S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？二、问题的关键解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。三、问题的分析在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。四、模型假设记第k次过河前A岸的商人数为XK，随从数为YKk=1，2，⋯XK,YK=0，1，2，3，将二维向量SK=(XK，YK)定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S。则S={(XK,YK)|(XK=0,YK=0,1,2,3),(XK=3,YK=0,1,2,3),(XK=YK=1)(XK=YK=2)}记第k次过河船上的商人数为UK，随从数为VK将二维向量DK=(UK,VK)定义为决策．由小船的容量可知允许决策集合（记作D)为D={(UK,VK)|UK+VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}主程序流程图图解法：状态s=(x,y)16个格点允许状态10个●点允许决策移动1或2格;k奇,左下移;k偶,右上移.xxy3322110S1sn+1d1d11总共需要11步可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。八、模型的检验用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。九、模型的拓展和延伸通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m名商人和n名随从的过河问题。十、总结这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题。学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。参考文献：（1）傅清祥．《数据结构与算法》．王晓东．北京：电子工业出版社1998．（2）姜启瑟．《数学建模》(第二版)．北京：高等教育出版社，2000．（3）运筹学教材编写组．《运筹学》(修订版)．北京：清华大学出版社。2001．附：商仆过河的C程序及运行截屏:#include<iostream>usingnamespacestd;structNode{ intnMer; intnSer; intlength;};classA{public: A(); ~A(); voidTspt(); //过河的动作 voiddoLeft(intnhead,intntail,intnlength); private: boolislegal(intnm,intns);//判断是否满足约束条件，满足为true Node*funTspt(intnm,intns,boolflag);//添加STEP[head]可以向后延伸的节点 boolnoRepeat(intnm,intns);//没有重复返回TRUE voidfunshow(inta[][2],intntail); boolfunLeft(Nodend,intb1,intb2,intn); voidshow(ints[],intp[][2],int&top,int&count,inta[]); inthead; inttail; intn; //商仆的对数 intnB; //船最多的载人数目 Node*STEP;};A::~A(){ free(STEP);}A::A(){ cout<<"请输入商仆的对数S=";F: cin>>n; if(n==1) { nB=2;cout<<"船最多载人的数目K="<<nB; } elseif(n==2) { cout<<"船最多载人的数目可以取:"; for(intx=n;x<=2*n;x++) { cout<<x<<"、"; } cout<<endl; cout<<"请输入船最多载人的数目K=";cin>>nB; } elseif(n==3) { cout<<"船最多载人的数目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"请输入船最多载人的数目K=";cin>>nB; } elseif(n==4) { cout<<"船最多载人的数目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"请输入船最多载人的数目K=";cin>>nB; } elseif(n>=5&&n<=100) { cout<<"船最多载人的数目可以取:"; for(intx=4;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"请输入船最多载人的数目K=";cin>>nB; } elseif(n<1||n>100){ cout<<"本程序仅在S=(0…100)以内保证其正确性"<<endl;cout<<"请重新输入商仆的对数S="; gotoF;} STEP=(Node*)malloc(sizeof(Node)*10000); memset(STEP,0,sizeof(Node)*10000); head=tail=0; STEP[0].nMer=STEP[0].nSer=n;}intmain(){cout<<"问题描述：S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？"<<endl; Aa; a.Tspt(); return0;}voidA::show(ints[],intp[][2],int&top,int&count,inta[]){ if(top==-1) return; //已找到目标状态需，输出数据 if(top==STEP[head].length) { cout<<"***********"<<++count<<"***********"<<endl; funshow(p,top+1); B: top--; if(top==-1) return;C: s[top]--; if(STEP[(s[top])].length!=top)//退过了 { s[top]=a[top]; gotoB; } if(funLeft(STEP[(s[top])],p[top-1][0],p[top-1][1],top-1)==false) gotoC; p[top][0]=STEP[(s[top])].nMer; p[top][1]=STEP[(s[top])].nSer; show(s,p,top,count,a); return; } //在中间加入节点STEP[(s[top+1])] if(funLeft(STEP[(s[top+1])],p[top][0],p[top][1],top)==true)//符合条件 { top++; p[top][0]=STEP[(s[top])].nMer; p[top][1]=STEP[(s[top])].nSer; show(s,p,top,count,a); return; } else //不符合条件 {E: s[top+1]--; if(STEP[(s[top+1])].length==top)//退过了，到了下一层 { s[top+1]=a[top+1];D: s[top]--; if(STEP[(s[top])].length!=top)//退过了，到了下一层 { for(inti=top;i<=STEP[head].length;i++) s[i]=a[i]; top--; if(top==-1) return; gotoD; } if(top==0) return; if(funLeft(STEP[(s[top])],p[top-1][0],p[top-1][1],top-1)==false) gotoD; p[top][0]=STEP[(s[top])].nMer; p[top][1]=STEP[(s[top])].nSer; show(s,p,top,count,a); return; } if(funLeft(STEP[(s[top+1])],p[top][0],p[top][1],top)==false) gotoE; top++; p[top][0]=STEP[(s[top])].nMer; p[top][1]=STEP[(s[top])].nSer; show(s,p,top,count,a); } }voidA::doLeft(intnhead,intntail,intnlength){ inta[1000]; inta1[1000]; intsp[1000][2]; boolflag=false; memset(a,0xff,4000); memset(a1,0xff,4000); memset(sp,0xff,8000); if(STEP[head].length%2==0) flag=true; while(STEP[head].length==nlength-1) { funTspt(STEP[head].nMer,STEP[head].nSer,flag); head++; } for(inti=0;i<head+1;i++) { a[(STEP[i].length)]=i; a1[(STEP[i].length)]=i; } sp[0][0]=sp[0][1]=n; STEP[head].nMer=STEP[head].nSer=0; inttop=0; intcount=0; show(a1,sp,top,count,a); }boolA::funLeft(Nodend,intb1,intb2,intn){ boolflag=abs(nd.nMer-b1)+abs(nd.nSer-b2)<nB+1 &&abs(nd.nMer-b1)+abs(nd.nSer-b2)>0; if(flag==false) returnfalse; if(n%2==0&&b1>=nd.nMer&&b2>=nd.nSer) returntrue; if(n%2==1&&b1<=nd.nMer&&b2<=nd.nSer) returntrue; returnfalse;}voidA::Tspt(){ Node*temp=newNode; temp=NULL; boolflag=false; while(head<=tail) { if(STEP[head].length%2==0) flag=true; else flag=false; temp=funTspt(STEP[head].nMer,STEP[head].nSer,flag); if(NULL!=temp) break; head++; } if(head>tail) {cout<<"此问题无解!"<<endl; exit(1); } doLeft(temp->nMer,temp->nSer,temp->length);//temp->nMer表示head deletetemp;}Node*A::funTspt(intnm,intns,boolflag){//flag==true向对岸运输 Node*nd=NULL; inttemp=1; inttM=STEP[head].nMer; //可供运输的商人数 inttS=STEP[head].nSer; //可供运输的仆人数 if(flag==false) //向此岸运输 { tM=n-STEP[head].nMer; tS=n-STEP[head].nSer; temp=-1; } for(inti=0;i<tM+1&&i<nB+1;i++)//i表示运输的商人数 { for(intj=0;j<tS+1&&j<nB-i+1;j++)//j表示运输的仆人数 { if(i+j==0) continue; intp=STEP[head].nMer-temp*i; intq=STEP[head].nSer-temp*j; if(islegal(p,q)==true&&noRepeat(p,q)==true) { if(p==0&&q==0) { tail++; STEP[tail].length=STEP[head].length+1; STEP[tail].nMer=p; STEP[tail].nSer=q; nd=(Node*)malloc(sizeof(Node)); nd->length=STEP[head].length+1; nd->nMer=head; nd->nSer=tail; returnnd; } tail++; STEP[tail].length=STEP[head].length+1; STEP[tail].nMer=p; STEP[tail].nSer=q; } } } returnnd;}boolA::noRepeat(intnm,intns){ intj1=0; if(STEP[head].length%2==0) j1=1; for(