商人過河的數(shù)學(xué)模型及編程解決.doc

14對商仆過河問題題目有14名商人各帶一名仆人要過河，但船最多能載4人。商人已獲得仆人的陰謀：在河的任意一岸，只要仆人數(shù)超過商人數(shù)，仆人會將商人殺死并竊取貨物。安排如何乘船的權(quán)利權(quán)利在商人手上，試為商人制定一個安全的過河方案。一摘要n對商仆過河，一只船最多載m人，船上和岸上的仆人數(shù)都不能多于商人數(shù)，否則商人有危險。安排合理的渡河方案，保證商人能安全渡河。（可利用向量，矩陣，圖解等方法）。二問題提出：有14對商仆乘船過河，一只船最多載4人，由商人和仆人自己劃船渡河，在河的任意一岸，一旦仆人數(shù)多于商人數(shù)，仆人就可將商人殺死，謀取利益，但是乘船渡河的主動權(quán)掌握在商人們手中，商人們?nèi)绾伟才哦珊臃桨?，才能安全渡河？三問題分析商仆安全渡河問題可以視為一個多步?jīng)Q策過程，多步?jīng)Q策是指決策過程難以一次完成，而是多步優(yōu)化，最后獲取一個全局最優(yōu)方案的決策方法。對于每一步，即船由此岸駛向彼岸，或者船由彼岸駛向此岸的決策，不僅會影響到該過程的效果，而且還會影響到下一步的初始狀態(tài)，從而對整個過程都會有影響。所以，在每一次過河時，就不能只從這一次過河本身考慮，還要把它看成是整個過河過程中的一個部分。在對船上的人員做決策時，要保證兩岸的商人數(shù)不能少于仆人數(shù)，用最少的步伐是人員全部過河。應(yīng)用狀態(tài)向量和運載向量，找出狀態(tài)隨運載變化的規(guī)律，此問題就轉(zhuǎn)化為狀態(tài)在允許范圍內(nèi)（即安全渡河條件），確定每一次該如何過河，從而達到渡河的目標?，F(xiàn)在我們都把它們數(shù)量化：即用數(shù)學(xué)語言來表示。四模型假設(shè)與符號假設(shè)（一）模型假設(shè)商人和仆人都會劃船，天氣很好，無大風(fēng)大浪，船的質(zhì)量很好，船槳足夠很多次的運載商人和仆人。（二）符號假設(shè)設(shè)（x，y）是狀態(tài)向量，表示任一岸的商人和仆人數(shù)，且x，y分別要大于等于0，小于等于M。1.設(shè)（m，n）是運載向量，表示運載的商人數(shù)和仆人數(shù)，0=m=N，0=n=N，0=m+n =3， DoIfsi+1= =sm，u=1，Break ，m，l，i -1，2 ； Ifu= =0，ci+1=dj；Break ，j，1，5； Ift= =0，PrintNo，Result；Break ； bi+1=3，3-si+1； Printsi，- - - -，ci+1，- - - -，bi+1； Ifsi+1= =0，0，Break ，i，1，12 程序運行結(jié)果如下： 此岸船上對岸 3，30，20，2 3，10，10，1 3，20，20，3 3，00，10，2 3，12，02，2 1，11，11，1 2，22，03，1 0，20，13，0 0，30，23，2 0，10，13，1 0，20，23，3 可以得出經(jīng)過11步的渡河就能達到安全渡河的目標及滿足渡河的次數(shù)盡量少的條件。這11步的渡河方案就是上面程序運行結(jié)果中船上下面的一列。渡河的整個過程如下所示： 去2隨從 回1隨從（3商人3隨從）（3商人1隨從） 去2隨從 回1隨從（3商人2隨從）（3商人0隨從） 去2商人 回1商人1隨從（3商人1隨從）（1商人1隨從） 去2商人 回1隨從（2商人2隨從）（0商人2隨從） 去2隨從 回1隨從（0商人3隨從）（0商人1隨從） 去2隨從 （0商人2隨從）（渡河成功）七、結(jié)果分析與檢驗八、模型的優(yōu)缺點與改進方向九、參考文獻【1】 茆詩松等 , 概率論與數(shù)理統(tǒng)計教程，北京：高等教育出版社,2004年?！?】 趙靜，但琦，數(shù)學(xué)建模與數(shù)學(xué)實驗3，北京：高等教育出版社，2008年。十、附錄（一）程序/約束條件:岸上仆人不能多于商人數(shù)#include using namespace std;struct Nodeint nMer;int nSer;int length;class Apublic:A();A();void Tspt();/過河的動作void doLeft(int nhead,int ntail,int nlength);private:bool islegal(int nm,int ns); /判斷是否滿足約束條件，滿足為trueNode *funTspt(int nm,int ns,bool flag);/添加STEPhead可以向后延伸的節(jié)點bool noRepeat(int nm,int ns);/沒有重復(fù)返回TRUEvoid funshow(int a2,int ntail);bool funLeft(Node nd,int b1,int b2,int n);void show(int s,int p2,int &top,int &count,int a);int head;int tail;int n;/商仆的對數(shù)int nB;/船最多的載人數(shù)目Node *STEP;A:A()free(STEP);A:A()coutn;coutnB;STEP = (Node *)malloc(sizeof(Node)*10000);memset(STEP,0,sizeof(Node)*10000);head = tail = 0;STEP0.nMer = STEP0.nSer = n;int main()A a;a.Tspt();return 0;void A:show(int s,int p2,int &top,int &count,int a)if(top = -1)return ;/已找到目標狀態(tài)需，輸出數(shù)據(jù)if(top = STEPhead.length)cout* +count *endl;funshow(p,top + 1);B:top-;if(top = -1)return ;C:stop-;if(STEP(stop).length != top)/退過了stop = atop;goto B;if(funLeft(STEP(stop),ptop - 10,ptop - 11,top - 1) = false)goto C;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;/在中間加入節(jié)點STEP(stop + 1) if(funLeft(STEP(stop + 1),ptop0,ptop1,top) = true)/符合條件top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;else/不符合條件E:stop + 1-;if(STEP(stop + 1).length = top)/退過了，到了下一層stop + 1 = atop + 1;D:stop-;if(STEP(stop).length != top)/退過了，到了下一層for(int i = top; i = STEPhead.length; i+)si = ai;top-;if(top = -1)return ;goto D;if(top = 0)return ;if(funLeft(STEP(stop),ptop - 10,ptop - 11,top - 1) = false)goto D;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;if(funLeft(STEP(stop + 1),ptop0,ptop1,top) = false)goto E;top+;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);void A:doLeft(int nhead,int ntail,int nlength)int a1000;int a11000;int sp10002;bool flag = false;memset(a,0xff,4000);memset(a1,0xff,4000);memset(sp,0xff,8000);if(STEPhead.length%2 = 0)flag = true;while(STEPhead.length = nlength - 1)funTspt(STEPhead.nMer,STEPhead.nSer,flag);head+;for(int i = 0; i head + 1; i+)a(STEPi.length) = i;a1(STEPi.length) = i;sp00 = sp01 = n;STEPhead.nMer = STEPhead.nSer = 0;int top = 0;int count = 0;show(a1,sp,top,count,a);bool A:funLeft(Node nd,int b1,int b2,int n)bool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) 0;if(flag = false)return false;if(n%2 = 0 & b1 = nd.nMer & b2 = nd.nSer)return true;if(n%2 = 1 & b1 = nd.nMer & b2 = nd.nSer)return true;return false;void A:Tspt()Node *temp = new Node;temp = NULL;bool flag = false;while(head tail)cout此問題無解!nMer,temp-nSer,temp-length);/temp-nMer表示headdelete temp;Node* A:funTspt(int nm,int ns,bool flag)/flag = true 向?qū)Π哆\輸Node *nd = NULL;int temp = 1;int tM = STEPhead.nMer;/可供運輸?shù)纳倘藬?shù)int tS = STEPhead.nSer;/可供運輸?shù)钠腿藬?shù)if(flag = false)/向此岸運輸tM = n - STEPhead.nMer;tS = n - STEPhead.nSer;temp = -1;for(int i = 0; i tM + 1 & i nB + 1; i+)/i表示運輸?shù)纳倘藬?shù)for(int j = 0; j tS + 1 & j length = STEPhead.length + 1;nd-nMer = head;nd-nSer = tail;return nd;tail+;STEPtail.length = STEPhead.length + 1;STEPtail.nMer = p;STEPtail.nSer = q;return nd;bool A:noRepeat(int nm,int ns)int j1 = 0;if(STEPhead.length%2 = 0)j1 = 1;for(int i = j1; i tail + 1; i+)if(STEPi.length%2 = j1 & nm = STEPi.nMer & ns = STEPi.nSer)return false;return true;bool A:islegal(int nm,int ns)/商人數(shù)少于仆人數(shù)或者商人數(shù)為0if(nm = 0) | (nm = n) | (nm = ns)return true;return false;void A:funshow(int a2