列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索.

Presentation on theme: "列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索."— Presentation transcript:

1 列挙問題 列挙問題の定義 アルゴリズムの速度 バックトラッキング 分割法 逆探索

2 列挙問題の定義 列挙問題 与えられた集合の要素（あるいは問題の解）を全て、ちょうど１度ずつ出力せよ 例）
　与えられた集合の要素（あるいは問題の解）を全て、ちょうど１度ずつ出力せよ 例） 　・ 与えられたグラフの、頂点 s から頂点 t までのパスを列挙せよ 　・ ナップサック問題の実行可能解を列挙せよ 列挙問題を解くアルゴリズム  列挙アルゴリズム

3 なぜ列挙したいかというと ・ 最適化問題  最適な解をひとつだけ見つける 問題（システム）のある種の極みの状態がわかる しかし、
・ 最適化問題　  最適な解をひとつだけ見つける 　問題（システム）のある種の極みの状態がわかる しかし、 ・ データの不備、目的関数のあいまいさがあると、最適解が必ずしも良いとは限らない ・ サンプリング、データ検索などでは、ひとつだけでは困る、見つけそこないがあると困ることがある ・ それはそれとして、同じものが何回も出てきては困る ・解を全部見つけると言うことは、問題全体の構造を捉えること 条件を満たす全ての解を列挙したい

4 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった （POS、web、文書、顧客データ、財務、利用者、人事…）
データ中心の科学 ・ 近年、IT技術の発達で、大規模なデータが半自動的に収集できるようになった 　　（POS、web、文書、顧客データ、財務、利用者、人事…） データがそろっているところでモデルを作って研究しよう データの選別 モデル化 データ処理 いわば、データを出発点とした問題解決の科学 （人工知能、データマイニング、自然言語処理、セマンティックweb…）

5 典型的なOR的なアプローチは、データ収集でつまづくことが多い
問題発見 定式化 解法（最適化） 典型的な OR（＋数理計画） 的アプローチ データ収集 （システム構築） 求解 運用 できたモデルを実際に使う ここがボトルネック であることが多い データ中心のアプローチなら、この問題が解決できる

6 Enumerations from databases solve many problems and give new knowledge
データの不備、目的のあいまいさ ・ データ中心科学では、処理の目的があいまいなことが多い ・ データに、不備・不正確・丁寧さ乱雑さなどのゆらぎがある 例） web ページの検索　 目的は、「見つけたいページを見つける」であるが、見つけたいページとは何であろうか？  答えがあることは明白だが、各解の評価尺度を作るのが困難  データの情報を正確に信じることも難しい 小さいデータではできることが、大きなデータではぜんぜんできない 例1：データを眺めて、特徴を得ること 例2： web検索、最近の話題を知りたい Enumerations from databases solve many problems and give new knowledge Web ページ データベース ？ 見つけたいページ

7 ・ 候補の提示と絞込みによる解決 ① キーワードを指定 ② キーワードを含むページを列挙 ③ 見つかったページを実際に検証
２段階の問題解決 ・ 候補の提示と絞込みによる解決 　① キーワードを指定 　② キーワードを含むページを列挙 　③ 見つかったページを実際に検証 見つけたいページ Enumerations from databases solve many problems and give new knowledge キーワード検索 候補 Enumerations from databases solve many problems and give new knowledge 実際にページ を見て検証 Web ページ データベース 小さいデータではできることが、大きなデータではぜんぜんできない 例1：データを眺めて、特徴を得ること 例2： web検索、最近の話題を知りたい ・ 数理的にはっきりとした部分をコンピュータで解く　（候補列挙） ・ 残りはユーザに任せる　（候補の絞込み）

8 列挙の難しさ：適当に見つけると  実行可能解は、最高 2n 個  最悪で、メモリを O(2n ) 使う
・ 適当に実行可能解を見つける、という作業を繰り返す ・ 見つけそこないがあるか、確認できない ・ 同じ解を出力しないようにするためには、メモリに今まで出力した解を蓄えておく必要がある ・ 変数が n 個ある組合せ最適化問題 　  実行可能解は、最高 2n 個 　  最悪で、メモリを O(2n ) 使う 1つの解が1バイトしか使わないとして ・ n ＝ 30 程度で1GB くらい ・ n ＝ 40 程度で1000GB くらい ・ こんなにたくさんのメモリは用意できない

9 しらみつぶしに探しましょう ・ しらみつぶしに組合せを調べればいいんじゃない？ ・ 変数が n 個ある組合せ最適化問題
・ しらみつぶしに組合せを調べればいいんじゃない？ ・ 変数が n 個ある組合せ最適化問題 　  組合せは 2n 個 　  全て調べると、 O(2n ) 時間かかる ・ n ＝ 30 程度で1時間くらいかかる ・ n ＝ 50 程度で100年くらい ・ 例えば、実行可能解が数千個しかないのに、こんなに時間がかかっていては困る

