Document

動的計画法
• 表の作成
• 制約の追加
• 練習問題
動的計画法とは
・ (組合せ最適化などの)問題を解く解法のひとつ
・ 問題が直線的な構造を持つとき、その構造にそって反復的
に解く
・ 特徴は、簡単な問題をたくさん解き、その解の表から、ひと
つずつ問題を解く、というもの。最終的に、解きたい大きさ
の問題が解ける
サブセットサム問題
・ n 個の数(a1,…,an)がある。これらの数の組合せで、合計
がちょうど b になるようなものがあるか?
例題) 15, 24, 65, 32, 4, 55, 54, 23
の組合せで合計が 145 となるものはあるか?
サブセットサム問題 (2)
・ n 番目の数だけ取り除いた問題を考える
・ 元の問題に合計 b の組合せがある
 取り除いた問題で合計 b か b - an の組合せがある
例題) 15, 24, 65, 32, 4, 55, 54, 23
の組合せで合計が 145 となるものはあるか?
 15, 24, 65, 32, 4, 55, 54
の組合せで合計が 145 か 122 となるものはあるか?
分枝限定法で解く
・ 要素 an から順番に、使う/使わないを決め、問題を分割し、
再帰的に解く
最後の 23 を取り除く
問題0: 15, 24, 65, 32, 4, 55, 54
問題1: 15, 24, 65, 32, 4, 55, 54
合計 145 はある?
合計 122 はある?
同様に
問題00: 15, 24, 65, 32, 4, 55
問題01: 15, 24, 65, 32, 4, 55
合計 145 はある?
合計 91 はある?
問題10: 15, 24, 65, 32, 4, 55
問題11: 15, 24, 65, 32, 4, 55
合計 122 はある?
合計 68 はある?
分枝限定法で解く (2)
・ 問題11111: 15, 24, 65
・ 問題000: 15, 24, 65, 32, 4
合計 -23 となるものはあるか?
合計 145 はとなるものはあるか?
・ こういった明らかに実行不能な問題は、すぐに答えが分かる
最悪で O(2n) 時間かかる
動的計画法
アイディア:
・ 0 から b までの全ての数について、合計がその数になる組
合せがあるかどうかを調べ、表を作る
・ anを取り除いた問題で、組合せてできる数を全て調べる
 元の問題で組合せてできる数は、
これらに anを加えた/加えないもの
1つ数を取り除き、小さくした問題の、
すべてのb についての答えの表を作れればよい
アルゴリズム
・ f( i, m ) : a1 ,…, ai の組合せで、和が m となるものがあれ
ば1、そうでなければ 0
・ i = 1,…,n に対して、以下の操作を実行する。
全ての 0 ≦m≦ b に対して、 f( i, m ) を計算する
・ f(i,m) = 1
・ f(i,m) = 0
f(i-1,m) =1 または f(i-1,m-ai) =1
f(i-1,m) =0 かつ f(i-1,m-ai) =0
・ f(1,m) は簡単に計算できる
計算時間は O(nb)
動的計画法コード
・ a[0],…,a[n-1] に数値を格納
DP_setsum (int *a, int n, int b){
int i, j, f[b+1];
for ( j=0 ; j<=b ; j++ ) f[j] = 0;
f[0] = 1;
for ( i=0 ; i<n ; i++ ){
for ( j=b-a[i] ; j>=0 ; j-- ){
if ( f[j] = = 1 ) f[j+a[i]] = 1;
}
}
for ( j=b ; j>=0 ; j-- ){
if ( f[j] = = 1 ){
printf (“%d\n”, j );
break;
}
}
}
もっと短いやつ
・ a[0],…,a[n-1] に数値を格納
DP_setsum (int *a, int n, int b){
int i, j, f[b+1];
for ( j=0 ; j<=b ; j++ ) f[j] = j;
for ( i=0 ; i<n ; i++ ){
for ( j=b-a[i] ; j>=0 ; j-- ){
if ( f[j] < f[j+a[i]] ) f[j+a[i]] = f[j];
}
}
printf (“%d\n”, b-f[b] );
}
どっちが速い?
・ 分枝限定法 : O(2n) 時間
・ 動的計画法 : O(nb) 時間
だいたい、 2n > b ならば動的計画法が速い
n = 30 ⇒ 2n ≒ 10億
ウィークポイント
・ 数に小数があるときは、表に当てはまらない数が出てくる
 ある程度の桁数までなら、小数点以下の数を
