商人过河matlab程序以及解析

做业1、2：之阳早格格创做商人过河一、问题沉述问题一：4个商人戴着4个随从过河，过河的工具惟有一艘小船，只可共时载二部分过河，包罗划船的人.随从们稀约, 正在河的任一岸, 一朝随从的人数比商人多, 便杀人越货.乘船渡河的规划由商人决断.商人们何如才搞仄安过河?问题二：假若小船不妨容3人，请问最多不妨有几名商人各戴一名随从仄安过河.二、问题分解问题不妨瞅搞一个多步计划历程.每一步由此岸到此岸或者此岸到此岸船上的人员正在仄安的前提下(二岸的随从数没有比商人多),经有限步使部分人员过河.用状态变量表示某一岸的人员情景，计划变量表示船上的人员情况，不妨找出状态随计划变更的顺序.问题便变换为正在状态的允许变更范畴内（即仄安渡河条件），决定每一步的计划，达到仄安渡河的目标.三．问题假设1. 过河途中没有会出现没有成抗力的自然果素.2. 当随从人数大于商人数时，随从们没有会改变杀人的计划.3．船的品量很佳，正在多次谦载的情况下也能仄常运做.4. 随从会听从商人的调动.四、模型形成x(k)~第k 次渡河前此岸的商人数 x(k),y(k)=0,1,2,3,4; y(k)~第k 次渡河前此岸的随从数 k=1,2,…..s(k)=[ x(k), y(k)]~历程的状态 S~允许状态集中 S={(x,y)|x=0,y=0,1,2,3,4; x=4,y=0,1,2,3,4;x=y=1,2,3} u(k)~第k 次渡船上的商人数 u(k), v(k)=0,1,2;v(k)~ 第k 次渡船上的随从数 k=1,2…..d(k)=( u(k), v(k))~历程的计划 D~允许计划集中 D={u,v|u+v=1,2,u,v=0,1,2}状态果计划而改变s(k+1)=s(k)+(-1)^k*d(k)~状态变化律供d(k)ÎD(k=1,2,….n),使s(k)ÎS 并按变化律s(k+1)=s(k)+(-1)^k*d(k)由（4,4）到达（0,0）数教模型： k+1kS =S +k k D （-1）（1）'4k k x x += （2）'4k k y y +=（3）k.k x y ≥ （4）''k k x y ≥（5）模型分解：由（2）（3）（5）可得化简得概括（4）可得k k x y =战 {}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6） 还要思量{}'(',')|'0,'0,1,2,3,4k k k k k S x y x y === （7）把（2）（3）戴进（7）可得化简得{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）概括（6）（7）（8）式可得谦脚条件的情况谦脚下式 {}(,)|0,4,0,1,2,3,4;k k k k k k k S x y x y x y ====（9） 所以咱们知讲谦脚条件的面如上图所示：面移动由{}(,)|4,0,1,2,3,4k k k k k S x y x y === （8）到达{}(,)|0,0,1,2,3,4k k k k k S x y x y ===（6）时，不妨认为完毕渡河.果为移动的格数小于等于2，惟有核心面（2，2）到（6）面战（8）面的距离为2，所以核心面（2,2）成为渡河的闭键面.当咱们移动到（2,2）面时，便无法举止下去.故4个商人，4个随从，船容量为2人时，无法仄安渡河. 对付于问题二，咱们不妨修坐模型为：k+1k S =S +k k D （-1）（10）'k k x x M += （11）'k k y y M += （12）k.k x y ≥（13）''k k x y ≥ （14）u(k), v(k)=0,1,2,3; （15）通过类似于问题一的步调不妨知讲：坐标上的闭键面是（3,3），最多不妨五名商人戴五名随从往日.需要决定五名商人戴五名随从的规划可止再决定六名商人戴六名随从的规划没有成止1、五名商人戴五名随从的情况：（1）最先没有成能有三名商人先过河，二名商人一名随从过河，一名商人二名随从过河（2）三个随从先过河（5,2），回去一个随从（5,3），往日二个随从（5,1）回去一个随从（5,2），再往日三个商人（2,2），回去一个商人一个随从（3,3），再往日三个商人（0,3），回去一个随从（0,4），往日三个随从（0,1），回去一个随从（0,2）再往日二个随从（0,0）综上可知：五名商人戴五名随从，小船不妨载三部分不妨过河2、六名商人戴六名随从的情况：（1）最先没有成能有三名商人先过河，二名商人一名随从过河，一名商人二名随从过河（2）三个随从先过河（6,3），回去一个随从（6,4），往日二个随从（6,2）回去一个随从（6,3），往日三个商人（3,3），此时二岸皆是（3,3），由坐标法分解知，那是最交近末面的临界面，然而是如果回去的时间一定是回去一个商人战一个随从，如果那一步可止，后里便举止没有去综上所述，六个商人戴六个随从，小船载三部分的情况下没有克没有及渡河分离1、2知，当小船最多载三部分的时间，最多五名商人各戴一个随从不妨过河.五、模型的考验取评介由少量人的过河问题推广到了更普遍人的过河问题，使得问题变得明白有顺序.六、参照文件[1]章胤，2014年燕山大教世界大教死数教修模竞赛训练ppt，2014年4月17日。

