商仆过河问题数学建模

1、商仆过河问题作者：*学院*班*2014年12月4日摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型, 并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河 问题的完整求解过程；有效地求解类似多步决策问题的作用。关键词：多步决策计算机求解状态转移律图解法MATLAB?序一、问题的提出S个商人各带一个随从乘船过河，一只小船只能容纳 KA,由他们自己划船。商人们窃 听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何 乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？二、问题的关键解决的关键集中在商人和随从的数

2、量上，以及小船的容量上，该问题就是考虑过河步 骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。三、问题的分析在安全的前提下(两岸的随从数不比商人多)，经有限步使全体人员过河。由于船上人 数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决 策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树.树根是原问题。原问题的解依赖于子问题树中所有子问题的解。四、模型假设记第k次过河前 前的商人数为Xk,随从数为Yk k=1 , 2, ?儿,Yk=0, 1, 2, 3

3、,将二 维向量S=(Xk, Yk)定义为状态.把满足安全渡河条件下的状态集合称为允许状态集合。记作S。则S=(Xk,Yk)|(X K =0,Yk =0,1,2,3),(X k =3,Yk =0,1,2,3),(X k =Yk =1)(Xk =YK =2)记第k次过河船上的商人数为U随从数为M将二维向量DK=(Uk ,Vk)定义为决策.由小船的容量可知允许决策集合(记作 D)为 D=(Uk ,Vk)|U K +V=l,2=(0,1);(0,2);(1,0);(1,1);(2,0)五、模型建立：动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级 一级、规模逐步缩小的子问题。