1単位とした表を作ればよい
・ それでも、循環小数・無理数のような数があると計算できない
メモリを省略
・ サブセットサム問題を解く動的計画法は、b が大きいと、大きなメ
モリと時間を消費する
・ 精度を犠牲にして、メモリと時間を節約する方法がある
・ 表のマスを、縦 ε個ずつまとめる
 縦のマスの数は b/ε個に減る
・ (x,y) のマスに書き込む代わりに、 (x, Ly/ε」) に書き込む
 エラーが最大 ε-1 発生
 n 反復繰り返すと、エラーの最大は n(ε-1)
誤差が n(ε-1) の範囲のものしか見つけられないが
メモリと時間は 1/εにできる
サブセットサムの解の数
・ n 個の数(a1,…,an)がある。これらの数の組合せで、合計がちょ
うど b になるようなものは、いくつあるか?
・ 15, 24, 65, 32, 4, 55, 54, 23
の組合せで合計 145 となるものはいくつ?
動的計画の拡張
・ f( i, m ) : a1 ,…, ai の組合せで、和が m となるものの数
・ i = 1,…,n 、 m = 0,…,b に対して、 f( i, m ) を計算する
・ f( i, m ) = f( i-1, m ) + f( i-1, m-ai )
・ f( 1, m )
は簡単に計算できる
計算時間は O(nb)
練習問題
・ 1,1,2,3,3,4,5,7 の組合せで、
合計 10 となる組合せはいくつあるか?
ちょうど k 個の和
・ n 個の数(a1,…,an)がある。これらの数のk個の組合せで、合計
がちょうど b になるようなものは、いくつあるか?
例) 15, 24, 65, 32, 4, 55, 54, 23 の中の 4個の数の組合せで
合計 145 となる組合せはいくつ?
動的計画の拡張
・ f( i, j, m ) : a1 ,…, ai の j 個の組合せで、
和が m となるものの数
・ i=1,…,n 、 j=0,…,k 、 m=0,…,b に対して、
f(i,j,m) を計算する
・ f( i, j, m ) = f( i-1, j, m ) + f( i-1, j-1, m-ai )
・ f(1,j,m) は簡単に計算できる
計算時間は O(nkb)
ナップサック問題
・最大積載量のあるナップサックに荷物を詰める問題
- 荷物はいくつかある
- 荷物はそれぞれ重さが違う
- 荷物はそれぞれ価値が違う
- 荷物の重さの合計は、最大積載量を超えてはいけない
このとき、荷物の価値の合計が最大になる詰め込み方を求めよ
ナップサック問題 (2)
・ 荷物 i の重さを ai 、価値を ci 、ナップサックの最大積載量を
b とすると、定式化は
max. Σ ci xi
s.t. Σ ai xi ≦ b
xi ∈ { 0,1 }
・ NP-hard 問題である
動的計画の拡張
・ f(i,m) : 荷物 1,…,i の組合せで、重さの和が m となるも
のの中での、 価値の和の最大値
max. Σ cj xj
s.t. Σ aj xj = m
x1,…, xi ∈ { 0,1 }
max. Σ cj xj
s.t. Σ aj xj = m
xi = 0
x1,…, xi -1 ∈ { 0,1 }
max. Σ cj xj
s.t. Σ aj xj = m- ai
xi = 1
x1,…, xi-1 ∈ { 0,1 }
・ f( i, m ) = max { f( i-1, k ), f( i-1, m-ai ) + ci }
・ f(1,m)
は簡単に計算できる
計算時間は O(nb)
ナップサックDPコード
・ a[0],…,a[n-1] に重さ、 c[0],…,c[n-1] に価値を格納
DP_knapsack (int *a, int *c, int n, int b){
int i, j, m=0, mx=0, f[b+1];
for ( j=0 ; j<=b ; j++ ) f[j] = -1;
f[0] = 0;
for ( i=0 ; i<n ; i++ ){
for ( j=b-a[i] ; j>=0 ; j-- ){
if ( f[j] >= 0 && f[j+a[i]] < f[j]+c[i] ) f[j+a[i]] = f[j]+c[i];
}
}
for ( j=b ; j>=0 ; j-- )
if ( f[j] > m ){ m = f[j]; mx = j; }
printf (“weight = %d, profit = %d\n”, mx, m );
}
練習問題
・ n 個の数(a1,…,an)がある。これらの数を3つのグループに分け、
1つ目のグループの合計が b1 に、2つ目のグループの合計が
b2 になるようなものはあるか?
・ この問題を解くための動的計画法を設計しなさい
問題の例)15, 24, 65, 32, 4, 55, 54, 23 を1番目、2番目のグルー
プの合計が 120,110 とするようななる分け方はあるか?
直線構造の利用
・ 動的計画法のキモは、大きさが小さい問題の解を用いて、現在
の問題が解けるかどうか。
・ 言い方を変えれば、左から右に問題を解いていったときに、自
分の答えが、自分の左だけを見て作れるか
・ これは、ある種の直線構造があるかどうか、と考えていいだろう
(現時点の右側を変更しても、左側に影響がない、あるいは影響
が簡単なパラメータになる(重みの合計とか、組合せ的でな
い))
・ つまり、直線構造があれば動的計画を使えばいいし、動的計画
を使えるかどうかは、直線構造があるかないか
(有向非閉路的グラフとか、木も直線構造)
最長昇順列
・ 与えられた数列の中で、小さい順になっている部分列を昇順部
分列と言う
・例: 1,5,4,7,2,5,3,9,6,8  1,2,6 など
・ 与えられた数列の中から、最も長い昇順列を見つける問題を最
長昇順列問題という
・ この問題は直線構造がある
直線構造はあるか
・ i 番目の数 ai が最後となるような昇順列を考える
・ このような昇順列の後ろに何を追加しても、前半部分が昇順列
でなくなることはない
・ つまり、もし、ai が最適解に含まれるなら、前半部分(ai より小さ
な添え字を持つ数)が作る昇順列は、そのようなものの中で最
長になっているはず
 このあたりが直線構造
