Document

列挙問題
•
•
•
•
•
列挙問題の定義
アルゴリズムの速度
バックトラッキング
分割法
逆探索
列挙問題の定義
列挙問題
与えられた集合の要素（あるいは問題の解）を全て、ちょうど１
度ずつ出力せよ
例）
• 与えられたグラフの、頂点 s から頂点 t までのパスを列挙せよ
• ナップサック問題の実行可能解を列挙せよ
列挙問題を解くアルゴリズム  列挙アルゴリズム
なぜ列挙したいかというと
• 最適化問題  最適な解をひとつだけ見つける
問題（システム）のある種の極みの状態がわかる
しかし、
• データの不備、目的関数のあいまいさがあると、最適解が必ず
しも良いとは限らない
• サンプリング、データ検索などでは、ひとつだけでは困る、見つ
けそこないがあると困ることがある
• それはそれとして、同じものが何回も出てきては困る
• 解を全部見つけると言うことは、問題全体の構造を捉えること
条件を満たす全ての解を列挙したい
データ中心の科学
• 近年、IT技術の発達で、大規模なデータが半自動的に収集でき
るようになった
（POS、web、文書、顧客データ、財務、利用者、人事…）
データがそろっているところでモデルを作って研究しよう
データの選別
モデル化
データ処理
いわば、データを出発点とした問題解決の科学
（人工知能、データマイニング、自然言語処理、セマンティックweb…）
OR的アプローチのボトルネック
典型的なOR的なアプローチは、データ収集でつまづくことが多い
典型的な OR（＋数理計画）的アプローチ
問題発見
定式化
解法（最適化）
できたモデルを実際に使う
データ収集
（システム構築）
ここがボトルネック
であることが多い
求解
運用
データ中心のアプローチな
ら、この問題が解決できる
データの不備、目的のあいまいさ
• データ中心科学では、処理の目的があいまいなことが多い
• データに、不備・不正確・丁寧さ乱雑さなどのゆらぎがある
例） web ページの検索
目的は、「見つけたいページを見つける」であるが、見つけたい
ページとは何であろうか？
 答えがあることは明白だが、各解の評価尺度を作るのが困難
 データの情報を正確に信じることも難しい
Web ページ
データベース
？
Enumerations
from databases
solve many
problems and
give new
knowledge
見つけたい
ページ
２段階の問題解決
• 候補の提示と絞込みによる解決
① キーワードを指定
② キーワードを含むページを列挙
③ 見つかったページを実際に検証
見つけたい
ページ
候補
Web ページ
データベース
キーワード検索
Enumerations
from databases
solve many
problems and
Enumerations
give new
from databases
knowledge
Enumerations
solve many
Enumerations
from
databases
problems and
from
databases
solve
many
give new
solve
many
problems
and
knowledge
problems andgive new
give new knowledge
knowledge
Enumerations
from databases
solve many
problems and
give new
knowledge
実際にページ
を見て検証
• 数理的にはっきりとした部分をコンピュータで解く（候補列挙）
• 残りはユーザに任せる（候補の絞込み）
列挙の難しさ：適当に見つけると
• 適当に実行可能解を見つける、という作業を繰り返す
• 見つけそこないがあるか、確認できない
• 同じ解を出力しないようにするためには、メモリに今まで出力
した解を蓄えておく必要がある
• 変数が n 個ある組合せ最適化問題
 実行可能解は、最高 2n 個
 最悪で、メモリを O(2n ) 使う
1つの解が1バイトしか使わないとして
• n ＝ 30 程度で1GB くらい
• n ＝ 40 程度で1000GB くらい
• こんなにたくさんのメモリは用意できない
しらみつぶしに探しましょう
• しらみつぶしに組合せを調べればいいんじゃない？
• 変数が n 個ある組合せ最適化問題
 組合せは 2n 個
 全て調べると、 O(2n ) 時間かかる
