商仆過河問題-數(shù)學建模

數(shù)學建模論文-PAGE5-商仆過河問題作者：*學院**班***************號2014年12月4日摘要：為了求解3個商人和3個隨從的過河問題，用數(shù)學分析方法，建立數(shù)學模型，并且加以求解，展示動態(tài)規(guī)劃思想的應(yīng)用步驟。最后利用計算機編程進行求解，獲得過河問題的完整求解過程；有效地求解類似多步?jīng)Q策問題的作用。關(guān)鍵詞：多步?jīng)Q策計算機求解狀態(tài)轉(zhuǎn)移律圖解法MATLAB程序一、問題的提出S個商人各帶一個隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數(shù)比商人多，就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手中，商人們?nèi)绾伟才哦珊佑媱澊_保自身安全？二、問題的關(guān)鍵解決的關(guān)鍵集中在商人和隨從的數(shù)量上，以及小船的容量上，該問題就是考慮過河步驟的安排和數(shù)量上。各個步驟對應(yīng)的狀態(tài)及決策的表示法也是關(guān)鍵。三、問題的分析在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。由于船上人數(shù)限制，這需要多步?jīng)Q策過程，必須考慮每一步船上的人員。動態(tài)規(guī)劃法正是求解多步?jīng)Q策的有效方法。它要求把解的問題一層一層地分解成一級一級、規(guī)模逐步縮小的子問題。直到可以直接求出其解的子問題為止。分解成所有子問題按層次關(guān)系構(gòu)成一棵子問題樹．樹根是原問題。原問題的解依賴于子問題樹中所有子問題的解。四、模型假設(shè)記第k次過河前A岸的商人數(shù)為XK，隨從數(shù)為YKk=1，2，?XK,YK=0，1，2，3，將二維向量SK=(XK，YK)定義為狀態(tài)．把滿足安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合。記作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次過河船上的商人數(shù)為UK，隨從數(shù)為VK將二維向量DK=(UK,VK)定義為決策．由小船的容量可知允許決策集合（記作D)為D={(UK,VK)|UK+VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}主程序流程圖圖解法：狀態(tài)s=(x,y)16個格點允許狀態(tài)10個●點允許決策移動1或2格;k奇,左下移;k偶,右上移.xxy3322110S1sn+1d1d11總共需要11步可以得出經(jīng)過11步的渡河就能達到安全渡河的目標及滿足渡河的次數(shù)盡量少的條件。這11步的渡河方案就是上面程序運行結(jié)果中船上下面的一列。八、模型的檢驗用2名商人和2名隨從的過河問題的解決思路，檢驗3名商人和3名隨從的過河問題。九、模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進一步計算四名商人和四名隨從的過河問題，通過計算機編程可以設(shè)計m名商人和n名隨從的過河問題。十、總結(jié)這是通過數(shù)學分析的方法解決實用問題，經(jīng)過問題提出、問題假設(shè)、問題分析、模型建立、模型求解、模型檢驗的過程，解決商人過河問題。然后擴展延伸到n個商人的問題。學習數(shù)學建模以來，重新認識了學習數(shù)學的樂趣，也重新認識了數(shù)學，本以為數(shù)學是單調(diào)的，枯燥的，學習了之后，發(fā)現(xiàn)數(shù)學是普遍存在我們生活之中的。解決現(xiàn)實中的問題，很多都需要數(shù)學。沉浸在數(shù)學的世界里，發(fā)現(xiàn)學習是有趣的；相比于機械的認識各個組織器官，建立一個數(shù)學模型解決問題是十分有趣的。參考文獻：（1）傅清祥．《數(shù)據(jù)結(jié)構(gòu)與算法》．王曉東．北京：電子工業(yè)出版社1998．（2）姜啟瑟．《數(shù)學建?！?第二版)．北京：高等教育出版社，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]可以向后延伸的節(jié)點 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; //商仆的對數(shù) intnB; //船最多的載人數(shù)目 Node*STEP;};A::~A(){ free(STEP);}A::A(){ cout<<"請輸入商仆的對數(shù)S=";F: cin>>n; if(n==1) { nB=2;cout<<"船最多載人的數(shù)目K="<<nB; } elseif(n==2) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=n;x<=2*n;x++) { cout<<x<<"、"; } cout<<endl; cout<<"請輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n==3) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n==4) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n>=5&&n<=100) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=4;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n<1||n>100){ cout<<"本程序僅在S=(0…100)以內(nèi)保證其正確性"<<endl;cout<<"請重新輸入商仆的對數(shù)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人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數(shù)比商人多，就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手中，商人們?nèi)绾伟才哦珊佑媱澊_保自身安全？"<<endl; Aa; a.Tspt(); return0;}voidA::show(ints[],intp[][2],int&top,int&count,inta[]){ if(top==-1) return; //已找到目標狀態(tài)需，輸出數(shù)據(jù) 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; } //在中間加入節(jié)點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向?qū)Π哆\輸 Node*nd=NULL; inttemp=1; inttM=STEP[head].nMer; //可供運輸?shù)纳倘藬?shù) inttS=STEP[head].nSer; //可供運輸?shù)钠腿藬?shù) 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表示運輸?shù)纳倘藬?shù) { for(intj=0;j<tS+1&&j<nB-i+1;j++)//j表示運輸?shù)钠腿藬?shù) { 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(