商人过河问题matlab程序

function jueche=guohe

%%%%%%%%%%%%%%%%%%%%%%

程序开始需要知道商人和仆人数；

n=input('输入商人数目: ')

nn=input('输入仆人数目: ')

nnn=input('输入船的最大容量: ')

if nn>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=1y=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)=0lmd(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=2h=y

while(1)

if h==x

break

end

jueche(g)=lmd(h)

g=g+1

h=lmd(h)

end

jueche=A(jueche,:)

jueche(:,3)=[]

% n为商人数，m为仆人数，h为每次过河的最多人数

clear

n=3m=3h=2

m0=0n0=0

LS=0 % 允许的状态集合S与个数LS

LD=0 % 允许的决策集合D与个数LD

for i=0:n

for j=0:m

if i>=j&n-i>=m-j|i==n|i==0

LS=LS+1S(LS,:)=[i j]

end

if i+j>0&i+j<=h&(i>=j|i==0)

LD=LD+1D(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% 第n次允许的策略集逐次搜索

s0=q(i0,:)

if f0==1

break

end

for i=1:LD % 由s0搜索D后得到允许的状态

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 % 搜索对比S后允许状态

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-1saa1=sa

SA=zeros(tr,2)SB=zeros(tr,2)

for k=tr:-1:2

k1=k-1f0=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,:)

% 输出

SC = ones(size(SA))*3 - SA

nStep = ceil( size(SB,1) / 2 )

fprintf('\n过河步骤：\n')

for i = 1 : nStep

fprintf('第%i步：%i商%i仆过河', i, SB(2*i-1,:))

if i <nStep

fprintf('，%i商%i仆返回\n', SB(2*i,:))

else

fprintf('，完成\n\n')

end

end

fprintf('过河过程中状态变化：\n步骤 此岸商 此岸仆 方向 彼岸商 彼岸仆\n')

for i = 1 : nStep

fprintf('%3i %4i%8i ==> %4i%8i\n', i, SA(2*i-1, :), SC(2*i-1, :))

if i <nStep

fprintf(' %4i%8i <== %4i%8i\n', SA(2*i, :), SC(2*i, :))

end

end

---