動的計画法と分割統治法

昨日の中間発表でつっこまれた用語の混同を直すために、ここにメモしておこうと思います。今後もこんな感じで研究に関することをまとめておけば、いざというときに役に立つかも。

まず、動的計画法(Dynamic Programing)とは、オペレーションズリサーチのなかの計画問題を解くために用いられる手法で、高校の数学などで習った線形計画法の兄弟みたいなものです。（兄弟だからといって、解き方が似ているというわけではないです。）全ての部分問題をちょうど一回解き、それぞれ答えを表に格納して、同じ問題を複数回解かないようにします。この部分問題の解から最終的な問題の解を発見します。

これに対して、分割統治法(Divide and Conquer)は最終的な問題に対して再帰的な構造を見つけ出し、小さな問題に分割してから、部分問題の解を利用して最終的な問題の解を求めるって手法のようです。

分割統治法はBottomUp的な手法なのに対して、分割統治法はTopDown的な手法と考えてよいでしょう。

群馬大学の情報系の学科の講義ホームページを参照してみると、もう少しいろいろと詳しい話を調べることができます。