怎样用MATLAB解决状态转移问题（例如商人过河问题）

Question

三个商人各带一名随从欲经过一条河流，只有一小船在河岸且一次最多能载两人过河，随从暗自商议再和的任一岸只要人数多于商人则杀死商人逃离，问商人怎样抉择才能安全渡河？（用MATLAB解决，并能显示其中一河岸的状态）

Answer 1

function jueche=guohe

%%%%%%%%%%%%%%%%%%%%%%
程序开始需要知道商人和仆人数；
n=input(‘输入商人数目:’,’12’);
nn=input(‘输入仆人数目:’,’12’);
nnn=input(‘输入船的最大容量:’,’20’);
if nn>n
n=input(‘输入商人数目:’,’23’);
nn=input(‘输入仆人数目:’,’23’);
nnn=input(‘输入船的最大容量:’,’34’);
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=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);
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='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)=[];

Answer 2

写一个搜索才可以哦。