動的計画法がかすかに分かった

オイラー・プロジェクトの18問目、67問目。ピラミッド状に並んだ数字を上から下までたどるとき、足した結果が最大になる経路を見つけろというもの。

単純に上から大きい方を選びつつ降りていくだけでは正解は得られない。かといって、可能な経路をすべて調べると、ちょっと数が多くてつらいというところ。18問目と67問目は同じ問題だけど、18問目が15段でブルートフォースでも何とかなるのに対して、67問目は100段あって全経路を調べるには膨大な時間がかかる。経路は2^99（≒10^68）通りあるので、1秒間に1億経路をチェックしたとして10^60秒かかる計算。1年は10^17秒なので10^43年ぐらい。

これもやっぱり、動的計画法とかメモ化とかでいいんだろうと思いながら、コルメンのアルゴリズム教科書で、動的計画法のところをざっと読んでみたら、ちょっとすっきりした。

動的計画法と、再帰によるバックトラックをメモ化で高速化する手法は、トップダウンとボトムダウンの違いでしかなく、本質的ではないようだ。本質的なのは、問題を分割したときに、「部分の最適化」が全体に適用できることと、そうした最適化の重複が存在していること。こうした問題に対しては動的計画法が適用できる可能性が高い、ということ。分割統治と呼ばれてるものは部分問題の間に依存性がなく、分割したときにまた新しい問題となるような問題に対するアプローチ。と、そんな分類をしてくれてスッキリ。

漸化式を使って定式化もできるものの、工学的に見て適用可能かどうかを判断する基準は何かといった議論も興味深い。つまり、応用という点では自明じゃないってことなのか。

ともあれ、論理的にはトップダウン的解法のほうが簡単に感じる。小さな部分に着目して問題を再帰的に定義すればいいだけだから、単純。あとは表を作って、結果を蓄積していけばいいだけ。というわけで、Rubyで書いたのは以下。

def read_data
  nums = []
  while line = gets
#    print line
    line.chomp!.gsub!(/^ +/, "")
    next if line =~ /$^/
    nums << line.split(/ +/).map{|n| n.to_i}
  end
  nums
end

def max(level, pos, nums, table)
  return table[level][pos] if table[level][pos]

  left  = max(level+1, pos, nums, table)
  right = max(level+1, pos+1, nums, table)

  if left > right then
    table[level][pos] = nums[level][pos] + left
  else
    table[level][pos] = nums[level][pos] + right
  end
  table[level][pos]
end

nums = read_data
table = nums.map {|ary| ary.map{nil}}
table[-1] = nums[-1].dup
p max(0, 0, nums, table)

=begin
   3
  7 4
 2 4 6
8 5 9 33

nums  = [3, [7, 4], [2, 4, 6], [8, 5, 9, 33]]
table = [nil, [nil, nil], [nil, nil, nil], [8, 5, 9, 33]]
=end

numsからtableを作るのが意外に自明じゃなかった。あと、メモをグローバル変数とかに入れたくなるけど、そういう遠隔的な副作用って何だか嫌な感じもある。で、たくさん変数を渡すのって関数呼び出すのコストがなぁという感覚があるけど、考えてみれば、Rubyでは参照渡しだし、低レベルに考えてみれば、これってグローバル変数を使うのと本質的にはあんまり違わなくて、参照の名前をグローバルにしなくて済む分、変数なんか全部毎回渡しちゃえというスタイルのほうがいい気がしてきた。うーん、とか考えると、そのたびに変数をduplicateする純関数型って、やっぱりメモリの無駄使いがすごい感じがする。

ていうかnumsとtablesはstruct的に1つにするべきだったのか。