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

1、摘要：M对商仆过河，一只船最多载N人，船上和岸上的仆人数都不能多于商人数，否则商人有危险。安排合理的渡河方案，保证商人能安全渡河。（可利用向量，矩阵，图解等方法）一 问题提出：有M对商仆乘船过河，一只船最多载N人，由商人和仆人自己划船渡河，在河的任意一岸，一旦仆人数多于商人数，仆人就可将商人杀死，谋取利益，但是乘船渡河的主动权掌握在商人们手中，商人们如何安排渡河方案，才能安全渡河？二 假设：商人和仆人都会划船，天气很好，无大风大浪，船的质量很好，船桨足够很多次的运载商人和仆人。三 参数：1 设（x，y）是状态向量，表示任一岸的商人和仆人数，并且x，y分别要大于等于0，小于等于M。2 设（m，n

2、）是运载向量，表示运载的商人数和仆人数，0<=m<=N，0<=n<=N，0<=m+n<=N。3 设用s表示所有的可取状态向量的集合。4 设用d表示所有运载向量的集合。5 设用 表示从此岸到彼岸，作减；用 表示从彼岸到此岸，作加。Sk：表示第k步可取状态向量（sk属于s）；dk：表示第k步可取转移向量（dk属于d）；四 问题分析：商仆安全渡河问题可以视为一个多步决策过程，多步决策是指决策过程难以一次完成，而是多步优化，最后获取一个全局最优方案的决策方法。对于每一步，即船由此岸驶向彼岸，或者船由彼岸驶向此岸的决策，不仅会影响到该过程的效果，而且还会影响到下一步的

3、初始状态，从而对整个过程都会有影响。所以，在每一次过河时，就不能只从这一次过河本身考虑，还要把它看成是整个过河过程中的一个部分。在对船上的人员做决策时，要保证两岸的商人数不能少于仆人数，用最少的步伐是人员全部过河。应用状态向量和运载向量，找出状态随运载变化的规律，此问题就转化为状态在允许范围内（即安全渡河条件），确定每一次该如何过河，从而达到渡河的目标。现在我们都把它们数量化：即用数学语言来表示。 我们以3名商人为例设第k次渡河前此岸的商人数为xk，随从数为yk，k=1，2，xk，yk =0，1，2，3，将二维向量Sk =（xk，yk）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为

4、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）k dk （3）这样，制定安全渡河方案归结为如下的多步决策问题：求决策dk D（k = 1，2，n），使状态Sk S按照规律（3），由初始状态S1=（3，3）经有限步（设为n）到达状态Sn+

5、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； （*以上表示给出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 ； （*以上是保证状

6、态属于允许的状态*） 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，- - - -，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，

7、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随从）（3商人0随从） 去2商人 回1商人1随从（3商人1随从）（1商人1随从） 去2商人 回1随从（2商人2随从）（0商人2随从） 去2随从 回1随从（0商人3随从）（0商人1随从） 去2随从 （0商人2随从）（渡河成功）一 程序实现 #include "

8、;stdio.h"#include "string.h"#include <memory> #include <stdlib.h> #include<iostream>using namespace std;#include "conio.h"FILE *fp;/*设立文件指针，以便将它用于其他函数中*/struct along m,s;struct a *next;/*数组类型a：记录各种情况下船上的商人和仆人数，m：代表商人数s：代表仆人数*/struct a *jj,head;/*head为头指针的链表

9、单元（船上的人数的各种情况的链表）*/int n,total=0,js=0;/*total表示船上各种情况总数*/struct aim long m1,s1,m2,s2;int n;struct aim *back,*next;/*用于建立双向的指针链表，记入符合的情况，m1，s1表示要过岸的商人数和仆人数；m2，s2表示过岸了的商人数和仆人数，n表示来回的次数*/int k1,k2;void freeit(struct aim *p)struct aim *p1=p; p1=p->back;free(p);if(p1!=NULL)p1->next=NULL;return;/*释放

10、该单元格，并将其上的单元格的next指针还原*/ int determ(struct aim *p) struct aim *p1=p;if(p->s1>k2)return -1;/*仆人数不能超过总仆人数*/if(p->m1>k1)return -1;/*商人数不能超过总商人数*/if(p->s2>k2)return -1;/*对岸，同上*/if(p->m2>k1)return -1;/*对岸，同上*/if(p->s1<0)return -1;/*仆人数不能为负*/if(p->s2<0)return -1;/*商人数不能

11、为负*/if(p->m1<0)return -1;/*对岸，同上*/if(p->m2<0)return -1;/*对岸，同上*/if(p->m1!=0)if(p->s1>p->m1)return -1;if(p->m2!=0)if(p->s2>p->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

12、)if(p1->m1=p->m1)if(p1->m2=p->m2)return -1;/*用于解决重复，算法思想：即将每次算出的链表单元与以前的相比较，若重复，则表示出现循环*/if(p->s1=0&&p->m1=0)if(p->n%2=0)return 1;else return -1;/*显然如果达到条件就说明ok了*/return 0;/*判断函数*/int sign(int n)if(n%2=0)return -1;return 1;/*符号函数*/void copyit(struct aim *p3,struct aim *p

13、)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所指向的链表单元中*/void print(struct aim *p3)struct aim *p=p3;js+;while(p->back)p=p->back;printf("n第%d种方法:n",js);fprintf(fp,"n第

14、%d种方法:n",js);int count=0;while(p) printf("%ld,%ld%ld,%ldt",p->m1,p->s1,p->m2,p->s2);fprintf(fp,"%ld,%ld%ld,%ldt",p->m1,p->s1,p->m2,p->s2);p=p->next;count+;cout<<"一共有"<<count<<"步完成"<<endl;/*打印函数，将p3所指的内容打印

15、出来*/void trans(struct aim *p)struct aim *p3;/*p3为申请的结构体指针*/struct a *fla;int i,j,f;fla=&head;p3=(struct aim *)malloc(sizeof(struct aim);f=sign(p->n);for(i=0;i<total;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;

16、/*运算过程，即过河过程*/j=determ(p3);/*判断，j记录判断结果*/if(j=-1)if(i<total-1)continue;elsefreeit(p3);break;int count1=0;if(j=1)if(i<total-1)print(p3);count1+;continue;elseprint(p3);count1+;freeit(p3);break;/cout<<count1<<endl;printf("%d",count1);printf("n");if(j=0)trans(p3);re

17、turn;/*转移函数，即将人转移过河*/*n=0*/void main() struct aim *p,*p1;int j,a,e,f;struct a *flag;/*flag是用与记录头指针*/;if(fpt=fopen("c:result.dat","w+")=0)printf("cant creat itn");exit(0);fp=fpt; system("cls"); printf("问题描述:三个商人各带一个随从乘船过河，一只小船只能容纳X人，由他们自己划船。三个商人窃听到随从们密谋，在河

18、的任意一岸上，只要随从的人数比商人多，就杀掉商人。但是如何乘船渡河的决策权在商人手中，商人们如何安排渡河计划确保自身安全？n"); printf("n"); p=(struct aim *)malloc(sizeof(struct aim);p->back=NULL;p->next=NULL;p->s2=0;p->m2=0;p->n=1;/*设立初始头指针*/printf("请输入船上最多能乘多少人n");fprintf(fp,"请输入船上的人数n");scanf("%d",&n);fprintf(fp,"n%dn",n);flag=&head;for(e=0;e<=n;e+) for(f=0;f<=n;f+) if(e+f>0&&e+f<=n) total+; jj=(struct a*)malloc(sizeof(struct a); jj->m=e; jj->s=f; flag->next=jj; jj-