列挙アルゴリズムの
遅延時間減少法
宇野 毅明
国立情報学研究所
2002年3月 東北大大学院
情報科学研究科ワークショップ
列挙と発生
列挙・発生:
与えられた集合の要素を全て出力する問題
・列挙という言葉は, 比較的複雑な問題, アルゴリズムに用
いられるようだ
マッチング・全張木・多面体の頂点・幾何学図形など
・発生という言葉は, 比較的単純な問題, アルゴリズムに用
いられるようだ
2分木・順列・文字列など
どのような研究がされているか
比較的難しい問題(列挙)
・出力多項式時間のアルゴリズムが存在するか
・単純な仕組み・きれいな枠組みで系統立てできるか
・計算量の減少ができるか
比較的易しい問題(発生)
・計算量は減少できるか, 解1つあたり定数時間になるか
・遅延時間(2つの出力間の最大計算時間)はどのくらいか
・2つの出力間の差分の最大はどれくらいか (出力変化量)
・出力に, 圧縮・ポインタなどを用いているか
アルゴリズム構築法
列挙: 分割法・逆探索・バックトラックなど
・問題に対して, 比較的簡単に, 多項式時間で列挙できるか
どうかがわかる
・遅延時間・出力変化量などは考慮しないので,
その意味では良いアルゴリズムにならない
発生: グレイコード, 木探索で葉を隣接させる方法など
・遅延時間・出力変化量が小さい
・簡単なアルゴリズムでも, この枠組みにのせるには
比較的手間がかかる
出力変化量を小さくするのは大変
逆探索・バックトラック・分割法
 アルゴリズムの再帰構造が木構造になる
(木探索型と呼ばれる)
(列挙木と呼ぶ)
 遅延時間・出力変化量に, 列挙木の高さが入ってくる
・探索の仕方を, 木ではなく, パスにする
・木の高さをそろえ, 葉をつなぐ
両者共に, 技巧的な工夫が必要
今回の研究の目的
列挙アルゴリズム構築法を用いた簡単なアルゴリズムを,
発生アルゴリズムでの評価基準(遅延時間・出力変化量)が
良くなるようにする,
簡単かつ一般的な改良法を2つ提案する
条件:
その1: 全ての反復で解を出力すること
その2: 任意の反復の子孫の平均計算時間が,
全体の平均計算時間のオーダーになっていること
結果:
出力変化量: 親反復と子反復の差の最大
遅延時間:
1反復の計算量, あるいは
解1つ当りの平均計算時間 (余分なメモリと初期時間を要す)
仮定を満たす列挙アルゴリズム
逆探索
・解集合に親子関係を定義
・親子関係から木を導出
・導出した木を深さ優先探索
分割法の1種
1. ある解 x を見つけ出力
2. x 以外の解 x’ を求め, 出力. なければ終了
3. 解集合を, x を含むものと x’ を含むものに分割し,
2. を再帰呼び出し
両者共に, すべての反復で解を出力
.
.
.
.
再帰のレベルごとに
出力のタイミングを変える
列挙木の各反復 x で,
・ x の深さが奇数ならば
再帰呼出しの前に解を出力する
・ x の深さが偶数ならば
再帰呼出しの後に解を出力する
・ 葉では必ず出力する
出力変化量・遅延時間の減少
深さ優先で列挙木をたどった部分パスを考える
部分パスが
・葉か, 長さ 3 の折り返さないパス
を含むと, 必ず出力が行われる
・折り返す場合も, 先頭か末尾で出力を行う
 3 反復に1つは出力が行われる
