资源描述：
《商人们怎样安全过河 (附MATLAB程序完整)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、商人们怎样安全过河随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.但是乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析：D多步决策过程决策~每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.建立模型xk~第k次渡河前此岸的商人数xk,yk=0,1,2,3;yk~第k次渡河前此岸的随从数k=1,2,
2、....¼¼sk=(xk,yk)~过程的状态S~允许状态集合S={(x,y)
3、x=0,y=0,1,2,3;x=3,y=0,
4、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)
5、u+v=1,2}~允许决策集合~状态转移律多步决策问题求dkÎD(k=1,2,¼n),使skÎS,并按转移律由s1=(3,3)到达sn+1=(0,0).模型求解穷举法~编程上机S={(x,y)
6、x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}图解法状态s=(x,y)~16个格点允许状态~10个点允许决策~移动1
7、或2格;k奇,左下移;k偶,右上移.d1,.......，d11给出安全渡河方案评注和思考规格化方法,易于推广考虑4名商人各带一随从的情况程序%%%%%%%%%%%%%%%%开始%%%%%%%%%%%%%%%%%%%%%%functionjueche=guoheclearallclc%%%%%%%%%%程序开始需要知道商人和仆人数；%%%%%%%%%%%%%shangren=input('输入商人数目:');puren=input('输入仆人数目:');rongliang=input('输入船的最大容量:
8、');ifpuren>shangrenshangren=input('输入商人数目:');puren=input('输入仆人数目:');rongliang=input('输入船的最大容量:');end%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%决策生成jc=1;%决策向量放在矩阵d中，jc为插入新元素的行标初始为1；fori=0:rongliangforj=0:rongliangif(i+j<=rongliang)&(i+j>0)%满足条D={(u,
9、v)
10、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矩阵中，生成方法同矩阵生成；fori=shangren:-1:0forj=puren:-
11、1:0if((i>=j)&((shangren-i)>=(puren-j)))
12、((i==0)
13、(i==shangren))%(i>=j)&((shangren-i)>=(puren-j)))
14、((i==0)
15、(i==shangren))为可以存在的状态的约束条件A(kx,1:3)=[i,j,1];%生成状态数组集合D`A(kx+1,1:3)=[i,j,0];kx=kx+2;endendj=puren;end;%%%%%%%%%%%%%%%将状态向量生成抽象矩阵%%%%%%%%%%%%%%%%%%%k=(
16、1/2)*size(A,1);CX=zeros(2*k,2*k);a=size(d,1);fori=1:2*kforj=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);
17、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);ifsize(aa,1)==mbreak;endforj=1:size(a,1)pp=a(j,1);ifv(k,pp)~=0ifT(pp)>(P(k)+v(k,pp))T(pp)=(P(k)+v(k,pp));lmd(pp)=k;endende
