「動的計画法」の版間の差分
削除された内容 追加された内容
Jellyfishprince (会話 | 投稿記録) 編集の要約なし |
Jellyfishprinceさんの書かれた定義が少し変だと思うので、書かれた内容を概要に移動しました。 |
||
1行目:
'''動的計画法'''（どうてきけいかくほう、{{lang-en-short|Dynamic Programming, DP}}）は、[[計算機科学]]の分野において、
== 定義 ==
特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である。一般的に、帰納的な定義にしたがって再帰法でアルゴリズムを作ると計算結果の再利用は行わないが、入力が単純な構造で解が等しくなることの確認が容易であるとき、同じ入力について計算済であることの確認、結果の再利用をメモリ領域を消費して行い、計算を高速化する。▼
初歩的な説明で使われるフィボナッチ数の計算、ハノイの塔の必要移動回数の計算などでは、一次元の表（列）によって指数オーダーの計算時間を入力の数の大きさに対して線形時間に落とすことができる。（ただし、これらの級数の計算では、漸化式で参照するのは高々 2 つ前の計算結果だけなので、変数を1, 2 個用意してループすればことたりる。）▼
効果が顕著なのが組合せ問題で、文字列の近似照合（編集距離の計算）、ナップサック問題の解法などが、二次元の表により指数時間の手続きが多項式時間に効率化される有名な例である。▼
マルチプルアラインメントのように表が三次元以上必要になると、時間に対するトレードオフとなるメモリ領域量が大きくなりすぎるため、規模の大きな入力には実用的でなくなる。▼
▲帰納的な解法として分割統治法が使われている場合、次のようになる <ref name="ai">アルゴリズムイントロダクション 第3版 ISBN 978-4764904088</ref>。
# [[分割統治法]]：部分問題を解き、その結果を利用して、問題全体を解く
# [[メモ化]]：部分問題の計算結果を再利用する
16 ⟶ 11行目:
== 概要 ==
「動的計画法(dynamic programming)」という言葉は[[1940年代]]に[[リチャード・E・ベルマン]]が最初に使いはじめ、[[1953年]]に現在の定義となった<ref>Richard Bellman, An introduction to the theory of dynamic programming, The Rand Corporation, Santa Monica, Calif., 1953</ref>。
効率のよい[[アルゴリズム]]の設計技法として知られる代表的な構造の一つである。
対象となる問題を帰納的に解く場合にくり返し出現する小さな問題例について、解を表に記録し表を埋めていく形で計算をすすめ、冗長な計算をはぶくアルゴリズムのことをいう。
▲特定のアルゴリズムを指すのではなく、上記のような手法を使うアルゴリズムの総称である。一般的に、帰納的な定義にしたがって再帰法でアルゴリズムを作ると計算結果の再利用は行わないが、入力が単純な構造で解が等しくなることの確認が容易であるとき、同じ入力について計算済であることの確認、結果の再利用をメモリ領域を消費して行い、計算を高速化する。
▲初歩的な説明で使われるフィボナッチ数の計算、ハノイの塔の必要移動回数の計算などでは、一次元の表（列）によって指数オーダーの計算時間を入力の数の大きさに対して線形時間に落とすことができる。（ただし、これらの級数の計算では、漸化式で参照するのは高々 2 つ前の計算結果だけなので、変数を1, 2 個用意してループすればことたりる。）
▲効果が顕著なのが組合せ問題で、文字列の近似照合（編集距離の計算）、ナップサック問題の解法などが、二次元の表により指数時間の手続きが多項式時間に効率化される有名な例である。
▲マルチプルアラインメントのように表が三次元以上必要になると、時間に対するトレードオフとなるメモリ領域量が大きくなりすぎるため、規模の大きな入力には実用的でなくなる。
[[近似アルゴリズム]]の分野では、[[多項式時間]]での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似[[多項式時間]]では最適解を得ることができる。
| |||