商仆过河问题——数学建模

数学建模论文-1-商仆过河问题作者：*学院**班***************号2014年12月4日数学建模论文-2-摘要：为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机编程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。关键词：多步决策计算机求解状态转移律图解法MATLAB程序一、问题的提出S个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？二、问题的关键解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。三、问题的分析在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。四、模型假设记第k次过河前A岸的商人数为XK，随从数为YKk=1，2，⋯XK,YK=0，1，2，3，将二维向量SK=(XK，YK)定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作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次过河船上的商人数为UK，随从数为VK将二维向量DK=(UK,VK)定义为决策．由小船的容量可知允许决策集合（记作D)为D={(UK,VK)|UK+VK=l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)}数学建模论文-3-五、模型建立：动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。用动态规划法分析三名商人的过河问题。可得如下的递归树：K=1A(3,2)B(0,1)A(3,2)B(0.1)K=2A（3,1）B(0,2)(0,1)A（2,2）B(1,1)（0，2）A(3,0)B(0,3)(1,1)(2,0)（3,3）（1,1）(1,0)相同情况K=3(0,2)A(3,1)B(0,2)K=4K=5(0,1)(2,0)A(1,1)B(2,2)K=6A(2,2)B(1,1)K=7=A(0,2)B(3,1)K=8(0,1)数学建模论文-4-（转下页）（注解：当K为奇数时，船在B岸；当K为偶数时，船在A岸。）通过分析该递归树，知道求解关键在于正确地写出基本的状态转移关系式和恰当的边界条件。因为k为奇数时，船是从A岸驶向B岸，k为偶数时。船是由B岸驶回A岸。所以状态SK随决策DK变化的规律是SK+1=SK+(-1)KDK，k=l，2，⋯，称之为状态转移律，这样，制定过河方案就归结为如下的多步决策问题：每一步，船由A岸驶向B岸或B岸驶回A岸，都要对船上的人员(商人UK，随从VK各几人)作出决策，在保证安全的前提下即两岸的商人数XK都不比随从数YK少，用有限步使人员全部过河．用状态(变量)SK表示某一岸的人员状况，决策(变量)DK表示船上的人员状况，可以找出状态SK随决策DK变化的规律．这样安全过河问题就转化为：求决策DK∈D(k=1,2，……，n)，使得状态SK∈S，按照状态转移律，由初始状态S1=(3，3)，经有限步n到达状态SK+1=(O,O)。模型建立：SK+1=SK+(-1)KDK，k=l,2，3，其中DK∈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)这就是三个商人的过河问题模型。A(0,3)B(3,0)K=9(0,2)A(0,1)B(3,2)A(1,1)B(2,2)A(0,2)B(3,1)(1,0)(0,1)A(0,0)B(3,3)K=10K=11数学建模论文-5-六、模型求解：穷举法：计算机编程（见附）先建立编程的基本过程，然后考虑模型，再编写程序。然后就可以得出结果了。开始变量赋值初始化判断是否完全过河选择一种可行方案，进行过河或返回，得到新的状态否判断是不是允许状态集合中的状态，并且还没在已经考虑的状态中是否还有其他状态否结束是是是数学建模论文-6-主程序流程图图解法：状态s=(x,y)16个格点允许状态10个●点允许决策移动1或2格;k奇,左下移;k偶,右上移.总共需要11步可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。八、模型的检验用2名商人和2名随从的过河问题的解决思路，检验3名商人和3名随从的过河问题。九、模型的拓展和延伸通过三名商人和三名随从的过河问题的解决方案，可以进一步计算四名商人和四名随从的过河问题，通过计算机编程可以设计m名商人和n名随从的过河问题。xy3322110S1sn+1d1d11数学建模论文-7-十、总结这是通过数学分析的方法解决实用问题，经过问题提出、问题假设、问题分析、模型建立、模型求解、模型检验的过程，解决商人过河问题。然后扩展延伸到n个商人的问题。学习数学建模以来，重新认识了学习数学的乐趣，也重新认识了数学，本以为数学是单调的，枯燥的，学习了之后，发现数学是普遍存在我们生活之中的。解决现实中的问题，很多都需要数学。沉浸在数学的世界里，发现学习是有趣的；相比于机械的认识各个组织器官，建立一个数学模型解决问题是十分有趣的。参考文献：（1）傅清祥．《数据结构与算法》．王晓东．北京：电子工业出版社1998．（2）姜启瑟．《数学建模》(第二版)．北京：高等教育出版社，2000．（3）运筹学教材编写组．《运筹学》(修订版)．北京：清华大学出版社。2001．附：商仆过河的C程序及运行截屏:#includeiostreamusingnamespacestd;structNode{intnMer;intnSer;intlength;};classA{public:A();~A();voidTspt();//过河的动作voiddoLeft(intnhead,intntail,intnlength);private:boolislegal(intnm,intns);//判断是否满足约束条件，满足为trueNode*funTspt(intnm,intns,boolflag);//添加STEP[head]可以向后延伸的节点boolnoRepeat(intnm,intns);//没有重复返回TRUEvoidfunshow(inta[][2],intntail);boolfunLeft(Nodend,intb1,intb2,intn);voidshow(ints[],intp[][2],int&top,int&count,inta[]);inthead;数学建模论文-8-inttail;intn;//商仆的对数intnB;//船最多的载人数目Node*STEP;};A::~A(){free(STEP);}A::A(){cout请输入商仆的对数S=;F:cinn;if(n==1){nB=2;cout船最多载人的数目K=nB;}elseif(n==2){cout船最多载人的数目可以取:;for(intx=n;x=2*n;x++){coutx、;}coutendl;cout请输入船最多载人的数目K=;cinnB;}elseif(n==3){cout船最多载人的数目可以取:;for(intx=n-1;x=2*n;x++){coutx、;}coutendl;cout请输入船最多载人的数目K=;cinnB;}elseif(n==4){cout船最多载人的数目可以取:;for(intx=n-1;x=2*n;x++)数学建模论文-9-{coutx、;}coutendl;cout请输入船最多载人的数目K=;cinnB;}elseif(n=5&&n=100){cout船最多载人的数目可以取:;for(intx=4;x=2*n;x++){coutx、;}coutendl;cout请输入船最多载人的数目K=;cinnB;}elseif(n1||n100){cout本程序仅在S=(0…100)以内保证其正确性endl;cout请重新输入商仆的对数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个商人各带一个随从乘船过河，一只小船只能容纳K人，由他们自己划船。商人们窃听到随从们密谋，在河的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？endl;Aa;a.Tspt();return0;}voidA::show(ints[],intp[][2],int&top,int&count,inta[]){if(top==-1)数学建模论文-10-return;//已找到目标状态需，输出数据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;}//在中间加入节点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)//退过了，到了下一层{数学建模论文-11-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])].nMe