せかいや

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

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