《狼羊菜过河和商人过河问题.doc》由会员分享，可在线阅读，更多相关《狼羊菜过河和商人过河问题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、1狼羊菜过河问题；（状态变量法）我们可以用四维向量来表示状态：各分量依次来表示人，狼，羊，菜：在左岸状态记为1，在对岸记为0；则可行的状态向量为：1,1,1,1, 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 00 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0共10个引入四维转移矩阵 0表示不过河，1表示过河，则有1,0,0,0 1 1 0 01 0 1 01 0 0 1规定状态向量与转移向量运算：1+1=0 1+0=1,0+1=1，0+0=1；首先由1 1 1 1与转移矩阵运算得状态0 1 0 1 ,由下继续运算得1 1 0 1-0 0 01-1
2、0 1 1 -0 0 1 0-1 0 10-0 0 0 0黑岩 编号1002：商人过河n=input(输入商人数目：);nn=input(输入仆人数目：);nnn=input(输入船的最大容量：); jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1； for i=0:nnn for j=0:nnn if (i+j0) % 满足条D=(u,v)|1=u+v=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
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 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)=
4、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; endend 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)=; jueche
