【Ruby】【アルゴリズム】川渡り問題(深さ優先検索Ver)
今日の二丁目はちび専ガッちびナイトかー。orz
川渡り問題とは
男と3つの荷物--キツネ(狐),ガチョウ(鵞鳥),トウモロコシ(玉蜀黍)1袋--のうちの1つしか運べません。キツネとガチョウまたはガチョウとトウモロコシをいっしょにしておくことはできません。どうやって無事これらを向こう岸に渡らせることができるでしょう。
http://homepage3.nifty.com/aokura/html5/jscript/cross1.html
うーん、、このリンク元のサイトのほうがコードの量が全然少ない。
右岸・左岸にいるときで実装を書き分けてるのがスマートじゃないよね。。
調べてみたら「状態空間表現」という手が使えるみたい。
http://d.hatena.ne.jp/mohayonao/20110117/1295267818
次はこれでやってみよう。
■コード
#回答表示用 def show answers answers.each do |ans| ans.each do |step| puts _dehash(step) end puts "-------------" end end #回答表示用 def _dehash(step) arr = step.split("_") another_side = "right" another_side = "left" if arr[2] == "false" "carry #{arr[0]} to #{another_side}" end @_members = ["dack", "corn", "wolf"] #現在の状況をスナップ def _hash(now, left, is_left_side) now + "_" + left.join("") + "_" + is_left_side.to_s end #食べられてしまうものを岸に残していないか def daijyobu? arr return false if arr.index("dack") != nil && arr.index("corn") != nil return false if arr.index("wolf") != nil && arr.index("dack") != nil true end def solve(now, left, history, answers) #左岸になくなったら終了 return answers << history if left.length == 0 is_left_side = false is_left_side = true if (history.length) % 2 == 0 #右岸からの出発は”何も乗せない”というアクションが可能 if !is_left_side && daijyobu?(@_members - left) hash_val = _hash("", left, is_left_side) if history.index(hash_val) == nil _history = history.dup _history << hash_val answer = solve("", left, _history, answers) end end if is_left_side #積荷を降ろす left << now if now != "" left.each do |candidate| #さっき積んだ物は再び乗せない next if candidate == now _left = left.dup; _left.delete(candidate) #食べてしまう場合はnext next if !daijyobu?(_left) hash_val = _hash(candidate, _left, is_left_side) #実行履歴のないものだけ実行する if history.index(hash_val) == nil _history = history.dup _history << hash_val solve(candidate, _left, _history, answers) end end else #右岸に着いたとき candidates = @_members - left candidates << now if now != "" candidates.each do |candidate| next if candidate == now _right = candidates.dup _right.delete(candidate) next if !daijyobu?(_right) hash_val = _hash(candidate, left, is_left_side) if history.index(hash_val) == nil _history = history.dup _history << hash_val solve(candidate, left, _history, answers) end end end answers end answers = solve("",["dack", "corn", "wolf"],[], []) show(answers)
■実行結果
carry dack to right carry to left carry corn to right carry dack to left carry wolf to right carry to left carry dack to right ------------- carry dack to right carry to left carry wolf to right carry dack to left carry corn to right carry to left carry dack to right -------------