商人过河的数学模型及编程解决

1、14对商仆过河问题题目有14名商人各带一名仆人要过河，但船最多能载4人。商人已获得仆人的阴谋：在河的任意一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取货物。安排如何乘船的权利权利在商人手上，试为商人制定一个安全的过河方案。一摘要n对商仆过河，一只船最多载m人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）。二问题提出：有14对商仆乘船过河，一只船最多载4人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才

2、能安全渡河？三问题分析商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到

3、渡河的目标。现在我们都把它们数量化：即用数学语言来表示。四模型假设与符号假设（一）模型假设商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。（二）符号假设设（x，y）是状态向量，表示任一岸的商人和仆人数，且x，y分别要大于等于0，小于等于M。1.设（m，n）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。2.设用s表示所有的可取状态向量的集合。3.设用d表示所有运载向量的集合。4.设用 表示从此岸到彼岸，作减；用 表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（Sk属于s）

4、；dk：表示第k步可取转移向量（dk属于d）；五模型的建立 我们以3名商人为例。设第k次渡河前此岸的商人数为xk，随从数为yk，k=1，2，xk，yk =0，1，2，3，将二维向量Sk =（xk，yk）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为：S=（x，y）|x = 0或3，y = 0，1，2，3，x = y = 1，2 （1）又设第k次渡船上的商人数为uk，随从数为vk，将二维向量dk=（uk+ vk）定义为决策。则允许决策集合为：D=（u，v）| u + v = 1，2 （2）因为k为奇数时船从此岸驶向彼岸，k为偶数时船由彼岸驶向此岸，所以状态Sk随着

5、决策dk变化的规律即状态转移规律是：Sk+1 = Sk +（- 1）k dk （3）这样，制定安全渡河方案归结为如下的多步决策问题：求决策dk D（k = 1，2，n），使状态Sk S按照规律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态Sn+1=（0，0）。六模型的简化与求解下面通过程序给出这个多步决策问题的一个解： 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个允许的状态*） d1=0，2；d2=2，0；d3=1，1；d4=0，1； d5=1，0； （*以上表示

6、给出5个允许的决策*） i=1；j=1；k=1；s0=s1=3，3； Print此岸船上对岸； Do Dosi+1=si+（-1）i dj； t=0； DoIfsi+1= =ak，t=1，k，1，10； Ift= =0，Continue ； （*以上是保证状态属于允许的状态*） 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 程序运行结果如下： 此岸船上对岸 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 可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。渡河的整个过程如下所示： 去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随从）（渡河成功）七、结果分析与检验八、模型的优缺点与改进方向九、参考文献【1】 茆诗松等 , 概率论与数理统计教程，北京：高等教育出版社,2004年。【2】 赵静，但琦，数学建模与数学实验3，北京：高等教育出版社，2008年。十、附录（一）程序/约束条件:岸上仆人不能多于商人数#include <iostream>using namespace std;struct Nodeint n

9、Mer;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可以向后延伸的节点bool noRepeat(int nm,int ns);/没有重复返回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;/商仆的对数int nB;/船最多的载人数目Node *STEP;A:A()free(STEP);A:A()cout<<"请输入商仆的对数:"cin>>n;cout<<"请输入船最多载人的数目:"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 ;/已找到目标状态需，输出数据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)/退过了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 ;/在中间加入节点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)/退过了，到了下一层stop + 1 = atop + 1;D:stop-;if(STEP(stop).length != top)/退过了，到了下一层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<<"此问题无解!"<<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 向对岸运输Node *nd = NULL;int temp = 1;int tM = STEPhead.nMer;/可供运输的商人数int tS = STEPhead.nSer;/可供运输的仆人数if(flag = false)/向此岸运输tM = n - STEPhead.nMer;tS = n - STEPhead.nSer;temp = -1;for(int i = 0; i < tM + 1 && i < nB

20、 + 1; i+)/i表示运输的商人数for(int j = 0; j < tS + 1 && j < nB - i + 1; j+)/j表示运输的仆人数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