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

數(shù)學(xué)建模論文-PAGE5-商仆過河問題作者：*學(xué)院**班***************號(hào)2014年12月4日摘要：為了求解3個(gè)商人和3個(gè)隨從的過河問題，用數(shù)學(xué)分析方法，建立數(shù)學(xué)模型，并且加以求解，展示動(dòng)態(tài)規(guī)劃思想的應(yīng)用步驟。最后利用計(jì)算機(jī)編程進(jìn)行求解，獲得過河問題的完整求解過程；有效地求解類似多步?jīng)Q策問題的作用。關(guān)鍵詞：多步?jīng)Q策計(jì)算機(jī)求解狀態(tài)轉(zhuǎn)移律圖解法MATLAB程序一、問題的提出S個(gè)商人各帶一個(gè)隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數(shù)比商人多，就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手中，商人們?nèi)绾伟才哦珊佑?jì)劃確保自身安全？二、問題的關(guān)鍵解決的關(guān)鍵集中在商人和隨從的數(shù)量上，以及小船的容量上，該問題就是考慮過河步驟的安排和數(shù)量上。各個(gè)步驟對(duì)應(yīng)的狀態(tài)及決策的表示法也是關(guān)鍵。三、問題的分析在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過河。由于船上人數(shù)限制，這需要多步?jīng)Q策過程，必須考慮每一步船上的人員。動(dòng)態(tài)規(guī)劃法正是求解多步?jīng)Q策的有效方法。它要求把解的問題一層一層地分解成一級(jí)一級(jí)、規(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個(gè)格點(diǎn)允許狀態(tài)10個(gè)●點(diǎn)允許決策移動(dòng)1或2格;k奇,左下移;k偶,右上移.xxy3322110S1sn+1d1d11總共需要11步可以得出經(jīng)過11步的渡河就能達(dá)到安全渡河的目標(biāo)及滿足渡河的次數(shù)盡量少的條件。這11步的渡河方案就是上面程序運(yùn)行結(jié)果中船上下面的一列。八、模型的檢驗(yàn)用2名商人和2名隨從的過河問題的解決思路，檢驗(yàn)3名商人和3名隨從的過河問題。九、模型的拓展和延伸通過三名商人和三名隨從的過河問題的解決方案，可以進(jìn)一步計(jì)算四名商人和四名隨從的過河問題，通過計(jì)算機(jī)編程可以設(shè)計(jì)m名商人和n名隨從的過河問題。十、總結(jié)這是通過數(shù)學(xué)分析的方法解決實(shí)用問題，經(jīng)過問題提出、問題假設(shè)、問題分析、模型建立、模型求解、模型檢驗(yàn)的過程，解決商人過河問題。然后擴(kuò)展延伸到n個(gè)商人的問題。學(xué)習(xí)數(shù)學(xué)建模以來，重新認(rèn)識(shí)了學(xué)習(xí)數(shù)學(xué)的樂趣，也重新認(rèn)識(shí)了數(shù)學(xué)，本以為數(shù)學(xué)是單調(diào)的，枯燥的，學(xué)習(xí)了之后，發(fā)現(xiàn)數(shù)學(xué)是普遍存在我們生活之中的。解決現(xiàn)實(shí)中的問題，很多都需要數(shù)學(xué)。沉浸在數(shù)學(xué)的世界里，發(fā)現(xiàn)學(xué)習(xí)是有趣的；相比于機(jī)械的認(rèn)識(shí)各個(gè)組織器官，建立一個(gè)數(shù)學(xué)模型解決問題是十分有趣的。參考文獻(xiàn)：（1）傅清祥．《數(shù)據(jù)結(jié)構(gòu)與算法》．王曉東．北京：電子工業(yè)出版社1998．（2）姜啟瑟．《數(shù)學(xué)建?！?第二版)．北京：高等教育出版社，2000．（3）運(yùn)籌學(xué)教材編寫組．《運(yùn)籌學(xué)》(修訂版)．北京：清華大學(xué)出版社。2001．附：商仆過河的C程序及運(yùn)行截屏:#include<iostream>usingnamespacestd;structNode{ intnMer; intnSer; intlength;};classA{public: A(); ~A(); voidTspt(); //過河的動(dòng)作 voiddoLeft(intnhead,intntail,intnlength); private: boolislegal(intnm,intns);//判斷是否滿足約束條件，滿足為true Node*funTspt(intnm,intns,boolflag);//添加STEP[head]可以向后延伸的節(jié)點(diǎn) boolnoRepeat(intnm,intns);//沒有重復(fù)返回TRUE voidfunshow(inta[][2],intntail); boolfunLeft(Nodend,intb1,intb2,intn); voidshow(ints[],intp[][2],int&top,int&count,inta[]); inthead; inttail; intn; //商仆的對(duì)數(shù) intnB; //船最多的載人數(shù)目 Node*STEP;};A::~A(){ free(STEP);}A::A(){ cout<<"請(qǐng)輸入商仆的對(duì)數(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<<"請(qǐng)輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n==3) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請(qǐng)輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n==4) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=n-1;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請(qǐng)輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n>=5&&n<=100) { cout<<"船最多載人的數(shù)目可以取:"; for(intx=4;x<=2*n;x++) { cout<<x<<"、"; }cout<<endl; cout<<"請(qǐng)輸入船最多載人的數(shù)目K=";cin>>nB; } elseif(n<1||n>100){ cout<<"本程序僅在S=(0…100)以內(nèi)保證其正確性"<<endl;cout<<"請(qǐng)重新輸入商仆的對(duì)數(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個(gè)商人各帶一個(gè)隨從乘船過河，一只小船只能容納K人，由他們自己劃船。商人們竊聽到隨從們密謀，在河的任意一岸上，只要隨從的人數(shù)比商人多，就殺掉商人。但是如何乘船渡河的決策權(quán)在商人手中，商人們?nèi)绾伟才哦珊佑?jì)劃確保自身安全？"<<endl; Aa; a.Tspt(); return0;}voidA::show(ints[],intp[][2],int&top,int&count,inta[]){ if(top==-1) return; //已找到目標(biāo)狀態(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é)點(diǎn)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ū)Π哆\(yùn)輸 Node*nd=NULL; inttemp=1; inttM=STEP[head].nMer; //可供運(yùn)輸?shù)纳倘藬?shù) inttS=STEP[head].nSer; //可供運(yùn)輸?shù)钠腿藬?shù) if(flag==false) //向此岸運(yùn)輸 { tM=n-STEP[head].nMer; tS=n-STEP[head].nSer; temp=-1; } for(inti=0;i<tM+1&&i<nB+1;i++)//i表示運(yùn)輸?shù)纳倘藬?shù) { for(intj=0;j<tS+1&&j<nB-i+1;j++)//j表示運(yùn)輸?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(