狼羊菜过河和商人过河问题

《狼羊菜过河和商人过河问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1狼羊菜过河问题；（状态变量法）我们可以用四维向量来表示状态：各分量依次来表示人，狼，羊，菜：在左岸状态记为1，在对岸记为0；则可行的状态向量为：[1,1,1,1,][0000][1010][0101][1110][0001][1011][0100][1101][0010]共10个引入四维转移矩阵0表示不过河，1表示过河，则有[1,0,0,0][1100][1010][1001规定状态向量与转移向量运算：1+1=01+0=1,0+1=1，0+0=1；首先由[1111]与转移矩阵运算得状态[0101],

2、由下继续运算得[1101]->[0001]->[1011]->[0010]->[1010]->[0000]黑岩编号1002：商人过河n=input('输入商人数目：');nn=input('输入仆人数目：');nnn=input('输入船的最大容量：');jc=1;%决策向量放在矩阵d中，jc为插入新元素的行标初始为1；fori=0:nnnforj=0:nnnif(i+j<=nnn)&(i+j>0)%满足条D={(u,v)

3、1<=u+v<=nnn,u,v=0,1,2}d(jc,1:3)=[i,j,1]

4、;%生成一个决策向量立刻扩充为三维；d(jc+1,1:3)=[-i,-j,-1];%同时生成他的负向量；jc=jc+2;%由于生成两个决策向量，则jc要向下移动两个；endendj=0;endkx=1;%状态向量放在A矩阵中，生成方法同矩阵生成；fori=n:-1:0forj=nn:-1:0if((i>=j)&((n-i)>=(nn-j)))

5、((i==0)

6、(i==n))%(i>=j)&((n-i)>=(nn-j)))

7、((i==0)

8、(i==n))为可以存在的状态的约束条件A(kx,1:3)=[i

9、,j,1];%生成状态数组集合D`A(kx+1,1:3)=[i,j,0];kx=kx+2;endendj=nn;end;k=(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值endendx=1;y=size(A,1);m=size(v,1);T=zer

10、os(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);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;endendendmi=min(T(a));ifmi==infbreak;

11、elsed=find(T==mi);d=d(1);P(d)=mi;T(d)=inf;k=d;S(d)=1;endendiflmd(y)==infjueche='cannotreach';return;endjueche(1)=y;g=2;h=y;while(1)ifh==xbreak;endjueche(g)=lmd(h);g=g+1;h=lmd(h);endjueche=A(jueche,:);jueche(:,3)=[];jueche