您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 企业财务 > 商人过河的数学模型及编程解决
摘要:M对商仆过河,一只船最多载N人,船上和岸上的仆人数都不能多于商人数,否则商人有危险。安排合理的渡河方案,保证商人能安全渡河。(可利用向量,矩阵,图解等方法)一.问题提出:有M对商仆乘船过河,一只船最多载N人,由商人和仆人自己划船渡河,在河的任意一岸,一旦仆人数多于商人数,仆人就可将商人杀死,谋取利益,但是乘船渡河的主动权掌握在商人们手中,商人们如何安排渡河方案,才能安全渡河?二.假设:商人和仆人都会划船,天气很好,无大风大浪,船的质量很好,船桨足够很多次的运载商人和仆人。三.参数:1.设(x,y)是状态向量,表示任一岸的商人和仆人数,并且x,y分别要大于等于0,小于等于M。2.设(m,n)是运载向量,表示运载的商人数和仆人数,0=m=N,0=n=N,0=m+n=N。3.设用s表示所有的可取状态向量的集合。4.设用d表示所有运载向量的集合。5.设用表示从此岸到彼岸,作减;用表示从彼岸到此岸,作加。Sk:表示第k步可取状态向量(sk属于s);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随着决策dk变化的规律即状态转移规律是:Sk+1=Sk+(-1)kdk(3)这样,制定安全渡河方案归结为如下的多步决策问题:求决策dk∈D(k=1,2,…,n),使状态Sk∈S按照规律(3),由初始状态S1=(3,3)经有限步(设为n)到达状态Sn+1=(0,0)。模型的解答下面通过程序给出这个多步决策问题的一个解,a[1]={0,0};a[2]={0,1};a[3]={0,2};a[4]={0,3};a[5]={3,0};a[6]={3,1};a[7]={3,2};a[8]={3,3};a[9]={1,1};a[10]={2,2};(*以上给出10个允许的状态*)d[1]={0,2};d[2]={2,0};d[3]={1,1};d[4]={0,1};d[5]={1,0};(*以上表示给出5个允许的决策*)i=1;j=1;k=1;s[0]=s[1]={3,3};Print[″此岸————船上————对岸″];Do[Do[s[i+1]=s[i]+(-1)^id[j];t=0;Do[If[s[i+1]==a[k],t=1],{k,1,10}];If[t==0,Continue[]];(*以上是保证状态属于允许的状态*)l=Mod[i+1,2];m=l;u=0;If[i+1=3,Do[If[s[i+1]==s[m],u=1,Break[]],{m,l,i-1,2}]];If[u==0,c[i+1]=d[j];Break[]],{j,1,5}];If[t==0,Print[No,Result];Break[]];b[i+1]={3,3}-s[i+1];Print[s[i],″----″,c[i+1],″----″,b[i+1]];If[s[i+1]=={0,0},Break[]],{i,1,12}]程序运行结果如下:此岸——————船上——————对岸{3,3}——————{0,2}——————{0,2}{3,1}——————{0,1}——————{0,1}{3,2}——————{0,2}——————{0,3}{3,0}——————{0,1}——————{0,2}{3,1}——————{2,0}——————{2,2}{1,1}——————{1,1}——————{1,1}{2,2}——————{2,0}——————{3,1}{0,2}——————{0,1}——————{3,0}{0,3}——————{0,2}——————{3,2}{0,1}——————{0,1}——————{3,1}{0,2}——————{0,2}——————{3,3}可以得出经过11步的渡河就能达到安全渡河的目标及满足渡河的次数尽量少的条件。这11步的渡河方案就是上面程序运行结果中船上下面的一列。渡河的整个过程如下所示:去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随从)—————→(渡河成功)一.程序实现#includestdio.h#includestring.h#includememory#includestdlib.h#includeiostreamusingnamespacestd;#includeconio.hFILE*fp;/*设立文件指针,以便将它用于其他函数中*/structa{longm,s;structa*next;};/*数组类型a:记录各种情况下船上的商人和仆人数,m:代表商人数s:代表仆人数*/structa*jj,head;/*head为头指针的链表单元(船上的人数的各种情况的链表)*/intn,total=0,js=0;/*total表示船上各种情况总数*/structaim{longm1,s1,m2,s2;intn;structaim*back,*next;};/*用于建立双向的指针链表,记入符合的情况,m1,s1表示要过岸的商人数和仆人数;m2,s2表示过岸了的商人数和仆人数,n表示来回的次数*/intk1,k2;voidfreeit(structaim*p){structaim*p1=p;p1=p-back;free(p);if(p1!=NULL)p1-next=NULL;return;}/*释放该单元格,并将其上的单元格的next指针还原*/intdeterm(structaim*p){structaim*p1=p;if(p-s1k2)return-1;/*仆人数不能超过总仆人数*/if(p-m1k1)return-1;/*商人数不能超过总商人数*/if(p-s2k2)return-1;/*对岸,同上*/if(p-m2k1)return-1;/*对岸,同上*/if(p-s10)return-1;/*仆人数不能为负*/if(p-s20)return-1;/*商人数不能为负*/if(p-m10)return-1;/*对岸,同上*/if(p-m20)return-1;/*对岸,同上*/if(p-m1!=0)if(p-s1p-m1)return-1;if(p-m2!=0)if(p-s2p-m2)return-1;/*两岸商人数均不能小于仆人数*/while(p1!=NULL){p1=p1-back;if(p1!=NULL)if(p1-n%2==p-n%2)if(p1-s1==p-s1)if(p1-s2==p-s2)if(p1-m1==p-m1)if(p1-m2==p-m2)return-1;}/*用于解决重复,算法思想:即将每次算出的链表单元与以前的相比较,若重复,则表示出现循环*/if(p-s1==0&&p-m1==0)if(p-n%2==0)return1;elsereturn-1;/*显然如果达到条件就说明ok了*/return0;}/*判断函数*/intsign(intn){if(n%2==0)return-1;return1;}/*符号函数*/voidcopyit(structaim*p3,structaim*p){p3-s1=p-s1;p3-s2=p-s2;p3-m1=p-m1;p3-m2=p-m2;p3-n=p-n+1;p3-back=p;p3-next=NULL;p-next=p3;}/*复制内容函数,将p中的内容写入p3所指向的链表单元中*/voidprint(structaim*p3){structaim*p=p3;js++;while(p-back){p=p-back;}printf(\n第%d种方法:\n,js);fprintf(fp,\n第%d种方法:\n,js);intcount=0;while(p){printf(%ld,%ld——》%ld,%ld\t,p-m1,p-s1,p-m2,p-s2);fprintf(fp,%ld,%ld——》%ld,%ld\t,p-m1,p-s1,p-m2,p-s2);p=p-next;count++;}cout一共有count步完成endl;}/*打印函数,将p3所指的内容打印出来*/voidtrans(structaim*p){structaim*p3;/*p3为申请的结构体指针*/structa*fla;inti,j,f;fla=&head;p3=(structaim*)malloc(sizeof(structaim));f=sign(p-n);for(i=0;itotal;i++){fla=fla-next;copyit(p3,p);p3-s1-=fla-m*f;p3-m1-=fla-s*f;p3-s2+=fla-m*f;p3-m2+=fla-s*f;/*运算过程,即过河过程*/j=determ(p3);/*判断,j记录判断结果*/if(j==-1){if(itotal-1){continue;}else{freeit(p3);break;}}intcount1=0;if(j==1){if(itotal-1){print(p3);count1++;continue;}else{print(p3);count1++;freeit(p3);break;}//coutcount1endl;printf(%d,count1);printf(\n);}if(j==0)trans(p3);}return;}/*转移函数,即将人转移过河*//*n=0*/voidmain(){structaim*p,*p1;intj,a,e,f;structa*flag;/*flag是用与记录头指针*/FILE*fpt;if((fpt=fopen(c:result.dat,w+))==0){printf(can′tcreatit\n);exit(0);}fp=fpt;system(cls);printf(问题描述:三个商人各带一个随从乘船过河,一只小船只能容纳X人,由他们自己划船。三个商人窃听到随从们密谋,在河的任意一岸上,只要随从的人数比商人多,就杀掉商人。但是如何乘船渡河的决策权在商人手中,商人们如何安排渡河计划确保自身安全?\n)
本文标题:商人过河的数学模型及编程解决
链接地址:https://www.777doc.com/doc-3347774 .html