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

1、14對(duì)商仆過(guò)河問(wèn)題題目有14名商人各帶一名仆人要過(guò)河，但船最多能載4人。商人已獲得仆人的陰謀：在河的任意一岸，只要仆人數(shù)超過(guò)商人數(shù)，仆人會(huì)將商人殺死并竊取貨物。安排如何乘船的權(quán)利權(quán)利在商人手上，試為商人制定一個(gè)安全的過(guò)河方案。一摘要n對(duì)商仆過(guò)河，一只船最多載m人，船上和岸上的仆人數(shù)都不能多于商人數(shù)，否則商人有危險(xiǎn)。安排合理的渡河方案，保證商人能安全渡河。（可利用向量，矩陣，圖解等方法）。二問(wèn)題提出：有14對(duì)商仆乘船過(guò)河，一只船最多載4人，由商人和仆人自己劃船渡河，在河的任意一岸，一旦仆人數(shù)多于商人數(shù)，仆人就可將商人殺死，謀取利益，但是乘船渡河的主動(dòng)權(quán)掌握在商人們手中，商人們?nèi)绾伟才哦珊臃桨?，?/p>

2、能安全渡河？三問(wèn)題分析商仆安全渡河問(wèn)題可以視為一個(gè)多步?jīng)Q策過(guò)程，多步?jīng)Q策是指決策過(guò)程難以一次完成，而是多步優(yōu)化，最后獲取一個(gè)全局最優(yōu)方案的決策方法。對(duì)于每一步，即船由此岸駛向彼岸，或者船由彼岸駛向此岸的決策，不僅會(huì)影響到該過(guò)程的效果，而且還會(huì)影響到下一步的初始狀態(tài)，從而對(duì)整個(gè)過(guò)程都會(huì)有影響。所以，在每一次過(guò)河時(shí)，就不能只從這一次過(guò)河本身考慮，還要把它看成是整個(gè)過(guò)河過(guò)程中的一個(gè)部分。在對(duì)船上的人員做決策時(shí)，要保證兩岸的商人數(shù)不能少于仆人數(shù)，用最少的步伐是人員全部過(guò)河。應(yīng)用狀態(tài)向量和運(yùn)載向量，找出狀態(tài)隨運(yùn)載變化的規(guī)律，此問(wèn)題就轉(zhuǎn)化為狀態(tài)在允許范圍內(nèi)（即安全渡河條件），確定每一次該如何過(guò)河，從而達(dá)到

3、渡河的目標(biāo)?，F(xiàn)在我們都把它們數(shù)量化：即用數(shù)學(xué)語(yǔ)言來(lái)表示。四模型假設(shè)與符號(hào)假設(shè)（一）模型假設(shè)商人和仆人都會(huì)劃船，天氣很好，無(wú)大風(fēng)大浪，船的質(zhì)量很好，船槳足夠很多次的運(yùn)載商人和仆人。（二）符號(hào)假設(shè)設(shè)（x，y）是狀態(tài)向量，表示任一岸的商人和仆人數(shù)，且x，y分別要大于等于0，小于等于M。1.設(shè)（m，n）是運(yùn)載向量，表示運(yùn)載的商人數(shù)和仆人數(shù)，0<=m<=N，0<=n<=N，0<=m+n<=N。2.設(shè)用s表示所有的可取狀態(tài)向量的集合。3.設(shè)用d表示所有運(yùn)載向量的集合。4.設(shè)用 表示從此岸到彼岸，作減；用 表示從彼岸到此岸，作加。Sk：表示第k步可取狀態(tài)向量（Sk屬于s）

4、；dk：表示第k步可取轉(zhuǎn)移向量（dk屬于d）；五模型的建立 我們以3名商人為例。設(shè)第k次渡河前此岸的商人數(shù)為xk，隨從數(shù)為yk，k=1，2，xk，yk =0，1，2，3，將二維向量Sk =（xk，yk）定義為狀態(tài)。安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合，記為S，則允許狀態(tài)集合為：S=（x，y）|x = 0或3，y = 0，1，2，3，x = y = 1，2 （1）又設(shè)第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，將二維向量dk=（uk+ vk）定義為決策。則允許決策集合為：D=（u，v）| u + v = 1，2 （2）因?yàn)閗為奇數(shù)時(shí)船從此岸駛向彼岸，k為偶數(shù)時(shí)船由彼岸駛向此岸，所以狀態(tài)Sk隨著

5、決策dk變化的規(guī)律即狀態(tài)轉(zhuǎn)移規(guī)律是：Sk+1 = Sk +（- 1）k dk （3）這樣，制定安全渡河方案歸結(jié)為如下的多步?jīng)Q策問(wèn)題：求決策dk D（k = 1，2，n），使?fàn)顟B(tài)Sk S按照規(guī)律（3），由初始狀態(tài)S1=（3，3）經(jīng)有限步（設(shè)為n）到達(dá)狀態(tài)Sn+1=（0，0）。六模型的簡(jiǎn)化與求解下面通過(guò)程序給出這個(gè)多步?jīng)Q策問(wèn)題的一個(gè)解： a1=0，0；a2=0，1；a3=0，2；a4=0，3；a5=3，0；a6=3，1；a7=3，2；a8=3，3；a9=1，1；a10=2，2； （*以上給出10個(gè)允許的狀態(tài)*） d1=0，2；d2=2，0；d3=1，1；d4=0，1； d5=1，0； （*以上表示

