Coursera「Data Structures and Algorithms」

ここ1ヶ月半CourseraでCSのコースを受講しているのですが、そこで動的計画法についての面白い話があったのでシェア。 www.coursera.org 「Data Structures and Algorithms」という課程の中の「algorithmic-toolbox」コースWeek5のテーマが「動的計画法」です。

動的計画法(Dynamic Programming)とは

まず前提として動的計画法とは何か？という話です。

Wikipediaより

動的計画法 - Wikipedia

計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。

分割統治法：部分問題を解き、その結果を利用して、問題全体を解く

メモ化：部分問題の計算結果を再利用する

抽象化された説明なので知らない方はピンと来ないかもしれませんが「アルゴリズムのグループの名前」であることと、「分割統治法」「メモ化」の2つの手法を使うという、認識でとりあえず問題ないと思います。具体的にはナップサック問題やレーベンシュタイン距離の計算に使われます。

なぜDynamic「Programming」なのか

動的計画法の英語名称はDynamic Programmingなのですが、なぜ上述したようにアルゴリズムのグループなのに、Programmingという名前なのか、というのはずっと不思議でした。

「動的計画法」はリチャード・E・ベルマンという数学者によって1953年に考案されています。ちなみにベルマンは、動的計画法以外にもベルマン方程式やハミルトン-ヤコビ-ベルマン方程式を考案していたり、1976年にジョン・フォン・ノイマン理論賞と受賞したりと歴史的にも重要な数学者です。

リチャード・E・ベルマン - Wikipedia

Dynamic「Programming」と名付けられた理由は、動的計画法が生まれた背景にあると、Courseraの授業で教えてもらったのですが、調べていたらより詳しく動的計画法の生まれた経緯について書かれたPaperがあったのでこちらから引用させてもらい、ざっくりとして翻訳をしてきたいと思います。

https://pubsonline.informs.org/doi/pdf/10.1287/opre.50.1.48.17791

科学用語が大嫌いな国防長官WilsonとDynamic Programmingの誕生

The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research

1950年代は数学は不遇だった。その当時の国防長官だったWilsonが研究/研究用語を病的に恐れ憎んでいたからだ、というようなことが書いてあります。この研究の中に数学が含まれているのだと思います。

His face would suffuse,he would turn red, and he would get violent if people used the term, research, in his presence.

もし彼の目の前で研究用語を使おうものなら顔が真っ赤になって攻撃的になったと。恐ろしすぎますね。

The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation.

The RAND Corporation(当時ベルマンが所属していた企業)は、空軍から仕事をもらっていて、空軍のボスはWilsonだったので、なんとしても数学的なことを社内でやっていると知られるわけにいきませんでした。

What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons.

どうやらベルマンは最初は「planning」という名前を考えていたらしいのですが、色々な理由から良くないと判断したようです。

I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone.

ベルマンは最終的に「programming」という名前を選択します。段階的要素と時間変動的要素を表した言葉ということで「dynamic」という名前も考えられました。これは前述した「分割統治法」「メモ化」が段階的に実行されていくことを表していると思います。

Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense.

この、古典的な物理学での力学系という意味でも全く正しい「dynamic」という言葉を使おうと決めます。この方も物理学での力学系との類似を指摘されていますが、この文章だけ読むとどちらかというと後付だったようで、非常に興味深いです。

qiita.com

It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name.

また軽蔑的な意味にならないことも大事だったと書いてあります。あまりピンとこないような気もしますが、そういう時代背景だったのでしょうか。もしかしたらDynamic Programmingと似た部分のあるGreedyArgorithm(貪欲法)の存在も影響しているのかもしれません。