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

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
4.3 マージソート.
配列の宣言 配列要素の初期値 配列の上限 メモリ領域 多次元配列 配列の応用
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
極小集合被覆を列挙する 実用的高速アルゴリズム
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
動的計画法 表の作成 制約の追加 練習問題.
第12回 ソート(3): シェルソート、クイックソート
プログラミング入門2 第4回 配列 for文 変数宣言 初期化
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
第11回 整列 ~ シェルソート,クイックソート ~
A: Attack the Moles 原案:高橋 / 解説:保坂.
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
組合せ最適化問題と厳密解法 最小木、ナップサック問題、ビンパッキング、巡回セールスマン問題 LPによる上界・下界 分枝限定法
On the Enumeration of Colored Trees
ファーストイヤー・セミナーⅡ 第8回 データの入力.
有効数字 有効数字の利用を考える.
プログラミング基礎I(再) 山元進.
Problem H ねこ鍋改造計画(仮) 秋葉 拓哉.
An Algorithm for Enumerating Maximal Matchings of a Graph
アルゴリズムイントロダクション第5章( ) 確率論的解析
アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015.
情報知能学科「アルゴリズムとデータ構造」
第10回 ソート(1):単純なソートアルゴリズム
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
 Combinations(2)        古川 勇輔.
第6章 2重ループ&配列 2重ループと配列をやります.
第11回 整列 ~ シェルソート,クイックソート ~
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
シャノンのスイッチングゲームにおけるペアリング戦略の複雑さについて
生命情報学入門 配列のつなぎ合わせと再編成
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
定兼邦彦 今井浩 東京大学理学系研究科 情報科学専攻
前回の練習問題.
第3回 アルゴリズムと計算量 2019/2/24.
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
25. Randomized Algorithms
First Course in Combinatorial Optimization
A Simple Algorithm for Generating Unordered Rooted Trees
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 探索と計算量.
プログラミング 4 木構造とヒープ.
ナップサック問題 クマさん人形をめぐる熱いドラマの結末.
列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
Data Clustering: A Review
重み付き投票ゲームにおける 投票力指数の計算の高速化
第16章 動的計画法 アルゴリズムイントロダクション.
短い部分文字列の ミスマッチトレランスを 高速計算するアルゴリズム
アルゴリズムとプログラミング (Algorithms and Programming)
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
プログラミング入門2 第5回 配列 for文 変数宣言 初期化
ヒープソート.
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
PROGRAMMING IN HASKELL
Cプログラミング演習 ニュートン法による方程式の求解.
参考:大きい要素の処理.
プログラミング入門2 第5回 配列 変数宣言、初期化について
プログラミング演習I 補講用課題
第1章 文字の表示と計算 printfと演算子をやります 第1章 文字の表示と計算.
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
アルゴリズム ~すべてのプログラムの基礎~.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

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

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

サブセットサム問題 • 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を加えた/加えないもの 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-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億

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

誤差が n(ε-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 問題である

動的計画の拡張 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 に、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 5 7 2 9 0 4 8 1

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

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