動的計画法 表の作成 制約の追加 練習問題

動的計画法とは • （組合せ最適化などの）問題を解く解法のひとつ • 問題が直線的な構造を持つとき、その構造にそって反復的に解く • 特徴は、簡単な問題をたくさん解き、その解の表から、ひとつずつ問題を解く、というもの。最終的に、解きたい大きさの問題が解ける

サブセットサム問題 • 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 となるものはあるか？

分枝限定法で解く 最後の 23 を取り除く 問題0： 15, 24, 65, 32, 4, 55, 54 合計 145 はある？ • 要素 an から順番に、使う／使わないを決め、問題を分割し、再帰的に解く 　　　最後の 23 を取り除く 問題0：　15, 24, 65, 32, 4, 55, 54 　　　　　合計 145　はある？ 問題1：　15, 24, 65, 32, 4, 55, 54 　　　　　合計 122　はある？ 　　　同様に 問題00：　15, 24, 65, 32, 4, 55 　　　　　合計 145　はある？ 問題01：　15, 24, 65, 32, 4, 55 　　　　　合計 91　はある？ 問題10：　15, 24, 65, 32, 4, 55 　　　　　合計 122　はある？ 問題11：　15, 24, 65, 32, 4, 55 　　　　　合計 68　はある？

分枝限定法で解く (2) • 問題11111： 15, 24, 65 合計 -23 となるものはあるか？ • 問題11111：　15, 24, 65 　　　　合計 -23 となるものはあるか？ • 問題000：　15, 24, 65, 32, 4 　　合計 145　はとなるものはあるか？ • こういった明らかに実行不能な問題は、すぐに答えが分かる 最悪で O(2n) 時間かかる

すべてのb についての答えの表を作れればよい 動的計画法 アイディア： • 0 から b までの全ての数について、合計がその数になる組合せがあるかどうかを調べ、表を作る • anを取り除いた問題で、組合せてできる数を全て調べる  元の問題で組合せてできる数は、 　これらに anを加えた／加えないもの １つ数を取り除き、小さくした問題の、 すべてのb についての答えの表を作れればよい

アルゴリズム • f( i, m ) ： a1 ,…, ai の組合せで、和が m となるものがあれば1、そうでなければ 0 • i = 1,…,n に対して、以下の操作を実行する。 全ての 0 ≦m≦ b に対して、 f( i, m ) を計算する • f(i,m) = 1 f(i-1,m) =1 または f(i-1,m-ai) =1 • f(i,m) = 0 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) 時間 n = 30 ⇒ 2n ≒ 10億

ウィークポイント • 数に小数があるときは、表に当てはまらない数が出てくる  ある程度の桁数までなら、小数点以下の数を 　 ある程度の桁数までなら、小数点以下の数を 　　　１単位とした表を作ればよい • それでも、循環小数・無理数のような数があると計算できない

誤差が n（ε－１） の範囲のものしか見つけられないが メモリを省略 • サブセットサム問題を解く動的計画法は、b が大きいと、大きなメモリと時間を消費する • 精度を犠牲にして、メモリと時間を節約する方法がある • 表のマスを、縦 ε個ずつまとめる 　  縦のマスの数は ｂ／ε個に減る • (x,y) のマスに書き込む代わりに、 (x, Ｌy／ε」) に書き込む 　  エラーが最大 ε－１ 発生 　  n 反復繰り返すと、エラーの最大は n（ε－１） 誤差が n（ε－１） の範囲のものしか見つけられないが メモリと時間は １／εにできる

サブセットサムの解の数 • 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 問題である

動的計画の拡張 max. Σ cj xj s.t. Σ aj xj = m x1,…, xi ∈ { 0,1 } max. Σ cj xj • f(i,m) ：　荷物 1,…,i の組合せで、重さの和が m となるものの中での、 価値の和の最大値 max. Σ cj xj s.t. Σ aj xj = m x1,…, xi ∈ { 0,1 } • f( i, m ) = max { f( i-1, m ), f( i-1, m-ai ) + ci } • f(1,m) は簡単に計算できる 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 } 計算時間は 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 に、２つ目のグループの合計が b2 になるようなものはあるか？ • この問題を解くための動的計画法を設計しなさい 問題の例）15, 24, 65, 32, 4, 55, 54, 23 を１番目、２番目のグループの合計が 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)

パスの数 • 有向サイクルを含まないような、非閉路的グラフの、２点間を結ぶ有向パスの数を計算する

グラフの直線的な構造を利用 • 非閉路的なので、グラフの頂点に終点から始点方向に、終点に近いほうが必ず小さくなるような番号付けができる 　（自分から行ける頂点は自分よりも小さい） • この順番でスキャンすることで、表を作ることはできないが、 数が数えられる ３ ６ ５ ７ ２ ９ ０ ４ ８ １

番号順にパスの数を数える • グラフが非閉路的なので、頂点 v から終点へのパスの数は、v からいける頂点から終点までのパスの数の総和 　 番号順に、パスの数を計算すればよい １＋２ １１＋３ ２＋３＋６ １４＋３３＋４０ ３ ３ １＋１ １４ ６ ５ １１ ７ ３３ ２ ２ ９ ８７ ０ １ ４ ６ ８ ４０ １４＋１１＋２＋６ １ １ １＋２＋３ ３３＋６＋１

まとめ • 組合せ最適化問題に対する動的計画法の作り方 （漸化式を作れれば良い） • サブセットサム・その変形・ナップサック問題・最長部分昇順列・非閉路的グラフの2点間を結ぶパスの数、に対する動的計画法