数学建模实验一陈说之吉白夕凡创作实验题目：研究商人过河问题一、实验目的：编写一个法式（可以是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->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第%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++){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(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,13,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,34,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种方法: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,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,13,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,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 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,12,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,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,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,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,12,1::2,2 0,1::4,2 0,2::4,1 0,0::4,3一共有14步完成第34种方法: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,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,01,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种方法: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,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,00,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,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步完成第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步完成。

商人们怎样安全过河随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析：决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河. 建立模型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)=[]; %%%%%%%%%%%%%%%%%% 程序完 %%%%%%%%%%%%%%%%%%欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习资料等等打造全网一站式需求。

《数学建模实验》课程考试试题----商人安全过河数学建模与求解一．问题提出：4名商人带4名随从乘一条小船过河，小船每次自能承载至多两人。

随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货.乘船渡河的方案由商人决定，商人们如何才能安全渡河呢二．模型假设：商人和随从都会划船，天气很好，无大风大浪，且船的质量很好，可以保证很多次安全的运载商人和随从。

三．问题分析：商随过河问题可以视为一个多步决策过程，通过多次优化，最后获取一个全局最优的决策方案。

对于每一步，即船由此岸驶向彼岸或由彼岸驶向此岸，都要对船上的人员作出决策，在保证两岸的商人数不少于随从数的前提下，在有限步内使全部人员过河。

用状态变量表示某一岸的人员状况，决策变量表示船上的人员状况，可以找出状态随决策变化的规律，问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到安全渡河的目标。

四．模型构成：k x ~第k 次渡河前此岸的商人数，k y ~第k 次渡河前此岸的随从数 k x , k y =0,1,2,3,4; k =1,2,… …k S =(k x , k y )~过程的状态,S ~ 允许状态集合，S={(x , y )| x =0, y =0,1,2,3,4; x =4 ,y =0,1,2,3,4; x =y =1,2,3} k u ~第k 次渡船上的商人数k v ~第k 次渡船上的随从数k d =(k u , k v )~决策，D={(u , v )| 21≤+≤v u ,k u , k v =0,1,2} ~允许决策集合 k =1,2,… …因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态k S 随决策k d 的变化规律是1+k S =k S +k )1(-k d ~状态转移律求k d ∈D(k =1,2, …n), 使k S ∈S, 并按转移律由1S =(4,4)到达状态1+n S =(0,0)。

《数学模型实验》实验报告姓名：王佳蕾学院：数学与信息科学学院地点：主楼402学号：20151001055 专业：数学类时间：2017年4 月16日一、实验名称：商人和仆人安全渡河问题的matlab实现二、实验目的：1.熟悉matlab基础知识，初步了解matlab程序设计；2.研究多步决策过程的程序设计方法；3.（允许）状态集合、（允许）决策集合以及状态转移公式的matlab表示；三、实验任务：只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1-2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。

怎么在保证商人安全的情况下，六个人都到河对岸去，建模并matlab实现。

要求：代码运行流畅，结果正确，为关键语句加详细注释。

四、实验步骤：1.模型构成2.求决策3.设计程序4.得出结论（最佳解决方案）五、实验内容：（一）构造模型并求决策设第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,...，xk，yk=0,1,2,3.将二维向量sk=（xk，yk）定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S，S 对此岸和彼岸都是安全的。

S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}设第k次渡船上的商人数为uk，随从数vk，将二维变量dk=（uk，vk）定义为决策，允许决策集合记为D,由小船的容量可知，D={(u,v)|1<=u+v<=2,u,v=0,1,2}k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，状态sk随决策变量dk的变化规律为sk+1=sk+(-1)^k*dk（状态转移律）这样制定安全渡河方案归结为如下的多步决策模型：求决策dk∈D(k=1,2,...,n)，使状态sk∈S，按照转移律，由初始状态s1=（3,3）经有限步n到达状态sn+1=（0,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第三步：模型求解。

