メモ付き探索(Ruby)
- 作者: 川中真耶,杵渕朋彦,椎名俊輔
- 出版社/メーカー: アスキー・メディアワークス
- 発売日: 2012/05/30
- メディア: 大型本
- 購入: 5人 クリック: 34回
- この商品を含むブログ (6件) を見る
次のような問題があります。
石の山があり、そこから二人で代わる代わる 1〜3 個の石を取ってゆく。最後の石を取った方が勝ちとする。
自分の番になって石が n 個あるとすると、ここで取るべき個数の最善手を与えるメソッド solve(n) を書け。
ただし、何個取っても負ける場合は 0 を返すものとする。
まずは素朴に再帰で書いてみました。残りの石が 1〜3 個のときは、それを取れば勝ちですし、そうでなければ、相手の次の手が(自分にとって)必勝になればよい。そのようにプログラミングします。
def solve1(n) return n if n <= 3 1.upto(3) {|i| return i if solve1(n - i).zero?} return 0 end puts solve1(40) #user 0m30.776s
石が 40個の場合で、30秒近くかかっています。このアルゴリズムではかかる時間が指数関数的に増えていくので、たぶん石が 50個にでもなると実用的ではなくなってしまします(※追記 実際にやってみました。50分ほどかかりました)。
次に、一旦結果を「メモ」する方法で求めてみます。これをすると、余計な探索が不要になり、高速化が期待できます。
def solve2(n, memo) return memo[n] unless !memo[n] or !(memo[n] > 0) return (memo[n] = n) if n <= 3 1.upto(3) {|i| return (memo[n] = i) if solve2(n - i, memo).zero?} return (memo[n] = 0) end puts solve2(1000, []) #user 0m0.024s
実際、石が 1000個の場合でも 0.1秒以下で求められました。大幅に高速化されています。メソッド内の第 1 行目がキモです。メモしておいた数値がここで使われます。
ということで必勝法ですが、i が1〜10 くらいで solve(i) を求めてみるとわかります。石が n 個のとき、n を 4 で割ったあまりだけ石を取ればよろしい。n が 4 の倍数なら必敗です。