動的計画法とは
どうてきけいかくほう
問題を小さな部分問題に分け、部分問題の答えを表に記録して再利用することで、同じ計算の繰り返しを避けるアルゴリズムの設計方法。ナップサック問題、硬貨の最少枚数、最長共通部分列、最短経路などに使われる。
「動的計画法」は、1分野の3問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
考え方: 重なる部分問題を1回だけ解く
フィボナッチ数を fib(n) = fib(n−1) + fib(n−2) とそのまま再帰で計算すると、同じ値を何度も計算し直し、呼び出しの回数は指数関数的に増えます(fib(30) で約269万回)。動的計画法では、一度求めた部分問題の答えを表に記録し、次からは表を引くだけにします。こうすると fib(n) は n に比例する手間で求まります。使える条件は、大きな問題の最適解が小さな部分問題の最適解から組み立てられること(最適部分構造)と、同じ部分問題が何度も現れること(部分問題の重なり)です。
メモ化と表の埋め方
実装には、再帰の形のまま、計算した結果を覚えておくメモ化(トップダウン)と、小さい部分問題から順に表を埋めていくボトムアップの2つの方法があります。例えば0/1ナップサック問題では、「品物 i までを使い、容量 c 以内で得られる最大の価値」を表にし、品物を入れる場合と入れない場合の大きい方を選びながら埋めていきます。品物の数を n、容量を W とすると、手間は O(nW) です。硬貨の最少枚数の問題も、0円から目標の金額まで、各金額の最少枚数を順に表にすれば解けます。
貪欲法との違いと応用
貪欲法はその時点で最もよい選択を1つ選んで先に進むだけなので速いものの、問題によっては最適解になりません。1円・4円・6円の硬貨で8円を払う場合、貪欲法は6 + 1 + 1の3枚ですが、動的計画法なら4 + 4の2枚が求まります。動的計画法は、文字列の編集距離や最長共通部分列(diffコマンド)、DNA配列のアラインメント、音声認識のビタビアルゴリズム、すべての頂点間の最短経路を求めるフロイド・ワーシャル法など、幅広く使われています。
動的計画法の練習問題に挑戦
フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fib(n−2) を返す」と再帰で定義した。fib(5) を呼んだとき、fib が呼ばれる回数は最初の呼び出しを含めて何回か。
- A6回
- B9回
- C15回
1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係として正しいものはどれか。
- A貪欲法でも最少の2枚になる
- B貪欲法では3枚になり、最少の2枚にならない
- C貪欲法では3枚になり、これが最少である
よくある質問
動的計画法と分割統治法はどう違いますか?
どちらも問題を部分問題に分けますが、マージソートのような分割統治法では部分問題が重ならないので、表に記録する必要がありません。動的計画法は、同じ部分問題が何度も現れる場合に、答えを記録して再利用する点が違います。
動的計画法の弱点は何ですか?
表の大きさの分だけ記憶領域と手間が必要です。ナップサック問題の O(nW) は容量 W の値に比例するので、W が非常に大きいと現実的でなくなります。必要な部分だけを記録したり、1行前の結果だけを残したりして、記憶領域を減らす工夫をします。
解説の中の「動的計画法」
計算した値を表に覚えておくメモ化(動的計画法)を使えば、計算は fib(0)〜fib(5) の6通りで済み、呼び出しも9回(2n − 1)に減ります。
フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fi…動的計画法で「0円から8円までの各金額を払う最少枚数」を小さい金額から順に表にすれば、必ず最少の枚数が求まります。
1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係…動的計画法では「容量 c までで達成できる最大の価値」を品物ごとに表で更新し、品物の数 n と容量 W に対して O(nW) で最適な値が求まります。
容量8のナップサックに、(重さ, 価値) が (2, 3)、(3, 4)、(4, 5)、(5, 6) の4つの品物から…
「動的計画法」が出てくる問題(3問)
- フィボナッチ数を求める関数 fib(n) を「n が1以下なら n を返し、そうでなければ fib(n−1) + fib(n−2) を返す」と再帰で定義した。fib(5) を呼んだとき、fib が呼ばれる回数は最初の呼び出しを含めて何回か。
- 1円、4円、6円の3種類の硬貨で8円を支払う。大きい硬貨から使えるだけ使う貪欲法で決めたときの枚数と、最少の枚数の関係として正しいものはどれか。
- 容量8のナップサックに、(重さ, 価値) が (2, 3)、(3, 4)、(4, 5)、(5, 6) の4つの品物から選んで入れる。各品物は1つずつしかなく、分割できない。重さの合計が8以下で、価値の合計の最大値はいくらか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。