• n ＝ 30 程度で1時間くらいかかる
• n ＝ 50 程度で100年くらい
• 例えば、実行可能解が数千個しかないのに、こんなに時間
がかかっていては困る
出力の数で時間を計る
• 列挙問題は解がたくさんあるので、解が多ければそれだけ
時間がかかるのはしょうがない
• でも、解が少なければ、早く終わってほしい
• 問題が与えられれば、その解の数Nは決まるので、N に対
して短時間なアルゴリズムがほしい
あるアルゴリズムの計算時間が、
入力の大きさ n と出力する解の数 N のみに依存する多項
式であるとき、出力多項式時間である、という
任意の解の次の解を出力するまでの時間が入力の大きさ n
の多項式であるとき、多項式時間遅延である、という
列挙アルゴリズムの作成手法
• 比較的、基礎的な問題なので、アルゴリズム作成手法も単純
• しかし、逆に言うと、バリエーションが少ない
－バックトラック法
深さ優先的＋辞書順の優先度で隣接関係を探索
－分割法
分枝限定法のように、問題を再帰的に分割する
－逆探索
親子関係という隣接性から得られる探索路を進む
バックトラック法
• あるいはバックトラッキングと呼ばれる
• 主に、単調な集合族の要素の列挙、あるいはその極大要素の
列挙に使われる
• 単調な集合族 F： X∈F  任意の X'⊆X に対して X'∈F
（ X∈F  Xの任意の部分集合は F に含まれる）
• 単調な集合族の例）
－グラフのクリーク
－ナップサック問題の実行可能解
－マッチングの集合
111…1
だめな例）パスの集合、サイクルの集合,…
000…0
バックトラック法 (2)
• 空集合から出発し、各反復で要素を１つずつ付け加えてい
き、再帰的に解を作る
1,2,3,4
• ただし、加える要素は、
集合中の最大添え字より
大きいもののみ
• 付け加えたものが解にならない
なら、引き返す（バックトラック）
1,2,3
1,2
1,2,4
1,3
1
1,3,4
1,4
2,3,4
2,3
2,4
2
3
φ
• すべての要素を付け
加え終えたら、反復終了
3,4
4
バックトラック法 (3)
• 空集合から出発し、各反復で集合中の最大添え字より
大きい添え字の要素を加える
1,2,3,4
Backtrack (S)
1,2,3
1 Output S
2 For each e > S の末尾
1,2
（S の最大添え字の要素）
If S ∪{e}が解 then
call Backtrack (S ∪{e})
1,2,4
1,3
1
• 仕組みが単純、多項式空間
• 多項式時間遅延（出力多項式時間）
1,3,4
1,4
2,3,4
2,3
2,4
2
3
φ
3,4
4
バックトラックでナップサック問題の解列挙
問題： 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)
ナップサック解列挙のコード
• 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]);
}
}
}
極大解に注目
• 単調な集合族は、台集合or要素の平均の大きさが大きくなると、爆
発的に要素数が大きくなる
• 解数が大きいと、求解後の処理も大変
 極大解のみを列挙することで冗長性をなくす
X∈F が F の極大解  任意の X⊆X’ に対して X’∈Fでない
• 極大解は、一般に隣接して
いないので、探索が難しい
111…1
000…0
ナップサック問題の極大解列挙
問題： a1,…,an の組合せで合計が b 以下のものの中で、極大なも
のを全て見つけよ
• a1,…,an をあらかじめ大きい順にソートしておく
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(n)
 解1つあたり O(n)
分割法
• 実行可能解集合X :
F の要素で性質 P を満たすもの
• X の要素が1つだけならば、それを出力して
反復終了
• F を分割して、 X を空でない２つの集合に分割
• 再帰的に列挙
例）
－グラフの頂点 s から頂点 t へのパス
－２部グラフのマッチング
F1
X1
F
F2
X
X2
分割法アルゴリズムの例
問題：グラフ G=(V,E) の頂点 s から頂点 t へのパスを列挙
問題の分割： s に接する辺 e をひとつ選び、
e を含むパスを列挙する問題と、
e を含まないパスを列挙する問題に分割する
ただし、 e を含むパス、含まないパスが存在すること
子問題：
e を含むパスを列挙： G から、e 以外の s に接続する枝を除去
e を含まないパスを列挙： G から e を除去
計算時間：
1反復 O(|E|)
 パス1つあたり O(|E|)
コード
• 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 にする
}
}
分割法の計算時間
• 実行可能解の集合を X 、その個数を N とする
• 分割法の各反復は、 X を細かい集合に分けていく
（1反復で、ある集合が2つに分かれる）
か、解を1つ出力する
• 反復の個数は、高々 2N-1
• 反復の計算時間は、通常入力の多項式
• 多項式時間遅延（出力多項式時間）
• 入力多項式空間
逆探索
• いくつかの解を除く全ての解に親を定義。ただし、
★ 任意の解は自分自身の先祖にならないこと
• 親子関係から木（林）を導出
• 導出した木を深さ優先探索する
反復数は出力数と等しくなる
計算時間は、解1つあたり1反復の計算時間
逆探索 (2)
• 導出した木を深さ優先探索する
 木の全体をメモリに格納する必要はない
• 与えられた解の子供を列挙するアルゴリズムがあれば十分
• 欲を言えば、i 番目の子供を与えると、 i+1 番目の子供を返す
関数があればよい（木の深さが指数でも多項式時間遅延）
メモリは、子供を見つけるのにかかるメモリ分必要
通常、入力の多項式
逆探索アルゴリズムの例
問題： n変数m等式の線形計画問題の、実行可能辞書を列挙
親の定義：単体法 S と目的関数 c を適当に選び、
各辞書 x に対して、 S によるピボットで移動する辞書を
x の親とする
子供の見つけ方：
辞書 x に対して、ピボットにより移動可能な辞書を、
添え字順で発生。得られた各辞書について、
その親を作り、x の子供であるか、チェックする
計算時間：
全て可能なピボット： nm 個 × ピボット n2+m ＝ O(n3m+nm2)
まとめ
• 列挙問題の定義
• アルゴリズムの速度：出力多項式時間
• バックトラック：ナップサックの実行可能解
• 分割法：グラフのパス
• 逆探索：線形計画の実行可能辞書

Download Report