出力変化量・遅延時間 が, それぞれ
親反復と子反復の差× 3 , 3 反復の計算時間に減少
何に使えるか
木探索型のアルゴリズム
2分木, 高さが k の2分木
順列, multiset の順列, 禁止位置がある順列
禁則パターンを含まない文字列
などなど
逆に, 使えないもの
・ 葉でしか出力を行わないタイプのアルゴリズム
(極大安定集合, 平面の木, 3角形分割など)
・ 出力差分の最大が, 出力の大きさのオーダーのもの
(マッチング、パスなど)
例1:禁止位置がある順列(1)
順列 x = ( p1,…,pn ) で, それぞれの pi が添え字集合 P(i) に含
まれないものを列挙せよ, という問題の, 簡単なバージョンに対
するアルゴリズムを作ってみる
問題:
順列 x = ( p1,…,pn ) で, 任意の pi ≠ i であるものを列挙せよ
解が O( n! ) あるので, しらみつぶしに探索しても, 解1つあたり
の計算時間は O( 1 )
しかし, 出力変化量・遅延時間はその限りではない
例1:禁止位置がある順列(2)
アルゴリズム:
Iter ( 1, 2, ( 2,3,…,n,1 ) ) を呼び出す
2,3,4,5,6,7,8,1
3,2,4,5,6,7,8,1
4,3,2,5,6,7,8,1
5,3,4,2,6,7,8,1
6,3,4,5,2,7,8,1
Iter ( i, j, x = ( p1,…,pn ) )
If pj = i or pi = j then j = j+1
If j = n+1 or i = n then return
x’ = x の pi と pj を入れ替えて得られる順列
x’を出力
Iter ( i+1, i+2, x = ( p1,…,pn ) )
If j = n then Iter ( i+1, i+2, x = ( p1,…,pn ) )
else Iter ( i, j+1, x = ( p1,…,pn ) )
遅延時間の減少
先ほどの方法で, 遅延時間を1反復の最大計算時間のオー
ダーで押さえることができた
今度は, もう少し欲張って, 遅延時間を解1つ当りの平均計
算時間のオーダーで押さえる方法を考える
ただし, 下の条件を満たすこと
T : 1反復の平均計算時間のオーダー
任意の反復 x に対して, x の列挙木上の子孫で消費される
計算時間は, 1反復あたり T でおさえられる
キューを使う
出力をいったんキューに溜め, 一定間隔でキューから取り出
して出力する
・ 最初, Q がいっぱいになるまで出力を溜め続ける
・ 一回, いっぱいになったら, 以後 3T 時間経過するごとに
Q の先頭要素を出力する. 出力が頻繁に起こり, Q があふ
れた場合も, 先頭を出力する
・アルゴリズム終了後, Q に要素が残っていたら, 先頭から
順次出力する
アルゴリズム
T* : 列挙木の根と葉を結ぶパスに含まれる反復が消費する
合計計算時間の最大値
キュー Q の長さ : ( 6T* / 3T ) +1
アルゴリズム実行中, 時刻 t から時刻 t' まで
に少なくとも (t‘- t - 6T*) / 3T 個の解が Q に挿入される
解析
アルゴリズム実行中, 時刻 t から時刻 t‘ まで
に少なくとも (t‘- t - 6T*) / 3T 個の解が Q に挿入される
最初, Q がいっぱいになるまでの時間
(t – 0 - 6T*) / 3T = ( 6T* / 3T ) +1
 t = 12T* +3T = O(T*)
Qがあふれた時刻 t 以後の時刻に t‘ に対して,
(t‘- t - 6T*) / 3T + ( 6T* / 3T ) +1 ≧ (t’-t) / 3T
 Q が空になることはない
結果
T* : 列挙木の根と葉を結ぶパスに含まれる反復が消費する
合計計算時間の最大値
メモリ: 出力1回の大きさ × Q の長さ
= 出力1回の大きさ × O( 6T* / 3T )
解の出力が開始されるまでの時間:
= O( T* )
何に使えるか
ならし解析を用いているもの
グラフの全張木, 有向全張木, マッチング, 連結成分
有向非閉路グラフの s-t パス
マトロイドの基, 平面点集合の三角形分割
など
例2:マトロイドの基(1)
問題: 集合E 上で定義されたマトロイド M の基を全て出力せよ
アルゴリズム
Iter (M, B (基) )
基 B’ := B を求める
e1 := B \ B’ の要素
Iter ( M/e, B\e )
Iter ( M\e, B’ )
ただし、縮約したマトロイドに単一サーキットがある場合、
e を除去したマトロイドに、すべての基に含まれる要素がある場合
はそれらを用いて多数への分割をする
例2:マトロイドの基(2)
m = 台集合の大きさ、
n = マトロイドのランク
1反復の計算量: O( mn ×オラクルの計算時間 )
列挙木の深さ: O( m )
反復間の出力の差: O( 1 )
基1つあたりの平均計算時間: O( オラクルの計算時間 )
グラフ G=(V,E) のグラフィックマトロイド(全張木列挙)の場合、
もう少し速くなって、 1反復の計算量: O( |E| )
今回提案した方法を用いると、
出力変化量: O( 1 )
遅延時間:
O( 1 ) (メモリO( mn × m ×1 ) )
全張木の場合、 O( m × m ×1 )
まとめ
木探索型の列挙アルゴリズムに対して,
出力変化量・遅延時間を, 1反復あたりの最悪値まで減少さ
せる方法を提案した.
ならし解析を用いた木探索型の列挙アルゴリズムに対して
遅延時間を解1つあたりの平均計算時間まで減少させる方
法を提案した.
ダウンロード

+1 - 国立情報学研究所