%北太天元求解 渡河問題(人、狼、羊、蔬菜)

%某人帶狼、羊、蔬菜渡河，有一艘船，每次渡船人最多只能載一物。

%我們知道狼吃羊、羊吃蔬菜，所以在人不在場時，狼和羊不能共存，

%羊和菜不能共存。試問此人最少的渡河次數。

%我們假設河是東西走向的，人、狼、羊、菜開始在北岸，最終的目標是

%人、狼、羊、菜都到了南岸。

% 用一個向量表示人、狼、羊、菜的state(態(tài))，如

% (1,1,1,1) 表示人、狼、羊、菜都在北岸

% (1,1,1,0) 表示人、狼、羊在北岸，菜在南岸

% 總共有2^4=16種狀態(tài)

% 最終要達到的狀態(tài)是 人、狼、羊、菜都在南岸, 也就是態(tài) (0,0,0,0)

% 我們?yōu)榱撕喕瘑栴}，還可以先把不可能的狀態(tài)排除掉，如

% (1,1,0,0)?-- 羊和菜都在南岸(人在北岸,狼在北岸）

% (0,0,1,1)?-- 羊和菜都在北岸（人在南岸,狼在南岸）

% (1,0,0,0)?-- 羊和菜都在南岸(人在北岸, 狼在南岸）

% (0,1,1,1)?-- 羊和菜都在北岸（人在南岸, 狼在北岸）

% (0,1,1,0) --?狼和羊都在北岸 (人在南岸）

% (1,0,0,1) --?狼和羊都在南岸 (人在北岸）

%

%這些狀態(tài)和數字的對應

% 二進制 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

%

% 每一個態(tài)對應一個節(jié)點

%從一個態(tài)可以轉化為另一個態(tài)，我們認為兩個節(jié)點（這個兩個態(tài)對應的節(jié)點

%連接有一條邊。

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

% 把態(tài)轉成一個數

% 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

%判斷節(jié)點i 和節(jié)點j 是否有邊連接

% i 和 j 都是 state_no

function b =?has_edge(i,j )

???vi = state_vec(i);

???vj = state_vec(j);

???if( vi(1) == vj(1) )?% 兩個態(tài)之間的變換一定要有人的狀態(tài)的改變

?????????????????????????% vi(1) == vj(1) 說明人的狀態(tài)沒有改變，因此沒有路徑

??????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