商人们怎样安全过河
随从们密约, 在河的任一岸, 一旦随从
的人数比商人多, 就杀人越货. 但是乘船渡河的方案由商人决定. 商人们怎样才能安全过河? 问题分析：?多步决策过程
决策~ 每一步(此岸到彼岸或彼岸到此岸)船上的人员
要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河. 建立模型
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)=[];
%%%%%%%%%%%%%%%%%% 程序完 %%%%%%%%%%%%%%%%%%