商人们怎样安全过河 (附MATLAB程序完整)

学号：20092122103 姓名：郑少钊数学实验作业实验一商人们怎样安全过河有3个商人带着随从要过一条河。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是乘船渡河的方案由商人决定，商人们怎样才能安全过河。

假设每人都会划船，小船一次只能容纳2人，且船载起始岸边。

请给出安全过河的最佳方案。

解：模型建立：用三元组（x,y,z）表示渡河过程中的某个状态x-----起始岸边上商人的个数y-----起始岸边随从的个数z-----小船的位置（z为1时，表示小船在起始岸边，为0时，表示小船在目的的岸边）其中一种方案：（3，3，0）---（2，2，1）---（3，2，0）---（3，0，1）---（3，1，0）---（1，1，1）---（2，2，0）---（0，2，1）---（.0，3，0）---（0，1，1）---（0，2，0）---（0，0，1）实验四最短总航线问题下表给出世界六大城市（伦敦、墨西哥城、纽约、巴黎、北京和东京）之间的航线距离（以英里为单位），试确定连通这六大城市的最短总航线。

解：由上表可得图如下：A:伦敦；B:墨西哥城；C:纽约；D:巴黎；E:北京；F:东京用MATLAB软件求解，代码如下：（Prim算法）cleara=[0 5558 3469 214 5074 5959;5558 0 2090 5725 7753 7035;3469 2090 0 3636 6844 6757;214 5725 3636 0 5120 6053;5074 7753 6844 5120 0 1307;5959 7035 6757 6053 1307 0;]T=[];c=0;v=1;n=6;sb=2:n;for j=2:nb(1,j-1)=1;b(2,j-1)=j;b(3,j-1)=a(1,j);endwhile size(T,2)<n-1[tmin,i]=min(b(3,:));T(:,size(T,2)+1)=b(:,i)c=c+b(3,i);v=b(2,i);temb=find(sb==b(2,i));sb(temb)=[];b(:,i)=[];for j=1:length(sb)d=a(v,b(2,j));if d<b(3,j)b(1,j)=v;b(3,j)=d;endendendT,c结果如下：T =1 1 3 1 54 3 25 6214 3469 2090 5074 1307c =12154因此，上图的最小生成树的边集合为｛（1，4），（1，3），（3，2），（1,5）,(5,6) ｝，最短总航线为12154.实验一求最短路问题求图14.9所示的有向网络中点1到点6的最短有向路。

