動的計画法単語

ドウテキケイカクホウ

動的計画法とは、アルゴリズムの形の一つである。

概要

具体的な例で考えてみよう。東京から大阪まで陸路で移動する最短ルート検索せよ、といった問題があるとする。

最も単純な回答は、考えられるルートの組み合わせを全部並べて、その中で一番短いものを探す方法だが、これはどう考えても効率が悪い。

例えば、名古屋を経由するルートに注すると、「東京名古屋の全パターン」×「名古屋大阪の全パターン」の組み合わせを考える必要があるわけだが、その大部分は99%同じルートでどこか100メートルだけ違うみたいなものが延々並ぶので、一々すべて計算するのは時間の無駄なわけである。

ところで、東京名古屋の最短経路、名古屋大阪の最短経路がそれぞれ分かっていると仮定すると、当たり前だが

 東京名古屋大阪の最短経路 = 東京名古屋の最短経路 + 名古屋大阪の最短経路

になる。東京名古屋間でどのようなルートを通ろうと、名古屋大阪間の選択には影しないので、この分割ができれば駄な組み合わせを大幅にカットすることができる。

この考え方は当然ながらもっと細かく適用できる。東京名古屋の最短経路は長野経由か静岡経由のどちらかの最短経路を考えればいいだろうということになるし、どちらのルートも手近な首都高インターまでは共通というような感じになる。あるいは名古屋を経由しないで中央道から北陸に抜けたらどうなるかという可性について考慮するなら、長野ジャンクションまでは使いまわせるだろう。

これをパターンとして抽出すると、次のように説明できる。

  1. ある部分の(最適)解 = それを構成するパーツの(最適)解の和で説明できる
  2. 複数箇所で共通のパーツは一度計算すれば他で使いまわせる

このようなパターンで問題を分割し、必要な計算量を最適化する方法を動的計画法という。

n個の中からr個選ぶ組み合わせは何通り?(パスカルの三角形)

高校数学に出てくるnCr。これはn個の中からr個取り出す組み合わせが何通りあるかを表している。例えば、{A,B,C,D,E}の中から3つを選ぶ組み合わせは、{A,B,C}, {A,B,D}, {A,B,E}, {A,C,D}, ..., {C,D,E}の10通りである。単純にnCrめるには教科書に載っていれば公式を使えばよい。しかし、予め必要な範囲を事前に計算して配列に入れておくことでプログラムを高速化することができる場合がある。このようなときに使われるのがパスカル三角形である。

パスカル三角形では以下の公式を使う。

nCr=n-1Cr-1+n-1Cr

なんとなく漸化式っぽく見えると思う。これを使って動的計画法を説明していく。動的計画法では表に数値を書き込んでいくように計算を行う。まずは表を用意する。続いて一番最初の答えを書き込む。ここでは0C0=1を書き込む。(0個の中から0個取り出す組み合わせは1通りである。)

n↓ r→ 0 1 2 3 4
0 1
1
2
3
4

続いて公式を使って、一つ前の計算結果から次の計算結果を計算できるところを順に埋めていく。ここでは2行のn=1の部分を埋めていく。公式nCr=n-1Cr-1+n-1Crとなっているので、nCrを計算するにはn-1Cr-1n-1Crを足せば良い。これは、計算しようとしているマス左上と上のマスの値を足せばそのマスの値が計算できるということである。

n↓ r→ 0 1 2 3 4
0 1
1 1 1
2
3
4

ここで、欄となっているところや、表の外側に出た部分は0として扱っている。同様に次の行も埋めていく。

n↓ r→ 0 1 2 3 4
0 1
1 1 1
2 1 2 1
3
4

同様に最後まで埋めていくとパスカル三角形完成する。

n↓ r→ 0 1 2 3 4
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1

これらをC++に書くと以下のようになる。


int main() {
        static const int N = 30;
        int C[N][N];
        memset(C, 0, sizeof(C));
        C[0][0] = 1;
        for (int n = 1; n < N; ++n) {
                C[n][0] = C[n - 1][0];
                for (int r = 1; r < N; ++r) {
                        C[n][r] = C[n - 1][r - 1] + C[n - 1][r];
                }
        }
}

ナップザック問題

以下、執筆

巡回セールスマン問題

以下、執筆

関連商品

関連コミュニティ

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E5%8B%95%E7%9A%84%E8%A8%88%E7%94%BB%E6%B3%95

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

動的計画法

1 yama
2010/08/02(月) 00:43:58 ID: STKZ8TK7Fj
パスカル三角形は、
nCr=n-1Cr-1+nCr
nCr=n-1Cr-1+n-1Cr
^^^
ではないでしょうか.
2 yama
2010/08/02(月) 01:20:28 ID: STKZ8TK7Fj
^^^がずれました.
n-1Cr の n-1の下に書いたつもりです.
3 nodchip
2010/08/02(月) 10:09:53 ID: tvVCz76rNQ
>>2
ありがとうございます。修正いたしました。
4 ななしのよっしん
2010/08/19(木) 17:42:26 ID: /76r25pouO
08年初頭だったかな「巡回セールスマン問題」というタグ
差別につけて回っているヤツがいたようだけど
暇だったから全部辿って消してやった
5 ななしのよっしん
2015/06/15(月) 12:24:30 ID: mHY6ycBXXG
自分に意味がわからなかったから勝手に意味を変える編集者スゲー
最適解はどこへ行った
6 ななしのよっしん
2016/12/18(日) 23:35:04 ID: VHW4OHtJrF
ここの定義だと単に漸化式とか再帰アルゴリズムのことを言ってるだけだよな。

必須定義:
* 問題全体は部分部分の結果を足せば出る
* 一度解いた問題は二度解かない <- これ重要
** 単に割ってくだけの作りだと同じサブ問題があちこちに出てダブることがあるので、その時は前の結果を使いまわす

必須ではないけどデフォ:
* そうやってベストケースな組み合わせを効率良く探す
7 ななしのよっしん
2016/12/19(月) 00:26:48 ID: VHW4OHtJrF
そもそも動的「計画法」という名前は、最終結果はとりあえず置いといて、先にどんな材料があれば答えが出るか決めちゃおうというところから来てる。
一般的にでかい問題は分割統治して、それぞれ別に作った結果を最後にがっちゃんこするってのがよくあるセオリーなわけだが、それぞれが全に独立でやっちゃうと部品の共通化ができなくてすげー効率が悪いわけよ。だから元締め側でそこは管理して「これは余所で用意したのと一緒だからそれを使いまわす」という車輪の再発明をしないというのがミソなわけだ。
ただ普通の計画と違って部品を作りながら足りないところを増やしていくから動的だという言い方をする。
8 ななしのよっしん
2019/05/29(水) 17:23:23 ID: f880YqjIl6
>>7
なるほどわかりやすい(ありがとう!)

急上昇ワード

2019/08/20(火)23時更新