10 出力の数で時間を計る ・ 列挙問題は解がたくさんあるので、解が多ければそれだけ時間がかかるのはしょうがない
・ でも、解が少なければ、早く終わってほしい ・ 問題が与えられれば、その解の数Nは決まるので、N に対して短時間なアルゴリズムがほしい あるアルゴリズムの計算時間が、 入力の大きさ n と出力する解の数 N のみに依存する多項式であるとき、出力多項式時間である、という 任意の解の次の解を出力するまでの時間が入力の大きさ nの多項式であるとき、多項式時間遅延である、という

11 列挙アルゴリズムの作成手法 ・ 比較的、基礎的な問題であるので、アルゴリズム作成手法も単純 ・ しかし、逆に言うと、バリエーションが少ない
　 － バックトラック法 　　　　　深さ優先的＋辞書順の優先度で隣接関係を探索 　 － 分割法 　　　　　分枝限定法のように、問題を再帰的に分割する 　 － 逆探索 　　　　　親子関係という隣接性から得られる探索路を進む

12 バックトラック法 ・ あるいはバックトラッキングと呼ばれる ・ 主に、単調な集合族の要素の列挙、あるいはその極大要素の列挙に使われる
・ 単調な集合族 F： 　X∈F 　  任意の X'⊆X に対して X'∈F 　　　　　（ X∈F 　 Xの任意の部分集合は F に含まれる） ・ 単調な集合族の例） 　－ グラフのクリーク 　－ ナップサック問題の実行可能解 　－ マッチングの集合 　－ ある頂点を始点とするパスの集合 111…1 000…0

13 バックトラック法 (2) ・ 空集合から出発し、各反復で要素を１つずつ付け加えていき、再帰的に解を作る ・ ただし、加える要素は、
　集合中の最大添え字より 　大きいもののみ ・ 付け加えたものが解にならない なら、引き返す（バックトラック） ・ すべての要素を付け 　加え終えたら、反復終了 φ 1,3 1,2 1,2,3 1,2,4 1,3,4 2,3,4 1 2 3 4 3,4 2,4 1,4 2,3 1,2,3,4

14 バックトラック法 (3) ・ 空集合から出発し、各反復で集合中の最大添え字より 大きい添え字の要素を加える Backtrack (S)
　大きい添え字の要素を加える Backtrack　(S) 1 Output S 2 For each e > S の末尾 　　　（S の最大添え字の要素） If S ∪{e}が解 then call Backtrack (S ∪{e}) 1,2,3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2 1,3 1,4 2,3 2,4 3,4 1 2 3 4 φ ・仕組みが単純、多項式空間 ・多項式時間遅延　（出力多項式時間）

15 バックトラックでナップサック問題の解列挙
問題： a1,…,an の組合せで、合計が b 以下のものを全て見つけよ Backtrack　(S) 1 Output S 2 For each i > S の末尾（S の最大添え字の要素） If ∑S ＋ ai ≦b then call Backtrack (S ∪{ai}) 計算時間： 　1反復 O(n) 　  　解1つあたり　 O(n) a1,…,an をあらかじめ大きい順にソートしておくと、 　1反復 O(子どもの数) 　  　解1つあたり　 O(1)

