商人过河问题的MATLAB和C语言程序

n=3;m=3;h=2; %初始状态及数据 m0=0;n0=0; tic LS=0; LD=0; 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<N k=1; sa=[]; sb=[]; for i0=1:le s0=q(i0,:); if f0==1 break end for i=1:LD 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 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