【Ruby】【アルゴリズム】有限オートマトンとは？宣教師と人食い問題（全列挙型Ver）　※だめな解法

数式解析できたよーってメールしたら、返事が来たよ。

数式解析は最初の題材にはちょうど良かったね。

字句解析は有限オートマトンでやって
構文解析はプッシュダウン・オートマトンってのでやることが多いです。

　
ふむふむ。
何言ってるのかなー。
じゃなかった。
調べてみよう。

有限オートマトンとは

有限個の状態と遷移と動作の組み合わせ
http://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3

なるほど。

このWikiを見ることで、よくプログラミング言語の話で
「状態を持つ」「オブジェクト」「状態を持たない」
みたいなワードが出てくるけど、良く意味が分かった。
「同じトリガーに対してシステムの反応が常に同じではない」など。

川渡り問題を有限オートマトンで解く？

取りうる状態が明らかになっているのか。
なるほど。
川渡り問題「宣教師と人食い」をこれで考えてみよう

３人の宣教師と３人の人食い人種がいて、舟を使って向こう岸まで渡ろうとしています。
舟には２人まで乗ることができます。
ところが、どんな状況でも、宣教師の数がそこにいる人食い人種の数より少なくなると、彼らに殺されしまいます。

怖い！
夜に解いてたら怖くなる問題だよー。。

結果

大失敗
　
大失敗orz
　
取れる状態（両岸とも食べられない）を全て列挙して、
それら一つ一つに「今の状態から遷移可能か？」を判定したんだけど、
遷移可能か判定するのが煩雑（詳細は下記）で、
むちゃ長いコードに。。
全列挙は、こういう問題は向いていない。

そりゃそうだよね。
「取れる状態」よりも「今の状態から取れるパターン」のほうが断然数が少ない。
全列挙だと徒に計算量が多くなってしまう。
　
学んだよ。。

おまけに、

これはあまり有限オートマトンとはいわないと思いますよ。
状態遷移図ではなく、ただ状態を列挙しただけですね。
有限オートマトンは有限の状態とその遷移の管理がポイントですが、これは遷移の管理してないですよね
単に試してみて、ダメだったら別のをって感じですよね、それはオートマトンとはいわないと思います

確かに。
遷移の状態は見ていない。
駄目だったら次、を繰り返してるだけ。

学んだよ。。

「遷移可能か判定するのが煩雑」を詳しくorz

今回の実装では左岸にいる状態を0、右岸にいる状態を1にしています。

000000  #<= 全員が左岸
111000  #<= 人間が右岸、鬼が左岸

　
例えば「左⇒右」の移動をするとして、これはどこかのビットが立つ状態になる。
　
で、

010100
↓
010000

の遷移はありうるか？というと、NG。「ありえない」。
　
現在1のところが0になることはないから（右岸に移動はない）

　
さらに、

010100
↓
011111

の遷移はありうるか？というと、NG。「ありえない」。
　
1になるビットの最大数は２だから（ボートの店員は2名）

　
さらに、「左←右」の移動を考える必要があり。
左に移動する場合は、

010100
↓
010000

の遷移はありうるか？というと、OK。

　
どうですか？
複雑ですよね。。

コードで書くとこんな感じです。
ビット演算が使えないかとも工夫したのですが、見つからず。

if ～ elsif ～ end　がほとんど同じことをやっているので、
ブロック渡しにすることで少し行数は減らせますが、
本質的に取るべき解法ではないので、そこまでリファクタリングの気力も湧かず。

def possible?(now, pattern, trial_count)
  return false if now == pattern
  count = 0
  if trial_count %2 == 0 #右から左へ
    now.split("").each_with_index do |n, i|
      if n == "0"
        return false if pattern[i] != "0" #0->1（右岸に移動）は出来ない
      else
        count += 1 if pattern[i] != "1" #移動するものをカウント
      end
    end
    return false if count>2 #移動する物の数が2以上は不可能
  else #左から右へ
    now.split("").each_with_index do |n, i|
      if n == "1"
        return false if pattern[i] != "1" #1->0（左岸に移動）は出来ない
      else
        count += 1 if pattern[i] != "0"
      end
    end
    return false if count>2
  end
  true
end

　
以下、駄目なコード。
0と1をcharだったりfixnumだったりと読み替えてるのもイケテない。
明日もっと良いコードを書く。
　

コード全量

def make_candidate
  results = ["000000"] #人人人鬼鬼鬼が左岸
  6.times do |i|
    _results = results.dup
    _results.each do |res|
      tmp2 = res.dup
      tmp2[i] = "1"
      results << tmp2
    end
  end
  results
end
def make_approvals results
  apps = []
  results.each do |res|
    a = res[0].to_i + res[1].to_i + res[2].to_i 
    b = res[3].to_i + res[4].to_i + res[5].to_i 
    if a == 3 || a == 0
      apps << res 
    elsif (3-a) >= (3-b) && a >= b #左岸がOK&&右岸がOK
      apps << res 
    end
  end
  apps
end

def possible?(now, pattern, trial_count)
  return false if now == pattern
  count = 0
  if trial_count %2 == 0 #右から左へ
    now.split("").each_with_index do |n, i|
      if n == "0"
        return false if pattern[i] != "0" #0->1（右岸に移動）は出来ない
      else
        count += 1 if pattern[i] != "1" #移動するものをカウント
      end
    end
    return false if count>2 #移動する物の数が2以上は不可能
  else #左から右へ
    now.split("").each_with_index do |n, i|
      if n == "1"
        return false if pattern[i] != "1" #1->0（左岸に移動）は出来ない
      else
        count += 1 if pattern[i] != "0"
      end
    end
    return false if count>2
  end
  true
end
def dejavu?(history, pattern, trial_count)
  history.each_with_index do |his, i|
    h1 = his[0].to_i + his[1].to_i + his[2].to_i 
    h2 = his[3].to_i + his[4].to_i + his[5].to_i 
    p1 = pattern[0].to_i + pattern[1].to_i + pattern[2].to_i 
    p2 = pattern[3].to_i + pattern[4].to_i + pattern[5].to_i 
    return true if (h1 == p1) && (h2 == p2) && (i%2 == trial_count%2)
  end
  false
end

@patterns = make_approvals(make_candidate)
def solve (now, history)
  history << now
  return true if now == "111111"
    @patterns.each do |pat|
      if possible?(now, pat, history.length) && !dejavu?(history, pat, history.length)
        return true if solve(pat, history) == true
      end
    end
  history.pop
end

history = []
solve("000000", history)
p history

　
■実行結果

["000000", 
 "100100", 
 "000100", 
 "000111",
 "000110", 
 "110110", 
 "100100", 
 "111100", 
 "111000", 
 "111110", 
 "111100", 
 "111111"]

大局を見誤ったらこうなる、という例で。
　
おやすみなさい。。

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】有限オートマトンとは？宣教師と人食い問題（全列挙型Ver）　※だめな解法

有限オートマトンとは

川渡り問題を有限オートマトンで解く？

結果

「遷移可能か判定するのが煩雑」を詳しくorz

コード全量