商人们怎样安全过河
随从们密约, 在河的任一岸, 一旦随从
的人数比商人多, 就杀人越货.
但是乘船渡河的方案由商人决定.
商人们怎样才能安全过河?
问题分析：多步决策过程
决策~ 每一步(此岸到彼岸或彼岸到此岸)船上
的人员
要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.
建立模型
xk~第k次渡河前此岸的商人数xk, yk=0,1,2,3;
yk~第k次渡河前此岸的随从数k=1,2,|....
sk=(xk , yk)~过程的状态S ~ 允许状态集合
S={(x , y)x=0, y=0,1,2,3; x=3, y=0,1,2,3; x=y=1,2}
uk~第k次渡船上的商人数uk, vk=0,1,2;
vk~第k次渡船上的随从数k=1,2,.....
dk=(uk , vk)~决策D={(u , v)u+v=1, 2} ~允许决策集合
~状态转移律
多步决策问题求dk D(k=1,2, n), 使sk S, 并按转移律由s1=(3,3)到达sn+1=(0,0).
模型求解
穷举法~ 编程上机
S={(x , y)x=0, y=0,1,2,3;x=3, y=0,1,2,3; x=y=1,2}
图解法
状态s=(x,y) ~ 16个格点允许状态~ 10个点
允许决策~ 移动1或2格; k奇,左下移; k偶,右上移.
d1,.......，d11给出安全渡河方案
评注和思考
规格化方法,易于推广
考虑4名商人各带一随从的情况
程序
%%%%%%%%%%%%%%%% 开始%%%%%%%%%%%%%%%%%%%%%%
function jueche=guohe
clear all
clc
%%%%%%%%%%程序开始需要知道商人和仆人数；%%%%%%%%%%%%%
shangren=input('输入商人数目: ');
puren=input('输入仆人数目: ');
rongliang=input('输入船的最大容量: ');
if puren>shangren
shangren=input('输入商人数目:');
puren=input('输入仆人数目:');
rongliang=input('输入船的最大容量:');
end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 决策生成
jc=1; %决策向量放在矩阵d中，jc为插入新元素的行标初始为1；
for i=0:rongliang
for j=0:rongliang
if (i+j<=rongliang)&(i+j>0) % 满足条D={(u,v)|1<=u+v<=rongliang,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=shangren:-1:0
for j=puren:-1:0
if ((i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))
% (i>=j)&((shangren-i)>=(puren-j)))|((i==0)|(i==shangren))为可以存在的状态的约束条件A(kx,1:3)=[i,j,1]; %生成状态数组集合D `
A(kx+1,1:3)=[i,j,0];
kx=kx+2;
end
end
j=puren;
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)=[];
%%%%%%%%%%%%%%%%%% 程序完%%%%%%%%%%%%%%%%%%。