4、直到可以直接求出其解的子问题为止。分解成所有子问题 按层次关系构成一棵子问题树.树根是原问题。原问题的解依赖于子问题树中所有子问题 的解。用动态规划法分析三名商人的过河问题。可得如下的递归树：1,K=（转下页）A(2,2) B(1,1)A (3,1)B(0,2)(1,0)(0,1)相同情况A(3,2)B(0,1)A(3,2)B(0.1)K=3K=4K=5K=6K=7A(3,0)B(0,3)L(0出A(3,1)B(0,2)A(1,1)B(2,2)(1,1)A(2,2)B(1,1)(2,0)A(0,2)B(3,1)K=8卡L（0出(注解：当K为奇数时,船在B岸；当KM禺数时,船在Ao )通过分析该

5、递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边 界条件。因为k为奇数时，船是从A岸驶向B岸,k为偶数时。船是由B岸驶回 科。所以状态&随 决策D变化的规律是&+i=S+(-1) K D<, k=l , 2, ?,称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题：每一步，船由A岸驶向B岸或B岸驶回A岸，都要对船上的人员(商人U,随从Vk各几人) 作出决策，在保证安全的前提下即两岸的商人数 X都不比随从数Yk少，用有限步使人员全 部过河.用状态(变量)Sk表示某一岸的人员状况，决策(变量)Dk表示船上的人员状况，可 以找出状态&随决策D

6、变化的规律.这样安全过河问题就转化为：求决策D<C D(k=1,2,，n),使得状态SkC S,按照状态转移律，由初始状态Si=(3 , 3),经有限步n到达状态Sk+i=(O,O)模型建立：SK+1=SK+(-1)KDK k=l,2 , 3,其中 DK C D=(UK ,VK)|UK +VK=l , 2, 其中 SK (XK ,YK)|(XK=0 , YK =1, 2, 3); (XK =3, YK=0,1,2,3);(XK =YK =1,2),Sn+1 =(0,0)这就是三个商人的过河问题模型。六、模型求解：穷举法：计算机编程(见附)先建立编程的基本过程，然后考虑模型，再编写程序。然

7、后就可以得出结果了。开始主程序流程图图解法：状态s=(x,y) 16 个格点允许状态 10个点允许决策移动1或2格;k奇，左下移;k偶，右上移.0Sn+1123 x总共需要11步可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。八、模型的检验用2名商人和2名随从的过河问题的解决思路，检验 3名商人和3名随从的过河问题。九、模型的拓展和延伸通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计 mg商人和n名随从的过河问题。十、总结这是通过数学分析的方法解决实

8、用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题,很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。参考文献：(1)傅清祥.数据结构与算法.王晓东.北京：电子工业出版社1998 .(2)姜启瑟.数学建模(第二版).北京：高等教育出版社，2000.(3)运筹学教材编写组.运筹学(修订版).北京：清华大

9、学出版社。2001.附：商仆过河的C程序及运行截屏：#include <iostream>using namespace std;struct Node int 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);/ 添力口 ST

10、EPhead可以向后延伸的节点bool noRepeat(int nm,int ns);/没有重复返回 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;/商仆的对数int nB;/船最多的载人数目Node *STEP;A:A()free(STEP);A:A()cout<<"请输入商仆的对数S="

11、F: cin>>n;if(n=1)nB=2;cout«"船最多载人的数目 K="«nB;else if(n=2)(cout«"船最多载人的数目可以取：for(int x=n;x<=2*n;x+)(cout«x«"、)cout«endl;cout«"请输入船最多载人的数目K="cin»nB;)else if(n=3)(cout«"船最多载人的数目可以取：for(int x=n-1 ;x<=2*n;x+)(cout&

12、#171;x«"、)cout«endl;cout«"请输入船最多载人的数目K="cin»nB;)else if(n=4)(cout«"船最多载人的数目可以取：for(int x=n-1 ;x<=2*n;x+)(cout«x«"、)cout«endl;cout«"请输入船最多载人的数目K="cin»nB;)else if(n>=5&&n<=100)(cout«"船最多载人的数

13、目可以取：for(int x=4;x<=2*n;x+)(cout«x«"、cout«endl;cout«"请输入船最多载人的数目K="cin»nB;)else if(n<1|n>100)cout<<"本程序仅在S=(0。)以内保证其正确性"<<endl;cout<<"请重新输入商仆的对数S="goto F；STEP = (Node *)malloc(sizeof(Node)*10000);memset(STEP,0,siz

14、eof(Node)*10000);head = tail = 0;STEP0.nMer = STEP0.nSer = n;int main()cout<<”问题描述：S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他 们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多， 就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身 安全？ "<<endl;A a;a.Tspt();return 0;void A:show(int s口,int p2,int &top,int &count,int

15、 a)if(top = -1)return ;/已找到目标状态需，输出数据if(top = STEPhead.length)return ;cout<<"I*“<<+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) got

16、o C;ptop0 = STEP(stop).nMer;ptop1 = STEP(stop).nSer;show(s,p,top,count,a);return ;在中间加入节点 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 ;E:D:else/不符合条件stop + 1-;if(STEP(stop + 1).length = top)/

17、stop + 1 = atop + 1;stop-;if(STEP(stop).length != top)/退过了，到了下一层退过了，到了下一层for(int i = top; i <= STEPhead.length; i+)si = ai;top-;if(top = -1)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,coun

18、t,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,8

19、000);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

20、);bool A二funLeft(Node nd,int b1,int b2,int n) bool flag = abs(nd.nMer - b1) + abs(nd.nSer - b2) < nB + 1&& 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 <

21、= nd.nMer && b2 <= nd.nSer)return true;return false;void A:Tspt()Node *temp = new Node;temp = NULL;bool 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

22、)cout<<”此问题无解！"<<endl;exit；表示headdoLeft(temp->nMer,temp->nSer,temp->length);/temp->nMer delete 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) / 向此

23、岸运输 tM = n - STEPhead.nMer;tS = n - STEPhead.nSer;temp = -1;for(int i = 0; i < tM + 1 && i < nB + 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)

24、= true && noRepeat(p,q) = true)if(p = 0 && q = 0)tail+;STEPtail.length = STEPhead.length + 1;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 < ta