直線構造はあるか
・ i 番目の数 ai が最後となるような昇順列の中で最も長いものの
長さを f(i) とする
・ i 番目の数 ai が最後となるような昇順列は、aj, aj<ai, j<i である
ような aj で終わる昇順列の最後に ai を付け足して得られる
 各aj まで終わる最長列の中で、最も長いものに ai を付け加
えればいい
・ f(i) = max { f(j) | aj<ai, j<i } +1
・ 計算時間は O(n2)
・ ヒープの亜種に、「添え字がここまでのものの中で最大値は
何?」という質問に O(log n) 時間で答えられるやつがあるので、
それを使うと、 O(nlog n)
パスの数
・ 有向サイクルを含まないような、非閉路的グラフの、2点間を結
ぶ有向パスの数を計算する
グラフの直線的な構造を利用
・ 非閉路的なので、グラフの頂点に終点から始点方向に、終点に
近いほうが必ず小さくなるような番号付けができる
(自分から行ける頂点は自分よりも小さい)
・ この順番でスキャンすることで、表を作ることはできないが、
数が数えられる
3
6
9
5
7
2
0
4
8
1
番号順にパスの数を数える
・ グラフが非閉路的なので、頂点 v から終点へのパスの数は、v
からいける頂点から終点までのパスの数の総和
 番号順に、パスの数を計算すればよい
1+2
11+3
14+33
+40
9
87
2+3+6
3
14
6
11
5
33
7
2
0
1
6
4
8
40
14+11
+2+6
1+1
33+6+1
1+2+3
1
まとめ
・ 組合せ最適化問題に対する動的計画法の作り方
(漸化式を作れれば良い)
・ サブセットサム・その変形・ナップサック問題・最長部分昇順列・
非閉路的グラフの2点間を結ぶパスの数、に対する動的計画
法