16 ナップサック解列挙のコード ・ a[0],…,a[n] の組合せで、合計が b 以下になるものを表示 int a[n], flag[n];
sub (int i, int s){ int j; for (j=0 ; j<n ; j++ ) if (flag[j] = = 1) printf (“%d\n”, a[j]); // 数の表示 for (j=i+1 ; j<n ; j++ ){ if ( s+a[j] <= b ){ // 解のチェック flag[j] = 1; sub(i, s+a[j]); }

17 極大解に注目 ・ 単調な集合族は、台集合or要素の平均の大きさが大きくなると、爆発的に要素数が大きくなる
・ 解数が大きいと、求解後の処理も大変  極大解のみを列挙することで冗長性をなくす 　X∈F が F の極大解  任意の X⊆X’ に対して X’∈Fでない ・ 極大解は、一般に隣接して いないので、探索が難しい 111…1 000…0

18 ナップサック問題の極大解列挙 問題： a1,…,an の組合せで合計が b 以下のものの中で、極大なものを全て見つけよ
Backtrack　(S) 1 Output S 2 For each i > S の末尾（S の最大添え字の要素） and ∑S ＋ ai ＋…+ an > b – ai-1 If ∑S ＋ ai ≦b then call Backtrack (S ∪{ai}) 計算時間： 　1反復 O(子どもの数) 　  　解1つあたり　 O(n)

19 分枝限定法的バックトラック ・ 任意の組合せ最適化問題の実行可能解を全探索的に探索 各反復で ・ 現在解が実行可能なら出力
各反復で　・ 現在解が実行可能なら出力 　　　　　　　・末尾より大きな各要素について、それを加えた解 　　　　　　　　が存在する可能性があるなら、再帰呼び出し Backtrack (S) 1 If S が実行可能 Output S 2 For each e > S の末尾 　If S に e 以降の要素を加えた解が存在する可能性がある then call Backtrack (S ∪{e}) ・仕組みが単純、多項式空間 ・出力多項式時間になるとは限らない

20 分割法 F1 X1 ・ 実行可能解集合X : F の要素で 性質 P を満たすもの ・ X の要素が1つだけならば、それを出力して 反復終了
　　　反復終了 ・ F を分割して、 X を空でない２つの集合に分割 ・ 再帰的に列挙 例） 　－ グラフの頂点 s から頂点 t へのパス 　－ ２部グラフのマッチング F X F2　　　X2

21 分割法アルゴリズムの例 問題： グラフ G=(V,E) の頂点 s から頂点 t へのパスを列挙
問題の分割： s に接する辺 e をひとつ選び、 　e を含むパスを列挙する問題と、 　e を含まないパスを列挙する問題に分割する ただし、 e を含むパス、含まないパスが存在すること 子問題： 　e を含むパスを列挙：　G から、e 以外の e に接する枝を除去 　e を含むパスを列挙：　G から e を除去 計算時間： 　1反復 O(|E|) 　  　パス1つあたり　 O(|E|)

22 コード ・ flag は最初全て 0、path に構築中のパスが入る
・ deg[v] は vの次数、edge[v] はv に隣接する頂点の配列 int flag[n], path[n]; enum_path (int s, int t, int i){ int j; if ( s = = t ){ path[0] から path[i] を出力 } else { flag[s] =1; path[i] = s; ・t から flag[]= = 0 である頂点のみを通って到達可能な頂点の flag を2 にする ・s に隣接して、flagが0 である頂点のflagを -1-s にする ・t から flag[]= = 2 である頂点のみを通って到達可能な頂点の flag を0 にする for ( j=0 ; j<deg[s] ; j++){ if (flag[edge[i][j]] = = 0 ) enum_path( edge[i][j], t, i+1); // t に到達可能な頂点のみに対して再帰呼び出し } ・s に隣接して、flagが-1-s である頂点のflagを 0 にする

23 分割法の計算時間 ・実行可能解の集合を X 、その個数を N とする ・ 分割法の各反復は、 X を細かい集合に分けていく
　　（1反復で、ある集合が2つに分かれる） 　か、解を1つ出力する ・ 反復の個数は、高々 2N-1 ・ 反復の計算時間は、通常入力の多項式 ・ 多項式時間遅延　（出力多項式時間） 　 ・ 入力多項式空間

24 逆探索 ・ いくつかの解を除く全ての解に親を定義。ただし、 ★ 任意の解は自分自身の先祖にならないこと ・ 親子関係から木（林）を導出
　　　 ★ 任意の解は自分自身の先祖にならないこと ・ 親子関係から木（林）を導出 ・ 導出した木を深さ優先探索する 反復数は出力数と等しくなる 計算時間は、解1つあたり1反復の計算時間

25 逆探索 (2) ・ 導出した木を深さ優先探索する  木の全体をメモリに格納する必要はない
　　 木の全体をメモリに格納する必要はない ・ 与えられた解の子供を列挙するアルゴリズムがあれば十分 ・ 欲を言えば、i 番目の子供を与えると、 i+1 番目の子供を返す関数があればよい（木の深さが指数でも多項式時間遅延） メモリは、子供を見つけるのにかかるメモリ分必要 通常、入力の多項式

26 逆探索アルゴリズムの例 問題： n変数m等式の線形計画問題の、実行可能辞書を列挙 親の定義： 単体法 S と目的関数 c を適当に選び、
　各辞書 x に対して、 S によるピボットで移動する辞書を 　　x の親とする 子供の見つけ方： 　辞書 x に対して、 ピボットにより移動可能な辞書を、 　添え字順で発生。得られた各辞書について、 　その親を作り、x の子供であるか、チェックする 計算時間： 　全て可能なピボット： nm 個 × ピボット n2+m　＝　O(n3m+nm2)

27 まとめ ・ 列挙問題の定義 ・ アルゴリズムの速度： 出力多項式時間 ・ バックトラック： ナップサックの実行可能解
・ アルゴリズムの速度：　出力多項式時間 ・ バックトラック：　ナップサックの実行可能解 ・ 分割法：　　グラフのパス ・ 逆探索：　　線形計画の実行可能辞書