Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "動的計画法 表の作成 制約の追加 練習問題."— Presentation transcript:

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

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

3 サブセットサム問題 ・ n 個の数(a1,…,an)がある。これらの数の組合せで、合計がちょうど b になるようなものがあるか?
例題) 15, 24, 65, 32, 4, 55, 54, 23       の組合せで合計が 145 となるものはあるか?

4 サブセットサム問題 (2) ・ n 番目の数だけ取り除いた問題を考える ・ 元の問題に合計 b の組合せがある
  取り除いた問題で合計 b か b - an の組合せがある 例題) 15, 24, 65, 32, 4, 55, 54, 23       の組合せで合計が 145 となるものはあるか?  15, 24, 65, 32, 4, 55, 54       の組合せで合計が 145 か 122 となるものはあるか?

5 分枝限定法で解く 最後の 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 はある?

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

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

8 アルゴリズム ・ f( i, m ) : a1 ,…, ai の組合せで、和が m となるものがあれば1、そうでなければ 0
・ i = 1,…,n に対して、以下の操作を実行する。 全ての 0 ≦m≦ b に対して、 f( i, m ) を計算する ・ f(i,m) = f(i-1,m) =1 または f(i-1,m-ai) =1 ・ f(i,m) = f(i-1,m) =0 かつ f(i-1,m-ai) =0 ・ f(1,m) は簡単に計算できる 計算時間は O(nb)

9 動的計画法コード ・ 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;

10 もっと短いやつ ・ 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] );

11 どっちが速い? ・ 分枝限定法 : O(2n) 時間 ・ 動的計画法 : O(nb) 時間
n = 30 ⇒ 2n ≒ 10億

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

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

14 サブセットサムの解の数 ・ n 個の数(a1,…,an)がある。これらの数の組合せで、合計がちょうど b になるようなものは、いくつあるか?
・ 15, 24, 65, 32, 4, 55, 54, 23         の組合せで合計 145 となるものはいくつ?

15 動的計画の拡張 ・ 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)

16 練習問題 ・ 1,1,2,3,3,4,5,7 の組合せで、         合計 10 となる組合せはいくつあるか?

17 ちょうど k 個の和 ・ n 個の数(a1,…,an)がある。これらの数のk個の組合せで、合計がちょうど b になるようなものは、いくつあるか? 例) 15, 24, 65, 32, 4, 55, 54, 23 の中の 4個の数の組合せで         合計 145 となる組合せはいくつ?

18 動的計画の拡張 ・ 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)

19 ナップサック問題 ・最大積載量のあるナップサックに荷物を詰める問題 - 荷物はいくつかある - 荷物はそれぞれ重さが違う
 - 荷物はいくつかある  - 荷物はそれぞれ重さが違う  - 荷物はそれぞれ価値が違う  - 荷物の重さの合計は、最大積載量を超えてはいけない このとき、荷物の価値の合計が最大になる詰め込み方を求めよ

20 ナップサック問題 (2) ・ 荷物 i の重さを ai 、価値を ci 、ナップサックの最大積載量を b とすると、定式化は
max. Σ ci xi s.t. Σ ai xi ≦ b xi ∈ { 0,1 } ・ NP-hard 問題である

21 動的計画の拡張 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, k ), 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)

22 ナップサック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 );

23 練習問題 ・ n 個の数(a1,…,an)がある。これらの数を3つのグループに分け、 1つ目のグループの合計が b1 に、2つ目のグループの合計が b2 になるようなものはあるか? ・ この問題を解くための動的計画法を設計しなさい 問題の例)15, 24, 65, 32, 4, 55, 54, 23 を1番目、2番目のグループの合計が 120,110 とするようななる分け方はあるか?

24 直線構造の利用 ・ 動的計画法のキモは、大きさが小さい問題の解を用いて、現在の問題が解けるかどうか。
・ 言い方を変えれば、左から右に問題を解いていったときに、自分の答えが、自分の左だけを見て作れるか ・ これは、ある種の直線構造があるかどうか、と考えていいだろう (現時点の右側を変更しても、左側に影響がない、あるいは影響が簡単なパラメータになる(重みの合計とか、組合せ的でない)) ・ つまり、直線構造があれば動的計画を使えばいいし、動的計画を使えるかどうかは、直線構造があるかないか (有向非閉路的グラフとか、木も直線構造)

25 最長昇順列 ・ 与えられた数列の中で、小さい順になっている部分列を昇順部分列と言う
・例: 1,5,4,7,2,5,3,9,6,8  1,2,6 など ・ 与えられた数列の中から、最も長い昇順列を見つける問題を最長昇順列問題という ・ この問題は直線構造がある

26 直線構造はあるか ・ i 番目の数 ai が最後となるような昇順列を考える
・ このような昇順列の後ろに何を追加しても、前半部分が昇順列でなくなることはない ・ つまり、もし、ai が最適解に含まれるなら、前半部分(ai より小さな添え字を持つ数)が作る昇順列は、そのようなものの中で最長になっているはず  このあたりが直線構造

27 直線構造はあるか ・ 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)

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

29 グラフの直線的な構造を利用 ・ 非閉路的なので、グラフの頂点に終点から始点方向に、終点に近いほうが必ず小さくなるような番号付けができる
 (自分から行ける頂点は自分よりも小さい) ・ この順番でスキャンすることで、表を作ることはできないが、 数が数えられる

30 番号順にパスの数を数える ・ グラフが非閉路的なので、頂点 v から終点へのパスの数は、v からいける頂点から終点までのパスの数の総和
  番号順に、パスの数を計算すればよい 1+2 11+3 2+3+6 14+33+40 1+1 14 11 33 87 40 14+11+2+6 1+2+3 33+6+1

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


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

Similar presentations


Ads by Google