メモ付き探索(Ruby)

アルゴリズムを学ぼう

アルゴリズムを学ぼう



次のような問題があります。

石の山があり、そこから二人で代わる代わる 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 の倍数なら必敗です。