北太天元解人、狼、羊、菜渡河问题
%北太天元求解 渡河问题(人、狼、羊、蔬菜)
%某人带狼、羊、蔬菜渡河，有一艘船，每次渡船人最多只能载一物。
%我们知道狼吃羊、羊吃蔬菜，所以在人不在场时，狼和羊不能共存，
%羊和菜不能共存。试问此人最少的渡河次数。
%我们假设河是东西走向的，人、狼、羊、菜开始在北岸，最终的目标是
%人、狼、羊、菜都到了南岸。
% 用一个向量表示人、狼、羊、菜的state(态)，如
% (1,1,1,1) 表示人、狼、羊、菜都在北岸
% (1,1,1,0) 表示人、狼、羊在北岸，菜在南岸
% 总共有2^4=16种状态
% 最终要达到的状态是 人、狼、羊、菜都在南岸, 也就是态 (0,0,0,0)
% 我们为了简化问题，还可以先把不可能的状态排除掉，如
% (1,1,0,0) -- 羊和菜都在南岸(人在北岸,狼在北岸）
% (0,0,1,1) -- 羊和菜都在北岸（人在南岸,狼在南岸）
% (1,0,0,0) -- 羊和菜都在南岸(人在北岸, 狼在南岸）
% (0,1,1,1) -- 羊和菜都在北岸（人在南岸, 狼在北岸）
% (0,1,1,0) -- 狼和羊都在北岸 (人在南岸）
% (1,0,0,1) -- 狼和羊都在南岸 (人在北岸）
%
%这些状态和数字的对应
% 二进制 0,0,0,0 对应到 0
% 二进制 i1,i2,i3,i4 对应到 i1*2^3 + i2*2^2+i3*2^1 +i4*2^0
% 其中 i1,i2,i3,i4 分别取值为0，1
%
% 每一个态对应一个节点
%从一个态可以转化为另一个态，我们认为两个节点（这个两个态对应的节点
%连接有一条边。
A = zeros(16,16);
for i=1:16
for j=1:16
A(i,j) = has_edge(i-1,j-1);
end
end
%观测 A^k(16,1) 随着k的增加什么时候开始变成非零，这表明从state (1,1,1,1)
% 到state (0,0,0,0) 开始有了一条长度为k的路径
p = A(16,1);
B = A;
路径长度 = 1;
while p == 0
B = B*A;
p = B(16,1);
路径长度 = 路径长度+1;
end
% 把态转成一个数
% s 是一个长度是4的向量，每个分量是0或1
function n = state_no( s )
n = s(1)*2^3 + s(2)*2^2 + s(3)*2 + s(4);
end
% 把state_no 专程state_vec
% n 是0-15之间的整数
function s = state_vec( n )
s = zeros(4,1);
s(1) = floor(n/8);
s(2) = floor( (n-s(1)*8)/4);
s(3) = floor( (n-s(1)*8-s(2)*4)/2);
s(4) = n-s(1)*8-s(2)*4-s(3)*2;
end
%判断节点i 和节点j 是否有边连接
% i 和 j 都是 state_no
function b = has_edge(i,j )
vi = state_vec(i);
vj = state_vec(j);
if( vi(1) == vj(1) ) % 两个态之间的变换一定要有人的状态的改变
% vi(1) == vj(1) 说明人的状态没有改变，因此没有路径
b = 0;
return;
end
if(vj(1) == 1) % 人在北岸
if(vj(2) == 0 && vj(3) == 0) % 狼和羊在南岸
b = 0;
return;
end
if(vj(3) == 0 && vj(4) == 0) % 羊和菜在南岸
b = 0;
return;
end
else % 人在南岸
if(vj(2) == 1 && vj(3) == 1) % 狼和羊在北岸
b = 0;
return;
end
if(vj(3) == 1 && vj(4) == 1) % 羊和菜在北岸
b = 0;
return;
end
end
if(vi(1) == 1) % 人在北岸
if(vi(2) == 0 && vi(3) == 0) % 狼和羊在南岸
b = 0;
return;
end
if(vi(3) == 0 && vi(4) == 0) % 羊和菜在南岸
b = 0;
return;
end
else % 人在南岸
if(vi(2) == 1 && vi(3) == 1) % 狼和羊在北岸
b = 0;
return;
end
if(vi(3) == 1 && vi(4) == 1) % 羊和菜在北岸
b = 0;
return;
end
end
v = vi-vj;
d = sum(abs(v(2:4)));
if(d > 1) % 这说明人带着两个或者以上的东西过河，这不符合最多携带一个的要求
b = 0;
return;
end
b = 1;
end
