3人的可以过河，4人的没有办法。
用递归的源程序如下：
运行结果是没有解，超过3人的没有解。
开始时商人，强盗所在的河的这边设为0状态，另一边设为1状态（也就是船开
始时的一边设为0，当船驶到对岸是设为1状态，在这两个状态时，都必须符合
条件）
#include
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();
}
a = [
0, 0;
0, 1;
0, 2;
0, 3;
3, 0;
3, 1;
3, 2;
3, 3;
1, 1;
2, 2;
]; % 10 enabled states
s=[0, 0;
0, 1;
0, 2;
0, 3;
1, 0;
1, 1;
1, 2;
1, 3;
2, 0;
2, 1;
2, 2;
2, 3;
3, 0;
3, 1;
3, 2;
3, 3;
];
d = [
0, 2;
2, 0;
1, 1;
0, 1;
1, 0;
]; % 5 enabled decisions
i = 1;
j = 1;
k = 1;
s(1, = [3, 3];
disp('This shore - On Boat - That shore')
for i = 1:12
* R5 P0 S8 N$ a' E- O
& B4 i4 Z# s# z D7 O7 j; f
for j = 1:5
t = 0;
r = mod(i, 2);
m = r;
u = 0;
for k = 1:10
if s(i, + (-1)^i * d(j, == a(k,
t = 1;
end
end
end
if t==1
if u==0
s(i+1, = s(i, + (-1)^i * d(j, ;
c(i+1, = d(j, ;
return;
elseif u==1
continue;
end
else continue;
end
end;
if t==0
disp('No Result');
return;
end;
b(i+1, = [3, 3] - s(i+1, ;
play = sprintf('{%d, %d}-{%d, %d}-{%d, %d}', s(i, 1), s(i, 2), c(i+1, 1), c(i+1, 2), b(i+1, 1), b(i+1, 2));
disp(play)
if s(i+1, ==[0, 0]
return;
end;
function jueche=guohe
%%%%%%%%%%%%%%%%%%%%%%
程序开始需要知道商人和仆人数；
n=input(‘输入商人数目:’,’12’);
nn=input(‘输入仆人数目:’,’12’);
nnn=input(‘输入船的最大容量:’,’20’);
if nn>n
n=input(‘输入商人数目:’,’23’);
nn=input(‘输入仆人数目:’,’23’);
nnn=input(‘输入船的最大容量:’,’34’);
end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成
jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1；
for i=0:nnn
for j=0:nnn
if (i+j<=nnn)&(i+j>0) % 满足条
D={(u,v)|1<=u+v<=nnn,u,v=0,1,2}
d(jc,1:3)=[i,j，1]；%生成一个决策向量立刻扩充为三维；
d(jc+1,1:3)=[-i,-j,-1]; % 同时生成他的负向量；
jc=jc+2; % 由于生成两个决策向量，则jc要向下移动两个； end
end
j=0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成
kx=1; % 状态向量放在A矩阵中，生成方法同矩阵生成；
for i=n:-1:0
for j=nn:-1:0
if ((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))
% (i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))为可以存在的状态的约束条件
A(kx,1:3)=[i,j,1]; %生成状态数组集合D `
A(kx+1,1:3)=[i,j,0];
kx=kx+2;
end
end
j=nn;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 将状态向量生成抽象矩阵
k=(1/2)*size(A,1);
CX=zeros(2*k,2*k);
a=size(d,1);
for i=1:2*k
for j=1:a
c=A(i,:)+d(j,:) ;
x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))) ;
v(i,x)=1; %x为空不会改变v值
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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)==m
break;
end
for j=1:size(a,1)
pp=a(j,1);
if v(k,pp)~=0
if T(pp)>(P(k)+v(k,pp))
T(pp)=(P(k)+v(k,pp));
lmd(pp)=k;
end
end
end
mi=min(T(a));
if mi==inf
break;
else
d=find(T==mi);
d=d(1);
P(d)=mi;
T(d)=inf;
k=d;
S(d)=1;
end
end
if lmd(y)==inf
jueche='can not reach';
return;
end
jueche(1)=y;
g=2; h=y;
while(1)
if h==x
break;
end
jueche(g)=lmd(h);
g=g+1;
h=lmd(h);
end
jueche=A(jueche,:);
jueche(:,3)=[];
clear all % 080817
clc % n为商人数，m为仆人数，h为每次过河的最多人数n=3;m=3;h=2; %初始状态及数据
m0=0;n0=0;
tic
LS=0; % 允许的状态集合S与个数LS
LD=0; %允许的决策集合D与个数LD
for i=0:n
for j=0:m
if i>=j&n-i>=m-j|i==n|i==0
LS=LS+1;S(LS,:)=[i j];
end
if i+j>0&i+j<=h&(i>=j|i==0)
LD=LD+1;D(LD,:)=[i j];
end
end
end
%用搜寻法找出符合条件的渡河方案%……………………………………………………………………………………………$$
N=15;
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 k=1; sa=[]; sb=[]; for i0=1:le %第n次允许的策略集逐次搜索 s0=q(i0,:); if f0==1 break end for i=1:LD %由s0搜索D后得到允许的状态 s1=s0+(-1)^t*D(i,:); if s1==[m0,n0] sa=[m0,n0]; sb=D(i,:); f0=1; break end for j=2:LS-1 %搜索对比S后允许状态 if s1==S(j,:) if k==1 sa(k,:)=s1; sb(k,:)=D(i,:); k=k+1; break end if k>1 %对重复状态删除处理 f1=0; for ii=1:k-1 if s1==sa(ii,:) f1=1; break end end end %…… if f1==0 sa(k,:)=s1; sb(k,:)=D(i,:); k=k+1; break end end end %………………… 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; end %………………………………………………………$$ %在可行方案集合中逆向搜寻唯一方案%……………………………………………………………………………………………￥￥ tr=t-1;saa1=sa; SA=zeros(tr,2);SB=zeros(tr,2); for k=tr:-1:2 k1=k-1;f0=0; sbb=Q2(:,k*2-1:k*2); saa=Q1(:,k1*2-1:k1*2); for i=1:2*N saa2=saa1-(-1)^k*sbb(i,:); for j=1:2*N if saa2==saa(j,:) saa1=saa2; sbb1=sbb(i,:); f0=1; break end end if f0==1 break end end SA(k1,:)=saa1; SB(k,:)=sbb1; end SA(tr,:)=[m0 n0]; SB(1,:)=[m,n]-SA(1,:); %………………………………………………………………………………………………￥￥ disp '初始状态：' X0=[m,n] disp '状态为:' SA disp '决策为:' SB toc 商人过河 一、问题重述和分析 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。现有4名商人各带一个随从一起渡河一只船只能容纳两个人，但如何乘船渡河的大权掌握在商人的手里，商人怎样安排才能在有限步内安全渡河？ 二、模型假设 1、在商人人数多于随从时乘船渡河的大权掌握在商人的手里； 2、商人和随从都会划船； 三．符号说明 x表示商人人数； y表示随从人数； z表示划船到河的此岸与彼岸。 四、模型的建立与求解 本题为多步决策模型，每一次过河都是状态量的转移过程。 此岸四个商人用x=0、1、2、3、4表示，此岸四个随从用y=0、1、2、3、4表示，z=0时表示划船到河的此岸时，z=1时表示划船到河的彼岸时，用有序数对（x，y，z）表示每次转移的状态量。解决此问题就是状态量（4,4,0）转移至（0,0,1），以下就是状态量转移的全部情况（其中“！”表示不能再转移下去或与前面步骤重复）： （4,4，0）→（3,3,1） ↓↓ （4,2,1）→（4,3,0）→（4,1,1）→（4,2,0）→（4,0,1）→（4,1,0）→！ ↓ （2,2,1） ↓ ！ 由以上关系可知，一只船只能容纳两个人的情况下，四名商人各带一个随从无法过河。 此外，如果船的容量增加到3人，那么商人就能以几种方式安全过河，以下 是其中一种方案： （4,4,0）→（4,2,1）→（4,3,0）→（4,1,1,）→（4,2,0）→（2,2,1） ↓ （0,1,1）←（0,3,0）←（0,2,1）←（0,4,0）←（0,3,1）←（3,3,0）↓ （0,2,0）→（0,0,1） 五、模型推广 通过以上模型的建立，若商人和随从人数增加或小船容量加大，考虑n名商人各带一随从的情况。 商人过河问题数学建模 WEIHUA system office room 【WEIHUA 16H-WEIHUA WEIHUA8Q8- 作业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,vu+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+1k S =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） 商人过河问题 /*************************************************** *M个商人与每人各带的一个仆人过河问题 *船每次至多运N个人，至少要有一人划船 *在任一岸，当商人数<仆人数时,仆人就杀人越货 *过河由商人安排运送人员及数目 *找出安全渡河的全部方法并打印(原问题中M=3，N=2) *2010-10-10 20时许（纪念伟大的双十） * LYP ***************************************************/ /****************************************************************** *本题为多步决策 *若考虑只针对人数为 M = 3 对，每次过河人数最多 N = 2 *可以证明路径中必须经坐标中(3,1)过至(1,1)点(过诃时)， *后返回至(2,2)点，再过诃至(0,2)点(只剩2个仆人) *可以先考虑(3,3)到(3,1)点 *再经(0,2)至(0,0),完成过诃(由图形的对称性关系,可以直接将(3,1)至(3,1)路径翻转,更改对应标号即可) *当然也可以用动态规划求解 *本代码不限定M,N值,可通过修改宏M,N的值,求其他商人(仆人)数与最大过河人数的全部路径 *******************************************************************/ /********************************************************************* * *商人数x < 仆人数y时遭杀人越货，过河失败 *对应可行域为: *x = 0, y = 0…M; elements[]中编号0…M *0 < x < M, y = x; elements[]中编号M+1…2M-1 *x = M, y = 0…M； elements[]中编号2M…3M *图像上表示如下:(共 3*M+1 个点),过河即从3M点到0点 *过河为左下方1/4圆区域 *返回为右上方1/4圆区域 论文题目：过河问题及其扩展 姓名学号学院年级缺勤记录 朱本超2009221104120031 数计学院09级 陈凯2009221104120004 数计学院09级 张安龙2009221104120016 数计学院09级 课程论文自检报告 请回答以下问题，并在每题后打√确认。 1．除作者外，是否请过同事（同学）对论文进行挑剔性阅读？ 2．“问题提出”或前言部分中的文献回顾是否完备？ 3．是否对照过提供的“论文格式”逐项检查论文的各个部分？ 4．文后参考文献与文中的文献引用是否一一对应？ 5．文后参考文献的书写格式是否符合国家标准？（尤其注意著录符号、外国人的姓和名、有无漏项等）6．参考文献是否以近5年的文献为主？ 7．作者信息是否完整？包括word文档属性中的作者与单位、学号等。 课程论文质量评价标准 评阅点评分标准分值得分 摘要基本写出论文大意且语言简练、文字组织合理20 基本写出论文大意且语言简练15 基本写出论文大意10 套话、虚话较多或字数不够或文不对题0-5 正文论证严谨、思路清晰、逻辑性强、有较强说服力，引文准确25 论证较严谨、思路较清晰、符合逻辑、有一定说服力，引文准确20 思路较清晰、引文较恰当15 有一定的说服力但论文紊乱、自相矛盾、大段抄袭他人文章0-10 结构结构严谨、逻辑严密、层次清晰20 结构合理、符合逻辑、层次分明18 结构基本合理、层次比较清楚、文理通顺15 有不合理部分，逻辑性不强0-10 深度和广度见解独特，对问题分析透彻，且非常全面25 有自主的见解，对问题的分析比较深入全面20 能提出自己的见解，分析的深度、广度一般15 分析比较深入全面10 对问题的分析既无深度，又无广度0-5 规范化格式完全符合规范，字数完全符合要求10 格式比较规范，字数偏少8 格式基本符合规范，但有个别地方不合规，字数较少 5 格式规范性尚可，但不足之处较多，字数太少0-3 备注：以上评分标准仅供参考。总分 讨论资金积累、国民收入与人口增长的关系 班级：2009级数学与应用数学 黄全（组长）: P092314746 邱亚彪: P091712712 谢志成:P091712679 央金:P091715381 罗国庭:P091712739 讨论资金积累、国民收入与人口增长的关系 摘要 如何保证人口增长对国民收入影响的正效应和国民平均收入持续性增长，一直是全国人民所共同关注的问题。本文对资金积累、国民收入和人口增长三者之间的关系进行讨论，通过导数结合三者之间存在的基本规律，建立相应的微分方程，利用微分方程法给出方程，由matlab解得资金积累、国民收入与人口增长的关系。通过掌握该关系，确定资金积累的增长率大于人口增长率时国民收入才会增长，从而更好地调整人口出身率、控制人口的数量和人口质量，保证我国人口增长与国民收入增长之间的适当的比例关系，使得国民平均持续性增长，促进社会经济的迅速发展，提高人民的生活质量，为整个社会的长远战略需求做贡献。 关键字：资金积累状态转移律图解法微分方程决策 一、 问题重述 讨论资金积累、国民收入与人口增长的关系 （1）若国民平均收入x 与按人口平均资金积累y 成正比，说明仅当总资金积累 的相对增长率k 大于人口的相对增长率r 时，国民平均收入才是增长的. （2）作出k(x)和r(x)的示意图，说明二曲线交点是平衡点，讨论它的稳定性。 （3）分析人口激增会引起什么后果 二、符号说明 1x : t 时刻总资金累积量，2x ：t 时刻人口数量， 3x ：国民平均收入量 ，k ：总资金的相对增长率 r ：人口的相对增长率 三 、模型的假设 在一定时期后,增长的人口数量为:：22x rx '=； 总资金的增长量为：11x kx '= ； 四、问题的分析 在社会主义发展的初级阶段，国民收入是指一定时期（通常为1年）内，物质生产部门劳动者新创造的价值,它是物质资料生产进一步发展和人口再生产条件改善的物质基础。在其他条件已定的情况下,国民收入总量愈多,人均消费基金和积累基金也越多，从而有利于人们生活的改善和技术装备水平的提高，也有利于人口数量的控制和人口质量的提高。人口增长从 3个方面影响国民收入的增减： ① 人口或劳动者数量的多少； ② 每个劳动者技术装备水平的高低； ③ 劳动者节省消耗和管理才能的大小。 国民收入又分为资金的累积和消费，累积资金=国民收入错误！未找到引用源。消费资金，而消费资金=基本消费资金错误！未找到引用源。人口发展速度。因此， 为增加人均国民收入，增强一国的经济实力和提高人民生活水平，要在大力发展经济、增加生产的基础上合理地调节人口增长。 商人过河functionjueche=guohe %程序开始需要知道商人和仆人数； n=input（' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; ifnn>n n=input（'' 输入商人数目:'）; nn=input（' 输入仆人数目:'）; nnn=input（' 输入船的最大容量:'）; end %决策生成 jc=1;% 决策向量放在矩阵 d 中，jc 为插入新元素的行标初始为 1 ； for i=0:nnn for j=0:nnn if（i+j<=nnn）&（i+j>0）% 满足条D={（u,v） |1<=u+v<=nnn,u,v=0,1,2} d（ jc,1:3）=[i,j ，1] ；%生成一个决策向量立刻扩充为三维； d（ jc+1,1:3）=[-i,-j,-1];% 同时生成他的负向量； jc=jc+2;% 由于生成两个决策向量，则jc 要向下移动两个；end end j=0; end% 状态数组生成 kx=1;% 状态向量放在 A 矩阵中，生成方法同矩阵生成； for i=n:-1:0 for j=nn:-1:0 if((i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n))%(i>=j)&((n-i)>=(nn-j)))|((i==0)|(i==n ))为可以存在状态的约束条件 A(kx,1:3)=[i,j,1];% 生成状态数组集合D' A(kx+1,1:3)=[i,j,0]; kx=kx+2; end end j=nn; end; % 将状态向量生成抽象矩阵 k=(1/2)*size(A,1); CX=zeros(2*k,2*k); a=size(d,1); for i=1:2*k for j=1:a c=A(i,:)+d( j,:); x=find((A(:,1)==c(1))&(A(:,2)==c(2))&(A(:,3)==c(3))); 课程设计题目：农夫过河 一．问题描述 一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则： (1)农夫一次最多能带一样东西（或者是狼、或者是羊、或者是白菜）过河； (2)当农夫不在场是狼会吃羊； (3)当农夫不在场是羊会吃掉白菜。 现在要求为农夫想一个方案，能将3样东西顺利地带过河。从出事状态开始，农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。 二．基本要求 (1)为农夫过河问题抽象数据类型，体会数据模型在问题求解中的重要性； (2)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设 计； (3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态； (4)设计一个算法求解农夫过河问题，并输出过河方案； (5)分析算法的时间复杂度。 三．概要设计 (1)数据结构的设计 typedef struct // 图的顶点 { int farmer; // 农夫 int wolf; // 狼 int sheep; // 羊 int veget; // 白菜 }Vertex; 设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在河的南岸。 t ypedef struct { int vertexNum; // 图的当前顶点数 Vertex vertex[VertexNum]; // 顶点向量（代表顶点） bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; // 定义图的邻接矩阵存储结构 存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。 (2)算法的设计 深度优先遍历基本设计思想：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的1/12边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 程序中的深度优先遍历算法如下： void dfsPath(AdjGraph *graph, int start, int end) // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end) 商人过河问题 一、三名商人各带一名随从的情况 1．问题（略） 2．模型假设 ①当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状 态； ②小船至多可容纳2人，且渡河时由随从（或者商人）来划船。 3．分析与建模 商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：…… 其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态a变到状态b，则在点a和点b之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。 建模步骤：⑴首先要确定过河过程中的所有安全状态，我们用二元数组(,) x y 表示一个安全状态（不管此岸还是彼岸），其中x表示留在此岸的主人数，y表示留在此岸的随从数。两岸各有十种安全状态： (0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3) ⑵在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种 安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸(3,3)到彼岸(0,0)的最短路。 ⑶观察发现此岸的状态(0,0)，(3,0)和彼岸的状态(0,3)，(3,3)都是孤立点，在求最短路的过程中不涉及这些点，把它们删去。两岸的点用1,2, (16) 新标号。 （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） ○②④⑥⑧⑩○○12○14○16 ①③⑤○⑦⑨○11○13○15○ （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） 商人过河的数学模型及编程解决 摘要：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）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为： 作业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+1k S =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）可得 44k k x y -≥- 化简得 k k x y ≤ 《数学建模实验》课程考试试题 ----商人安全过河数学建模与求解 一．问题提出： 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 为偶数时船从彼岸驶向此岸，所以状态 商人们怎样安全过河 随从们密约, 在河的任一岸, 一旦随从 的人数比商人多, 就杀人越货. 但是乘船渡河的方案由商人决定. 商人们怎样才能安全过河? 问题分析： 多步决策过程 决策~ 每一步(此岸到彼岸或彼岸到此岸)船上 的人员 要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河. 建立模型 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=guohe clear all clc %%%%%%%%%%程序开始需要知道商人和仆人数；%%%%%%%%%%%%% shangren=input('输入商人数目: '); puren=input('输入仆人数目: '); rongliang=input('输入船的最大容量: '); if puren>shangren shangren=input('输入商人数目:'); puren=input('输入仆人数目:'); rongliang=input('输入船的最大容量:'); end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成 jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1； for i=0:rongliang for j=0:rongliang if (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要向下移动两个； end end j=0; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 状态数组生成 kx=1; % 状态向量放在A矩阵中，生成方法同矩阵生成； for i=shangren:-1:0 for j=puren:-1:0 if ((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; end end “过河”问题的解法 陕西省西安市长安区第二中学杨西武 【关键词】 迪克斯特拉算法，图论，最短路径 【内容提要】 信息学奥林匹克竞赛，各类资料中都涉及“过河”一题，但都没有给出详解及程序。历届考题也没有涉及到，原因是其测试数据不便给出多组。但此题对考察学生的分析能力和解题能力却很有帮助。本文旨在给出其详解。 【问题描述】 某人m带一只羊s，一只狼w和一筐白菜v过河。没有船，他每次游过河时只能带一件东西，当没有人管理时，狼和羊不能相处，羊和白菜不能相处。在这些条件的约束下，他怎样才能将三件东西从左岸带往右岸？试编程给出一组过河次数最少的方案。【问题分析】 用无向图描述上述问题的解法路径 用结点代表状态 例如：初始状态v1可记为 {}> Φ <, , , ,v w s m（即，人、羊、狼、 白菜皆在左岸，右岸为空，这是一种安全状态，即满足约束条件 的状态）。最终状态v10可记为 {}> Φ ⑨{}{}> 商人过河问题的Java编程解决 转自：“电脑编程技巧与维护”https://www.doczj.com/doc/b58932961.html,/摘要为商人过河问题建立数学模型，归结为路径搜索问题，并给出一个通用的Jav程序来解决此类问题。 关键词商人过河，二元组，链表，集合 一、描述 商人过河问题是一个传统的智力问题。其描述如下：三名商人各带一名随从乘船渡河，—只小船只能容纳二人，由他们自己划行。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中，商人们怎样才能安全渡河呢？ 商人过河问题可以看作一个多步决策过程，通过一系列决策步骤逼近决策目标，并最终达到决策目标。对于该问题的每一步决策，就是要对船由此岸驶向彼岸或由彼岸驶回此岸的人员（包括商人和随从）作出规划，在保证商人安全的前提下，通过有限的步骤，实现人员全部过河的目标。 二、分析 针对这一具体问题，可以经过一番精心安排，找到一个解决方案。不过，本文希望对这一问题进行发展和延伸，建立起数学模型，发现其中蕴含的规律，并借助计算机的运算能力，找到一个通用的一般解法。 在商人过河问题中，用一个二元组来表示岸上商人和随从的组成(m，s)，其中m表示商人人数，s表示随从人数，每个组合可以视为一种状态。所有可能的状态可以表示为集合： S0={(m, s)|0≤m≤3; 0≤s≤3} 安全状态要求商人人数为0，或者大于等于随从人数，因此，所有的安全状态可以表示为集合： S1={(m, s)| m=0, s=0,1,2,3; m=3, s=0,1,2,3; m=s=1,2} 二元组(m，s)也可以表示一次渡河方案，其中m表示船载的商人人数，s表示船载的随从人数。则所有的渡河方案可以表示为集合： S2={(m , s)|0≤m；0≤s；0≤m+s≤2 } 一次渡河决策可以表示为： (m, s)K+1 = (m , s)K - (-1)K(u, v)K K = 0,1,2,3… (m , s)K为第K次渡河时，岸上的商人和随从的组成，(u, v)K为第K次渡河方案，K从0开始。 整个决策方案就是要找到有限步渡河决策，使商人和随从的人数组成从原始状态（3，3），经由一系列中间的安全状态，迁移到最终状态（0，0）的过程。 三、编程 建立前面的数学模型后，即找到一条从状态（3，3）到（0，0）的路径，可以编写程序，利用计算机的计算能力，通过穷举法找到一条状态迁移路径。 1．类二元组 类Dual实现问题分析中提到的二元组，其主要代码如下： class Dual { int m, s; 数学建模作业 班级：数学131 姓名：丁延辉 学号：13190122 （二）商人过河Matlab代码 三个商人三个随从 z=zeros(30,3); %z为由(a,b,c)的列向量组成的3行30列数组，初始化为0矩阵，a,b,c代表此刻此岸的商人，仆人数量以及船的运行状态，c=1表示即将向彼岸运行 m=zeros(1,20); %m为一维行向量，初始化为1矩阵，用于在后面的程序中判断第k次选择的乘船方案 d=[0,1,1;0,2,1;1,0,1;1,1,1;2,0,1]; %共有5种可以选择的乘船方案，最后面一列全为1，即用于在后面表示使得z(k,3)的取值保持随着k的奇偶性保持着0-1变换. z(1,:)=[3,3,1]; %初始状态为[3,3,1] k=1; m(k)=1; %第一次默认的乘船方案为决策1——d(1) flag=1; %用于在后面判断是否成功找到方案 answer=0; %用于在后面判断是否找到 答案 while k>0 %保持k>0 if m(k)>5 flag=0; break; end p=0; z(k+1,:)=z(k,:)+(-1)^k*d(m(k),:); %每一次的运算规则都是z(k+1)=z(k)-(-1)^k*d(m(k),:),d(m(k),:)表示决策方案 a=z(k+1,1); %将当前情况的矩阵数值复制给a商人,b仆人 b=z(k+1,2); c=z(k+1,3); if (a==3&&(b==0||b==1||b==2||b==3))||(a==1&&b==1)||(a==2&&b==2 )||(a==0&&(b==0||b==1||b==2||b==3)) %判断(a,b)是否符合限定情况 for j=1:k %判断是否此岸a,b,c与之前有重复，如果是，结束此次循环，重新选择乘船方案 if a==z(j,1)&&b==z(j,2)&&c==z(j,3) if m(k)~=5 %决策方案只有5种，所以m(k)<=5， 2011高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）：西京学院 参赛队员(打印并签名) ：1. 邹高永 2. 张大伟 3. 钱晓东 指导教师或指导教师组负责人(打印并签名)： 日期：年月日赛区评阅编号（由赛区组委会评阅前进行编号）： 2011高教社杯全国大学生数学建模竞赛 编号专用页 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 评 阅 人 评 分 备 注 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）： 商人过河 摘要 本文针对商人安全渡河的问题，采用多步决策的过程建立数学模型，求解得到了在随从没有杀人越货的情况下的渡河方案。 对于本题而言，在3名商人、3名随从、船的最大容量为2的情况下，首先定义了渡河前此岸的状态，并设安全渡河条件下的状态集定义为允许状态集合，接着得到渡河方案的允许决策集合，然后得到状态随渡河方案变化的规律，最后利用平面坐标分析法，并利用计算机进行了仿真，得到了一种商人安全渡河的方案。 但是，本文不仅仅是为了拼凑出一个可行方案，而是希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。基于此目的，利用了dijkstra算法，得到最短路径的最优解。但同时由于该算法遍历计算的节点很多，所以效率低，而且当有多个最短距离时，不能够将所有符合条件的情况逐一列出。 最后，从这类问题解得趣味性、合理性进行了深入讨论，得到了“传教士与野蛮人渡河”，“印度夫妻渡河”等问题通用的模型，并将其进行了推广。这也是本文的一大特色。 关键词渡河问题状态集合决策集合平面坐标dijkstra算法 组长：王鹏道110714 组员：任利伟110713、孙祎110706 小组成员负责情况： 王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立孙祎：四、模型求解、五、模型的检验、拓展及延伸 2014年11月24日 摘要 为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。 关键词：多步决策计算机求解状态转移律图解法 一、 问题的提出 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河? 二、 问题的关键 解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。 三、 问题的分析 在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 四、 模型假设 记第k 次过河前A 岸的商人数为X K ， 随从数为Y K k=1，2，? X K ,Y K =0，1，2，3，将二维向量S K =(X K ，Y K )定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则 S={(X K ,Y K )|(X K =0,Y K =0,1,2,3),(X K =3,Y K =0,1,2,3),(X K =Y K =1)(X K =Y K =2)} 记第k 次过河船上的商人数为U K 随从数为V K 将二维向量D K =(U K ,V K )定义为决策．由小船的容量可知允许决策集合（记作D)为 D={(U K ,V K )|U K +V K =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)} 五、 模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 摘要：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）定义为状态。安全渡河条件下的状态集合称为允许状态集合，记为S，则允许状态集合为：商人过河问题
商人过河问题数学建模修订稿
商人过河问题
论文题目：过河问题
商人安全过河问题
商人过河问题matlab程序
农夫过河问题
商人过河问题
最新商人过河的数学模型及编程解决
商人过河问题数学建模
商人过河模型问题的求解
商人们怎样安全过河 (附MATLAB程序完整)
“过河”问题的解法
Φ <, , , ,v w s m ②{}{}> 商人过河问题的Java编程解决
商人过河matlab程序以及解析
商人过河优化模型
数学建模商人过河__论文
商人过河的数学模型及编程解决
相关主题
文本预览