« I'm possible と云われても | メイン | グラフ理論というといかめしいが »
2010年07月17日
なぜ「動的計画法」というか？
DP、すなわち、Dynamic Programming （動的計画法）は古典的アルゴリズムの代表で、現在でも広く使われている。 最短パス（最短路）を求めるアルゴリズムとして知られるダイクストラ法も、原点はDPなので、DPを理解してもらうために、毎年重要な演習課題の１つとして課している。
ステージごとにベストな途中解をまとめていくので、計算手数は（最悪） n の２乗で抑えられるという「アルゴリズム上の特徴」に、どうしても力点をおく話し方になってしまう。 まぎらわしいのは Dynamic Programming の programming であるが、昔から英語の発音どおりのプログラミングでなく「計画法」という訳語が使われるので、Ｃプログラミングなどの programming とは区別してもらえると思っている。 「計画法」と訳されるように、これは「アルゴリズム」を意味するからである。
何故「動的計画法」と云うか？ 演習では、通常グラフの辺（枝）に数値が与えられるため「静的計画法」のように見てしまうが、この数値は動的に与えられることを前提にしているのである。 「はやぶさ」などロケットを考えてみればいい。 刻々データは変わるので、各ステージで最新のデータを得て、つぎのステージの最適解を求めて、つぎのステージへ行く。 もちろん、つぎのステージでも最新をデータを使う。 こうして、いつも「その時点ではベストな解」を得るアルゴリズムになっている。
「正解を求める方法」に集中すると、背後にある話をしている時間がなくなるので、ここに書いた次第。
投稿者 tadashi : 2010年07月17日 08:41