商人们怎样安全过河随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析：决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河. 建立模型xk~第k次渡河前此岸的商人数 xk, yk=0,1,2,3;yk~第k次渡河前此岸的随从数 k=1,2,|....sk=(xk , yk)~过程的状态 S ~ 允许状态集合S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}uk~第k次渡船上的商人数 uk, vk=0,1,2;vk~第k次渡船上的随从数 k=1,2,.....dk=(uk , vk)~决策 D={(u , v) u+v=1, 2} ~允许决策集合~状态转移律多步决策问题求dk D(k=1,2, n), 使sk S, 并按转移律由s1=(3,3)到达 sn+1=(0,0).模型求解穷举法~ 编程上机S={(x , y) x=0, y=0,1,2,3;x=3, y=0,1,2,3;x=y=1,2}图解法状态s=(x,y) ~ 16个格点允许状态~ 10个点允许决策 ~ 移动1或2格; k奇,左下移; k偶,右上移.d1,.......，d11给出安全渡河方案评注和思考规格化方法,易于推广考虑4名商人各带一随从的情况程序%%%%%%%%%%%%%%%% 开始 %%%%%%%%%%%%%%%%%%%%%%function jueche=guoheclear allclc%%%%%%%%%%程序开始需要知道商人和仆人数；%%%%%%%%%%%%%shangren=input('输入商人数目: ');puren=input('输入仆人数目: ');rongliang=input('输入船的最大容量: ');if puren>shangrenshangren=input('输入商人数目:');puren=input('输入仆人数目:');rongliang=input('输入船的最大容量:');end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1；for i=0:rongliangfor j=0:rongliangif (i+j<=rongliang)&(i+j>0) % 满足条D={(u,v)|1<=u+v<=rongliang,u,v=0,1,2}d(jc,1:3)=[i,j ,1]; %生成一个决策向量立刻扩充为三维；d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量；jc=jc+2; % 由于生成两个决策向量，则jc要向下移动两个；endendj=0;end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成kx=1; % 状态向量放在A矩阵中，生成方法同矩阵生成；for i=shangren:-1:0for j=puren:-1:0if ((i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))% (i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))为可以存在的状态的约束条件 A(kx,1:3)=[i,j,1]; %生成状态数组集合D `A(kx+1,1:3)=[i,j,0];kx=kx+2;endj=puren;end;%%%%%%%%%%%%%%% 将状态向量生成抽象矩阵%%%%%%%%%%%%%%%%%%%k=(1/2)*size(A,1);CX=zeros(2*k,2*k);a=size(d,1);for i=1:2*kfor j=1:ac=A(i,:)+d(j,:) ;x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ; v(i,x)=1; %x为空不会改变v值endend%%%%%%%%%%%%%%%%%%%%%%dijstra算法%%%%%%%%%%%%%%%%%%%%%%%%%%x=1; y=size(A,1);m=size(v,1);T=zeros(m,1);T=T.^-1;lmd=T;P=T;S=zeros(m,1);S(x)=1;P(x)=0; lmd(x)=0;k=x;while(1)a=find(S==0);aa=find(S==1);if size(aa,1)==mbreak;endfor j=1:size(a,1)pp=a(j,1);if v(k,pp)~=0if T(pp)>(P(k)+v(k,pp))T(pp)=(P(k)+v(k,pp));lmd(pp)=k;endendendmi=min(T(a));if mi==infbreak;d=find(T==mi);d=d(1);P(d)=mi;T(d)=inf;k=d;S(d)=1;endendif lmd(y)==infjueche='can not reach(不能过河)';return;endjueche(1)=y;g=2; h=y;while(1)if h==xbreak;endjueche(g)=lmd(h);g=g+1;h=lmd(h);endjueche=A(jueche,:);jueche(:,3)=[]; %%%%%%%%%%%%%%%%%% 程序完 %%%%%%%%%%%%%%%%%%欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造全网一站式需求。

数学建模课程作业论文题目：对商人过河问题的研究指导教师：黄光辉小组成员：黄志宇（20156260）车辆工程04班牛凯春（20151927）电气工程05班文逸楚（20150382）工商管理02班一、问题重述3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？二、问题分析本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。

对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。

对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标。

三、模型假设1.过河途中不会出现不可抗力的自然因素。

2.当随从人数大于商人数时，随从们不会改变杀人的计划。

3．船的质量很好，在多次满载的情况下也能正常运作。

4.随从会听从商人的调度，所有人都到达河对岸。

四、符号说明第k次渡河前此岸的商人数第k次渡河前此岸的随从数过程的状态向量允许状态集合第k次渡船上的商人数第k次渡船上的随从数决策向量允许决策集合x y 3322110s 1s n +1d 1d 11五、模型建立本题为多步决策模型，每一次过河都是状态量的转移过程。

用二维向量表示过程的状态，其中分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中则允许状态集合:=又将二维向量定义为决策，则允许的决策合集为:因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是该式称为状态转移律。

求决策，使,并按照转移律，由经过有限步n 到达状态六、模型求解本模型使用MATLAB 软件编程，通过穷举法获得决策方案如下(完整matlab 程序详见附录):初始状态：可用图片表示为：X0=33状态为:S =3132303111220203010200决策为:D =0201020120112001020102七、模型推广该商人和随从过河模型可以完美解决此类商人过河的决策问题，并且该模型还可推广至解决m个商人和n个随从过河，以及小船的最大载重人数改变时的问题，只需适当地改变相关的语句即可轻松实现模型的转换。

数学建模试验一陈述 【1 】试验标题：研讨商人过河问题一.试验目标：编写一个程序（可所以C,C++或Mathlab ）实现商人安然过河问题.二.试验情形：Turbo c 2.0..Matlab 6.0以上三.试验请求：请求该程序不但能找出一组安然过河的可行筹划,还可以得到所有的安然过河可行筹划.并且该程序具有必定的可扩大性,即不但可以实现3个商人,3个侍从的过河问题.还应能实现n 个商人,n 个侍从的过河问题以及n 个不合对象且每个对象有m 个元素问题(解释：对于3个商人,3个侍从问题分离对应于n=2,m=3)的过河问题.从而给出课后习题5（n=4,m=1）的全部安然过河筹划.四.试验步调：第一步：问题剖析.这是一个多步决议计划进程,涉及到每一次船上的人员以及要斟酌此岸和此岸上残剩的商人数和侍从数,在安然的前提下（两岸的侍从数不比商人多）,经有限步使全部人员过河.第二步：剖析模子的组成.记第k 次渡河前此岸的商人数为k x ,侍从数为k y , 2,1=k ,n y x k k 2,1,=,（具有可扩大性）,将）（k k y x ,界说为状况,状况聚集成为许可状况聚集（S ）.S={2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（}记第k 次渡船的商人数为k u ,侍从数为k v ,决议计划为),(k k v u ,安然渡河前提下,决议计划的聚集为许可决议计划聚集.许可决议计划聚集记作D,所以D={2,1,0,,21|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为k 为奇数时船从此岸驶向此岸,k 为偶数时船由此岸驶向此岸,所以状况k s 随决议计划k d 变更的纪律是k k k k d s s )1(1-+=-,此式为状况转移律.制订安然渡河筹划归结为如下的多步决议计划模子：求决议计划)2,1(n k D d k =∈,使状况S s k ∈按照转移律,由初始状况)3,3(1=s 经有限n 步到达)0,0(1=+n s第三步：模子求解.#include "stdio.h"#include "string.h"#include <memory>#include <stdlib.h>#include <iostream>using namespace std;#include "conio.h"FILE *fp;/*设立文件指针,以便将它用于其他函数中*/struct a{long m,s;struct a *next;};/*数组类型a ：记载各类情形下船上的商人和家丁数,m ：代表商人数 s ：代表家丁数*/ struct a *jj,head;/*head 为头指针的链表单元（船上的人数的各类情形的链表）*/ 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;}/*释放该单元格,并将其上的单元格的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;/*商人数不克不及为负*/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)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){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中的内容写入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第%d种办法:\n",js);int count=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所指的内容打印出来*/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++){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(i<total-1){continue;}else{freeit(p3);break;}}int count1=0;if(j==1){if(i<total-1){print(p3);count1++;continue;}else{print(p3);freeit(p3);break;}//cout<<cout1<<endl;printf("%d",count1);printf("\n");}if(j==0)trans(p3);}return;}/*转移函数,即将人转移过河*//*n=0*/void main(){ struct aim *p,*p1;int j,a,e,f;struct a *flag;/*flag是用与记载头指针*/FILE*fpt;if((fpt=fopen("c:result.dat","w+"))==0){printf("can't creat it\n");exit(0);}fp=fpt;system("cls");printf("问题描写：三个商人各带一个侍从乘船过河,一只划子只能容纳X人,由他们本身荡舟.三个商人窃听到侍从们谋害,在河的随意率性一岸上,只要侍从的人数比上人多,就杀失落商人.但是若何乘船渡河的决议计划权在商人手里,商人们若何安插渡河筹划确保自身安然？\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("please input the total of people on the board\n");fprintf(fp,"\n请输入船上的人数\n");scanf("%d",&n);fprintf(fp,"\n%d\n",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->next=NULL;flag=jj;}/*********************************/printf("please input the total of merchant and salvent as follow: mechant,salvent;\n"); fprintf(fp,"\nplease input the total of merchant and salvent as follow: mechant,salvent;\n"); scanf("%ld,%ld",&p->m1,&p->s1);fprintf(fp,"\n%ld,%ld\n",p->m1,p->s1);/**********************************/k1=p->m1;k2=p->s1;trans(p);fclose(fpt);getch();}第一步：三个商人,三个侍从的模子求解答案为：运行后的成果为：第1 种筹划：(3,3) 到(0,0).(3,1) 到(0,2).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(0,2) 到 (3,1).(0,0) 到 (3,3)第2 种筹划：(3,3) 到(0,0).(3,1) 到(0,2).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(1,1) 到 (2,2).(0,0) 到 (3,3)第3 种筹划：(3,3) 到(0,0).(2,2) 到(1,1).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2)(.0,2) 到 (3,1).(0,0) 到 (3,3)第4 种筹划：(3,3) 到(0,0).(2,2) 到(1,1).(3,2) 到(0,1).(3,0) 到(0,3).(3,1) 到(0,2).(1,1) 到(2,2).(2,2) 到 (1,1).(0,2) 到 (3,1).(0,3) 到 (3,0).(0,1) 到 (3,2).(1,1) 到 (2,2)(0,0) 到 (3,3)第二步：四个商人三个侍从,其成果为：第1种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第2种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第3种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第4种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第5种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第6种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第7种办法:4,3::0,0 3,2::1,1 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第8种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第9种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第10种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第11种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第12种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第13种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第14种办法:4,3::0,0 3,2::1,1 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第15种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第16种办法:2,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第17种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第18种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第19种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第20种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第21种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第22种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,10,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第23种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,20,0::4,3 一共有16步完成第24种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第25种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第26种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第27种办法:4,3::0,0 3,2::1,1 3,3::1,0 2,2::2,1 4,2::0,14,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,10,0::4,3 一共有16步完成第28种办法:4,0::0,3 4,1::0,2 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第29种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第30种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 2,1::2,2 1,0::3,3 1,1::3,20,0::4,3 一共有16步完成第31种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 0,2::4,10,3::4,0 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第32种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 1,1::3,2 0,0::4,3 一共有14步完成第33种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第34种办法:2,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,1::4,2 0,2::4,10,0::4,3 一共有16步完成第35种办法:4,3::0,0 4,1::0,2 4,2::0,1 3,2::1,1 3,3::1,02,2::2,1 3,2::1,1 2,1::2,2 2,2::2,1 1,1::3,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第36种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第37种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第38种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第39种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第40种办法:2,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第41种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第42种办法:4,3::0,0 4,1::0,2 4,2::0,1 2,2::2,1 3,2::1,12,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成第43种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,21,1::3,2 0,0::4,3 一共有12步完成第44种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,22,1::2,2 1,0::3,3 1,1::3,2 0,0::4,3 一共有14步完成第45种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 0,2::4,1 0,3::4,0 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第46种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,21,1::3,2 0,0::4,3 一共有12步完成第47种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 0,1::4,20,2::4,1 0,0::4,3 一共有12步完成第48种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,1::4,2 0,2::4,1 0,0::4,3 一共有14步完成第49种办法:4,3::0,0 4,1::0,2 4,2::0,1 4,0::0,3 4,1::0,22,1::2,2 2,2::2,1 1,1::3,2 2,1::2,2 1,0::3,31,1::3,2 0,0::4,3 一共有12步完成。

摘要：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次渡河前此岸的商人数为x k，随从数为y k，k=1，2，…，x k，y k =0，1，2，3，将二维向量S k =（x k，y k）定义为状态。

数学建模作业（四）——商人过河问题一．问题描述有四名商人各带一名仆人过河，但船最多能载二人，商人已获得仆人的阴谋：在河的任一岸，只要仆人数超过商人数，仆人会将商人杀死并窃取财物且安排如何乘船的权力掌握在商人手中。

试为商人制定一个安全过河的方案。

二．解决方案用递归的源程序如下：开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合条件）#include <stdlib.h>struct node /*建立一个类似栈的数据结构并且可以浏览每一个数据点*/ {int x;int y;int state;struct node *next;};typedef struct node state;typedef state *link;link PPointer1=NULL;link PPointer2=NULL;int a1,b1;int a2,b2;/*栈中每个数据都分为0，1状态*/void Push(int a,int b,int n){link newnode;newnode=(link)malloc(sizeof(state));newnode-> x=a;newnode-> y=b;newnode-> state=n;newnode-> next=NULL;if(PPointer1==NULL){PPointer1=newnode;PPointer2=newnode;}else{PPointer2-> next=newnode;PPointer2=newnode;}}void Pop()/*弹栈*/{link pointer;if(PPointer1==PPointer2){free(PPointer1);PPointer1=NULL;PPointer2=NULL;}pointer=PPointer1;while(pointer-> next!=PPointer2)pointer=pointer-> next;free(PPointer2);PPointer2=pointer;PPointer2-> next=NULL;}int history(int a,int b,int n) /*比较输入的数据和栈中是否有重复的*/ {link pointer;if(PPointer1==NULL)return 1;else{pointer=PPointer1;while(pointer!=NULL){if(pointer-> x==a&&pointer-> y==b&&pointer-> state==n)return 0;pointer=pointer-> next;}return 1;}}int judge(int a,int b,int c,int d,int n)/*判断这个状态是否可行，其中使用了history函数*/{if(history(a,b,n)==0) return 0;if(a> =0&&b> =0&&a <=3&&b <=3&&c> =0&&d> =0&&c <=3&&d <=3&&a+c==3&&b+d==3){switch(n){case 1:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a==b){Push(a,b,n);return 1;}else return 0;}case 0:{if(a==3){Push(a,b,n);return 1;}else if(a==0){Push(a,b,n);return 1;}else if(a> =b){Push(a,b,n);return 1;}else return 0;}}}else return 0;}int Duhe(int a,int b,int n)/*递归法解决商人渡河问题，如果这一个状态符合*/ {/*则判断下一个状态，直至问题解决*/ if(a==0&&b==0) return 1;if(n==0)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a-1,b-1,4-a,4-b,1)){if(Duhe(a-1,b-1,1)==1)return 1;}if(judge(a,b-2,3-a,5-b,1)){if(Duhe(a,b-2,1)==1)return 1;}if(judge(a-2,b,5-a,3-b,1)){if(Duhe(a-2,b,1)==1)return 1;if(judge(a-1,b,4-a,3-b,1)){if(Duhe(a-1,b,1)==1)return 1;}if(judge(a,b-1,3-a,4-b,1)){if(Duhe(a,b-1,1)==1)return 1;}else{Pop(0);return 0;}}if(n==1)/*判断0状态时，商匪状态是否符合要求*/{if(judge(a+1,b+1,2-a,2-b,0)){if(Duhe(a+1,b+1,0)==1)return 1;}if(judge(a,b+2,3-a,1-b,0)){if(Duhe(a,b+2,0)==1)return 1;}if(judge(a+2,b,1-a,3-b,0)){if(Duhe(a+2,b,0)==1)return 1;}if(judge(a+1,b,2-a,3-b,0)){if(Duhe(a+1,b,0)==1)return 1;}if(judge(a,b+1,3-a,2-b,0))if(Duhe(a,b+1,0)==1)return 1;}else{Pop(1);return 0;}}return 0;}main(){link pointer;Push(3,3,0);Duhe(3,3,0);pointer=PPointer1;while(pointer!=NULL){printf( "%d,%d---%d\n ",pointer-> x,pointer-> y,pointer-> state);pointer=pointer-> next;}getch();}。

要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。

并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。

还应能实现n个商人，n个随从的过河问题以及n个不同对象且每个对象有m个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。

从而给出课后习题5（n=4,m=1）的全部安全过河方案。

#include"stdio.h"#include"iostream.h"bool PsSet[4][4], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[5][2]={{0,1},{0,2},{2,0},{1,0},{1,1}};//PdSet表示允许决策集int Record[12][2],pos=1;//Record记录已走过的状态pos当前位置bool Check[12];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(i==0||i==3||i==j);else PsSet[i][j]=true;}//检验该状态是否被用过int IsRepeat(int px,int py,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py){ int i;if(px==0&&py==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d) 到(%d,%d)",Record[i][0],Record[i][1],3-Record[i][0],3-Record[i][1]);printf("\n");}}else if(turn==false){ for(i=0;i<5;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];if(px<0||py<0||px>3||py>3||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px+PdSet[i][0];py=py+PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];}}else {for(i=0;i<5;i++){px=px+PdSet[i][0];py=py+PdSet[i][1];if(px<0||py<0||px>3||py>3||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px-PdSet[i][0];py=py-PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px-PdSet[i][0];py=py-PdSet[i][1];}}}//主函数void main(){int px=3,py=3;InitPsSet();Check[0]=true;Record[0][0]=3;Record[0][1]=3;CrossRiver(px,py);}#include"stdio.h"#include"iostream.h"bool PsSet[2][2][2][2], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[4][4]={{1,1,0,0},{1,0,0,0},{1,0,1,0},{1,0,0,1}};//PdSet表示允许决策集int Record[8][4],pos=1;//Record记录已走过的状态pos当前位置bool Check[8];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){PsSet[0][1][1][0]=true;PsSet[0][0][1][1]=true;PsSet[0][1][1][1]=true; PsSet[1][0][0][0]=true;PsSet[1][0][0][1]=true;PsSet[1][1][0][0]=true; }//检验该状态是否被用过int IsRepeat(int px,int py,int pu,int pv,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&pu==Record[i][2]&&pv==Record[i ][3]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py,int pu,int pv){ int i;if(px==0&&py==0&&pu==0&&pv==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d,%d,%d) 到(%d,%d,%d,%d)",Record[i][0],Record[i][1],Record[i][2],Record[i][3],1-Record[i][0],1-Record[i][1],1-Record[i][2],1-Record[i][3]);printf("\n");}}else if(turn==false){ for(i=0;i<4;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];pu=pu-PdSet[i][2];pv=pv-PdSet[i][3];if(px<0||py<0||pu<0||pv<0||px>1||py>1||pu>1||pv>1||PsSet[px][py][pu][ pv]||IsRepeat(px,py,pu,pv,turn)){ px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];continue;}Record[pos][0]=px;Record[pos][1]=py;Record[pos][2]=pu;Record[pos][3]=pv;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py,pu,pv);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];}}else {for(i=0;i<4;i++){ px=px+PdSet[i][0];py=py+PdSet[i][1];pu=pu+PdSet[i][2];pv=pv+PdSet[i][3];if(px<0||py<0||pu<0||pv<0||px>1||py>1||pu>1||pv>1||PsSet[px][py][pu][ pv]||IsRepeat(px,py,pu,pv,turn)){ px=px-PdSet[i][0];py=py-PdSet[i][1];pu=pu-PdSet[i][2];pv=pv-PdSet[i][3];continue;}Record[pos][0]=px; Record[pos][1]=py;Record[pos][2]=pu; Record[pos][3]=pv;Check[pos]=turn; pos++;turn=!turn;CrossRiver(px,py,pu,pv);pos--; turn=!turn; px=px-PdSet[i][0];py=py-PdSet[i][1]; pu=pu-PdSet[i][2]; pv=pv-PdSet[i][3];}}}//主函数void main(){int px=1,py=1,pu=1,pv=1;InitPsSet();Check[0]=true;Record[0][0]=1;Record[0][1]=1;Record[0][2]=1;Record[0][3]=1;CrossRiver(px,py,pu,pv);}#include"stdio.h"#include"iostream.h"bool PsSet[5][5], turn;//PsSet是允许状态集turn表示由此岸到彼岸或由彼岸到此岸int PdSet[5][2]={{0,1},{0,2},{2,0},{1,0},{1,1}};//PdSet表示允许决策集int Record[20][2],pos=1;//Record记录已走过的状态pos当前位置bool Check[20];//Check记录走过状态的turn值int num=0;//初始化PsSetvoid InitPsSet(){for(int i=0;i<5;i++)for(int j=0;j<5;j++)if(i==0||i==4||i==j);else PsSet[i][j]=true;}//检验该状态是否被用过int IsRepeat(int px,int py,bool turn){ for(int i=0;i<pos;i++)if(px==Record[i][0]&&py==Record[i][1]&&turn==Check[i])return true;return false;}//过河子函数void CrossRiver(int px,int py){ int i;if(px==0&&py==0){ num++;printf("第%d 种方案",num);printf("\n");for(i=0;i<pos;i++){ printf("(%d,%d) 到(%d,%d)",Record[i][0],Record[i][1],4-Record[i][0],4-Record[i][1]); printf("\n");}}else if(turn==false){ for(i=0;i<5;i++){px=px-PdSet[i][0];py=py-PdSet[i][1];if(px<0||py<0||px>4||py>4||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px+PdSet[i][0];py=py+PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px+PdSet[i][0];py=py+PdSet[i][1];}}else {for(i=0;i<5;i++){px=px+PdSet[i][0];py=py+PdSet[i][1];if(px<0||py<0||px>4||py>4||PsSet[px][py]||IsRepeat(px,py,turn)) { px=px-PdSet[i][0];py=py-PdSet[i][1];continue;}Record[pos][0]=px;Record[pos][1]=py;Check[pos]=turn;pos++;turn=!turn;CrossRiver(px,py);pos--;turn=!turn;px=px-PdSet[i][0];py=py-PdSet[i][1];}}}//主函数void main(){int px=4,py=4;InitPsSet();Check[0]=true;Record[0][0]=4; Record[0][1]=4;CrossRiver(px,py);}。

案例名称:商人怎样安全过河学科分类：数学数学分支：初等数学模型预备知识：线性代数，解析几何，MATLAB适用对象：本科、专科学生1.问题的背景与问题提出这个案例是一个智力游戏。

3名商人各带1个随从乘船渡河，一只小船只能容纳2人，由他们自己划行。

随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。

但是如何乘船渡河的大权掌握在商人手中。

商人们怎样才能安全渡河呢？2.问题的分析与模型建立：将一个智力游戏转化成数学问题。

商人渡河问题是一个多步决策问题。

首先由学生从玩游戏开始，在纸面上完成渡河过程；然后再由学生实际演绎，在黑板上记录渡河过程。

利用学生的演绎记录结果进行问题的分析与模型的建立。

分析整个操作过程，让模型的建立随着思考的深入自然而然的呈现。

Step1 变量的设置：用有序数对（x,y）表示岸上商人数和随从数，（u,v）表示船上的商人数和随从数，代数思想的自然渗入；Step2 过程的数学化表示：（x2,y2）=（x1,y1）-（u1,v1）（x3,y3）=（x2,y2）+（u2,v2）......（x i+1,y i+1）=（x i,y i）+(-1)i（u i,v i）规律即模型自然呈现。

Step3 模型的优化：引入集合的表示法状态允许集S=｛（x,y）:x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2｝允许决策集D={((u,v)):1≤u+v≤2，u,v=0,1,2}状态转移律 s k+1=s k+(-1)k d k求决策d k（k=1，2,...,n）使状态s k按照转移律，由初始状态s1=(3,3)经过有限步n到达状态s n+1=(0,0)。

3.模型的求解与结果检验求解方法1：符号操作法求解方法2：图解法（引入坐标系）求解方法3：穷举法编程上机4.模型的评注与应用用这种规格化的方法建立的多步决策模型可以用计算机来求解，从而具有推广的意义。

5.参考文献[1]姜启源.数学模型.4版.北京：高等教育出版社，2011×图1 符号法图2 安全渡河的图解法（1）图3 安全渡河的图解法（2）x3 2 1 0sn +139d11dxs n +1dmatlab上机程序：(1)function s=businessmann=input('输入商人数目：');nn=input('输入仆人数目：');nnn=input('输入船的最大容量：');if nn>nn=input('输入商人数目：');nn=input('输入仆人数目：');nnn=input('输入船的最大容量：');endk=1;for i=0:nnn %产生出所有的可能过河的决策for j=0:nnnif (i+j<=nnn) &(i+j>0)d(k,1:3)=[i,j,1]; %1表示从此岸到彼岸d(k+1,1:3)=[-i,-j,-1]; %-1表示从彼岸到此岸k=k+2;endendendk=1;for i=n:-1:0 %产生安全队列for j=nn:-1:0if ((i>=j) & ((n-i)>=(nn-j))) | ((i==0)|(i==n))A(k,1:3)=[i,j,1]; %1表示此岸安全k=k+1;endendend%队列数据结构，第一列表示商人数，第二列表示仆人数，第三列用于记录该结点的上一个结点，第四列表示船的运动方向（1表示此岸往彼岸运动，-1表示从彼岸往此岸运动）sq(1,1)=n;sq(1,2)=nn;sq(1,3)=0;sq(1,4)=1; %初始状态front=1;rear=1; %队列的头尾指针while(front<=rear)x=sq(front,1);y=sq(front,2);flag=0;if (sq(front,4)==1)for v=2:2:size(d,1)i=x+d(v,1);j=y+d(v,2);if (is_save(A,i,j)==1)rear=rear+1;sq(rear,1)=i;sq(rear,2)=j;sq(rear,3)=front;sq(rear,4)=-1;endif (i==0 && j==0)flag=1;endendendif (flag==1)break;endflag=0;if (sq(front,4)==-1)for v=1:2:size(d,1)i=x+d(v,1);j=y+d(v,2);if (is_save(A,i,j)==1) & (sq(sq(front,3),1)~=i | sq(sq(front,3),2)~=j)rear=rear+1;sq(rear,1)=i;sq(rear,2)=j;sq(rear,3)=front;sq(rear,4)=1;endif (i==0 && j==0)flag=1;endendendif (flag==1)break;endfront=front+1;(2)function a=is_save(A,x,y)for i=1:size(A,1)if (x==A(i,1) && y==A(i,2))break;endendif i<size(A,1)a=1;elsea=0;。

数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是C,C++或Mathlab ）实现商人安全过河问题。

二、实验环境：Turbo c 2.0、Microsoft Visual C++ 6.0、Matlab 6.0以上 三、实验要求：要求该程序不仅能找出一组安全过河的可行方案，还可以得到所有的安全过河可行方案。

并且该程序具有一定的可扩展性，即不仅可以实现3个商人，3个随从的过河问题。

还应能实现 n 个商人，n 个随从的过河问题以及n 个不同对象且每个对象有m 个元素问题(说明：对于3个商人，3个随从问题分别对应于n=2,m=3)的过河问题。

从而给出课后习题5（n=4,m=1）的全部安全过河方案。

四、实验步骤：第一步：问题分析。

这是一个多步决策过程，涉及到每一次船上的人员以及要考虑此岸和彼岸上剩余的商人数和随从数，在安全的条件下（两岸的随从数不比商人多），经有限步使全体人员过河。

第二步：分析模型的构成。

记第k 次渡河前此岸的商人数为k x ，随从数为k y ，2,1=k ，n y x k k 2,1,=，（具有可扩展性），将）（k k y x ,定义为状态，状态集合成为允许状态集合（S ）。

S={2,1;3,2,1,0,3;3,2,1,0,0|,======y x y x y x y x ）（}记第k 次渡船的商人数为k u ，随从数为k v ，决策为),(k k v u ，安全渡河条件下，决策的集合为允许决策集合。

允许决策集合记作D ，所以D={2,1,0,,21|,=<+<v u v u v u ）（|1<u+v<2,u,v=0,1,2},因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船由彼岸驶向此岸，所以状态k s 随决策k d 变化的规律是k k k k d s s )1(1-+=-，此式为状态转移律。

制定安全渡河方案归结为如下的多步决策模型：求决策)2,1(n k D d k =∈，使状态S s k ∈按照转移律，由初始状态)3,3(1=s 经有限n 步到达)0,0(1=+n s第三步：模型求解。