商人过河问题matlab程序

商人过河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)));

v(i,x)=1;%x 为空不会改变v 值end

end%dijstra 算法

x=1;y=size(A,1);

m=size(v,1);

T=zeros(m,1);

T=T4-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='cannotreach';

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)=[];