6、給出5個(gè)允許的決策*） i=1；j=1；k=1；s0=s1=3，3； Print此岸船上對(duì)岸； Do Dosi+1=si+（-1）i dj； t=0； DoIfsi+1= =ak，t=1，k，1，10； Ift= =0，Continue ； （*以上是保證狀態(tài)屬于允許的狀態(tài)*） l=Modi+1，2；m=l；u=0； Ifi+1> =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，- -

7、- -，ci+1，- - - -，bi+1； Ifsi+1= =0，0，Break ，i，1，12 程序運(yùn)行結(jié)果如下： 此岸船上對(duì)岸 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)過(guò)11步的渡河就能達(dá)到安全渡河的目標(biāo)及滿足渡河的次數(shù)盡量少的條件。這11步的渡河方案就是上面程序運(yùn)行結(jié)果中船上下面的一列。渡河的整個(gè)過(guò)程如下所示： 去2隨從 回1隨從（3商人3隨從）（3商人1隨從） 去2隨從 回1隨從（3商人2隨從）（

8、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àn)八、模型的優(yōu)缺點(diǎn)與改進(jìn)方向九、參考文獻(xiàn)【1】 茆詩(shī)松等 , 概率論與數(shù)理統(tǒng)計(jì)教程，北京：高等教育出版社,2004年?！?】 趙靜，但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)3，北京：高等教育出版社，2008年。十、附錄（一）程序/約束條件:岸上仆人不能多于商人數(shù)#include <iostream>using namespace std;struct Nodeint n

9、Mer;int nSer;int length;class Apublic:A();A();void Tspt();/過(guò)河的動(dòng)作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é)點(diǎn)bool noRepeat(int nm,int ns);/沒(méi)有重復(fù)返回TRUEvoid funshow(int a2,int ntail);bool

10、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;/商仆的對(duì)數(shù)int nB;/船最多的載人數(shù)目Node *STEP;A:A()free(STEP);A:A()cout<<"請(qǐng)輸入商仆的對(duì)數(shù):"cin>>n;cout<<"請(qǐng)輸入船最多載人的數(shù)目:"cin>>nB;STEP = (Node *)malloc(sizeof(No

11、de)*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 ;/已找到目標(biāo)狀態(tài)需，輸出數(shù)據(jù)if(top = STEPhead.length)cout<<"* "<<+count<<" *"

12、;<<endl;funshow(p,top + 1);B:top-;if(top = -1)return ;C:stop-;if(STEP(stop).length != top)/退過(guò)了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é)點(diǎn)STEP(stop + 1) if(funLeft(STE

13、P(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)/退過(guò)了，到了下一層stop + 1 = atop + 1;D:stop-;if(STEP(stop).length != top)/退過(guò)了，到了下一層for(int i = top; i <= STEPhead.length; i+)si

14、 = 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

15、(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.nSe

16、r,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) < nB + 1 &

17、& 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;bo

18、ol flag = false;while(head <= tail)if(STEPhead.length%2 = 0)flag = true;elseflag = false;temp = funTspt(STEPhead.nMer,STEPhead.nSer,flag);if(NULL != temp)break;head+;if(head > tail)cout<<"此問(wèn)題無(wú)解!"<<endl;exit(1);doLeft(temp->nMer,temp->nSer,temp->length);/temp->

19、nMer表示headdelete temp;Node* A:funTspt(int nm,int ns,bool flag)/flag = true 向?qū)Π哆\(yùn)輸Node *nd = NULL;int temp = 1;int tM = STEPhead.nMer;/可供運(yùn)輸?shù)纳倘藬?shù)int tS = STEPhead.nSer;/可供運(yùn)輸?shù)钠腿藬?shù)if(flag = false)/向此岸運(yùn)輸tM = n - STEPhead.nMer;tS = n - STEPhead.nSer;temp = -1;for(int i = 0; i < tM + 1 && i < nB

20、 + 1; i+)/i表示運(yùn)輸?shù)纳倘藬?shù)for(int j = 0; j < tS + 1 && j < nB - i + 1; j+)/j表示運(yùn)輸?shù)钠腿藬?shù)if(i + j = 0)continue;int p = STEPhead.nMer - temp*i;int q = STEPhead.nSer - temp*j;if(islegal(p,q) = true && noRepeat(p,q) = true)if(p = 0 && q = 0)tail+;STEPtail.length = STEPhead.length + 1;

21、STEPtail.nMer = p;STEPtail.nSer = q;nd = (Node*)malloc(sizeof(Node);nd->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