ダイナミック・プログラミング演算法？

質問

ダイナミック・プログラミング演算法って何ですか？

回答No.2

fushigichan

tomokun_thさん、こんにちは。

ダイナミック・プログラミングとは、ヘルマンによってなされた最適化法の研究です。

ある接点Ａから接点Ｄへの最短絡が与えられたとします。
これを、L(A,D)と書くこととします。
このＡからＤに至る経路の途中に、接点Ｂを経由するとすると、
ＡからＢへの部分もまた、最短絡になっています。

[証明]
ＡからＢへの別の最短絡があったとし、
Ａ→Ｃ→Ｅ→Ｂ　が、そうだとします。
このとき、
L(A,C)+L(C,E)+L(E,B)<L(A,B)
ということになりますね。
さて、この辺辺にL(B,D)を加えれば
L(A,C)+L(C,E)+L(E,B)+L(B,D)<L(A,B)+L(B,D)
ということになります。
このことは、
Ａ→Ｃ→Ｅ→Ｂ→Ｄが、Ａ→Ｂ→Ｄ
よりも短いということになって、路Ａ→Ｂ→Ｄが
最短であるという仮定に反します。
よって、最短絡の途中の接点への部分も、また最短絡になっていることを示す。

詳しくは、参考URLをご覧下さい。
この性質を体系的に扱った、最適化法の研究が
ベルマンによってなされました。
これが、Ｄ．Ｐ．（ダイナミック・プログラミング）とか
最適化法の原理と呼ばれるものです。

参考URL：

http://ysserve.cs.shinshu-u.ac.jp/Lecture/Optimization1/node13.html,http://www.genome.ad.jp/Japanese/lect/13-01.html

回答No.1

hitomura

＞ダイナミック・プログラミング演算法って何ですか？
いや、これだけ書かれても…

すみませんが、何の学習／仕事で、かつ、どんな文脈で登場した言葉か教えていただけないでしょうか？

補足

そうですね・・・すみませんでした。

今大学で、「多属性効用分析」というものを勉強しているのですが、その中で出てきた言葉です。

決定分析のパラダイムの中の５段階の過程のうちの「最適化分析」という項目で、「最適化分析するには、ダイナミックプログラミング演算法を使用するのが最も単純で、適切である。」という記述があり、詳しい説明は何も載っていませんでした。

自分で調べてみようと試みたのですが、全く資料が出てこないので、困っていたので、ここに質問させてもらいました。

もし説明できる方がいらっしゃれば、よろしくお願いします。