商人们怎样安全过河建立模型xk~第k次渡河前此岸的商人数yk~第k次渡河前此岸的随从数sk=(xk , yk)~过程的状态S={(x , y) x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2} uk~第k次渡船上的商人数vk~第k次渡船上的随从数dk=(uk , vk)~ 决策多步决策问题求dk到达sn+仁(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给出安全渡河方案xk, yk=0,1,2,3;k=1,2,|....S~允许状态集合uk, vk=0,1,2;k=1,2,..…u+v=1,2} ~允许决策集合~状态转移律n),使sk S,并按转移律由s仁(3,3)要求~在安全的前提下(两岸的随从数不比商人多)，经有限步使全体人员过河D={(u , v)D(k=1,2,评注和思考规格化方法 ,易于推广考虑 4 名商人各带一随从的情况 程序%%%%%%%%%%%%%%%% 开始 %%%%%%%%%%%%%%%%%%%%%% function jueche=guohe clear all clc%%%%%%%%%% 程序开始需要知道商人和仆人数； %%%%%%%%%%%%% shangren=input(' 输入商人数目 : '); puren=input(' 输入仆人数目 : ');rongliang=input(' 输入船的最大容量 : ');if puren>shangren shangren=input(' 输入商人数目 :'); puren=input(' 输入仆人数目 :'); rongliang=input(' 输入船的最大容量 :');end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决 策 生成jc=1; %决策向量放在矩阵 fori=0:rongliangfor j=0:rongliangif (i+j<=rongliang)&(i+j>0)d(jc,1:3)=[i,j ,1];d(jc+1,1:3)=[-i,-j,-1];jc=jc+2;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;endend 中， jc 为插入新元素的行标初始为 1； % 满足条 D={(u,v)|1<=u+v<=rongliang,u,v=0,1,2} %生成一个决策向量立刻扩充为三维； % 同时生成他的负向量； 由于生成两个决策向量，则 jc。

数学建模实验一报告实验题目：研究商人过河问题一、实验目的：编写一个程序（可以是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第三步：模型求解。

商人过河的MATLAB程序n=4;m=4;h=2; %初始状态及数据m0=0;n0=0;ticLS=0; % 允许的状态集合S与个数LSLD=0; %允许的决策集合D与个数LDfor i=0:nfor j=0:mif i>=j&n-i>=m-j|i==n|i==0LS=LS+1;S(LS,:)=[i j];endif i+j>0&i+j<=h&(i>=j|i==0)LD=LD+1;D(LD,:)=[i j];endendend%用搜寻法找出符合条件的渡河方案N=18;Q1=inf*ones(2*N,2*N);Q2=inf*ones(2*N,2*N);t=1;le=1;q=[m n];f0=0; %判断循环终止标记while f0~=1&t<="" p="">k=1;sa=[];sb=[];for i0=1:le %第n次允许的策略集逐次搜索s0=q(i0,:);breakendfor i=1:LD %由s0搜索D后得到允许的状态s1=s0+(-1)^t*D(i,:); if s1==[m0,n0]sa=[m0,n0];sb=D(i,:);f0=1;breakendfor j=2:LS-1 %搜索对比S后允许状态if s1==S(j,:)if k==1sa(k,:)=s1;sb(k,:)=D(i,:);k=k+1;breakendif k>1 %对重复状态删除处理f1=0;for ii=1:k-1if s1==sa(ii,:)f1=1;breakendendend %……if f1==0sa(k,:)=s1;sb(k,:)=D(i,:);breakendendend %…………………end %………………………………end %……………………………………………q=sa; le=size(q,1);Q1(1:le,t*2-1:t*2)=q;Q2(1:le,t*2-1:t*2)=sb;t=t+1;endif length(q)==6tr=t-1;saa1=sa;SA=zeros(tr,2);SB=zeros(tr,2);for k=tr:-1:2k1=k-1;f0=0;sbb=Q2(:,k*2-1:k*2);saa=Q1(:,k1*2-1:k1*2);for i=1:2*Nsaa2=saa1-(-1)^k*sbb(i,:);for j=1:2*Nif saa2==saa(j,:)saa1=saa2;sbb1=sbb(i,:);f0=1;breakendendif f0==1endendSA(k1,:)=saa1;SB(k,:)=sbb1;endSA(tr,:)=[m0 n0];SB(1,:)=[m,n]-SA(1,:); %………………………………………………………………………………………………￥￥disp '初始状态：'X0=[m,n]disp '状态为:'SAdisp '决策为:'SBtocendif length(q)~=6disp '没有可行的方法过河'enddisp '可以走的状态为：'；q。