水差し問題のプログラミング(MATLAB, FreeMat)

 

ダイハード３の１シーン。　https://www.youtube.com/watch?v=BVtQNK_ZUJg

 

４リットル・３リットルの水差しで２リットルを計るにはどうすべきか？

 

この水差し問題を幅優先探索で調べると以下の探索順になる。

　　　　(0,0) (4,0) (0,3) (4,3) [0,0] (1,3) [4,3] [0,0] (3,0) [0,3] [4,0] [4,3] [0,3]

　　　　(1,0) [4,0] [4,0] (3,3) [0,3] [4,0] [1,3] [0,0] (0,1) [4,3] [0,3] [3,0] (4,2)

ただし、[ ]は既に出てきた状態であるのでそれ以上調べない。2が出たら終了。

 

計算結果（３リットル・５リットルの水差しで合計７リットルにする場合の例）

  0  3  0  0  3  3  3  0  1  2  1  2

  0  0  5  3  5  2  3  2  5  0  0  5

  1  1  1  2  2  3  4  6  7  8  9 10   （この行は一つ前の状態の i ）

i_k =   10 　13  

 

%  Mizusasi.m : 水差し問題(MATLAB, FreeMat)

global state check i k

setpath('C:\FreeMat\0_12_Mizusasi'); % MTALABでは不要

MAX = [3,5];    % 容器AとBの容量（litter）

GOAL  = 7;    % 求める水の容量

state = [0,0,1];   % 状態（水量）を格納する。3列目は前の状態(i)

check = zeros(MAX(1)+1,MAX(2)+1);   % 同一状態のチェック用  

A=0; B=0; i=0; k=2; check(1,1)=1; sw=0;

while (sw==0)

    i=i+1;

  for j=1:2

    if state(i,j)==0 

        state(k,j)=MAX(j); state(k,3-j)=state(i,3-j); MizuSub(state(k,:));

    elseif state(i,j)==MAX(j) 

        state(k,j)=0; state(k,3-j)=state(i,3-j); MizuSub(state(k,:));  

    end

    if state(i,j)>=MAX(3-j)-state(i,3-j)

        state(k,j)=state(i,j)-MAX(3-j)+state(i,3-j);

        state(k,3-j)=MAX(3-j); MizuSub(state(k,:));

    elseif state(i,j)>0;

        state(k,j)=0; state(k,3-j)=state(i,j)+state(i,3-j); MizuSub(state(k,:));

    end

  end

%  if state(k,1)==GOAL || state(k,2)==GOAL sw=1; end % GOALが片方だけの場合

  if state(k-1,1)+state(k-1,2)==GOAL sw=1; end % GOALが和である場合

end

state' % 状態遷移の表示

i_k=[i k] % i k の表示

 

function MizuSub(a) % サブプログラム

  global state check i k

    if check(a(1)+1,a(2)+1)==1

    else

        check(a(1)+1,a(2)+1)=1; state(k,3)=i; k=k+1; 

    end