平面三角分割グラフを列挙する
アルゴリズムの改良
中野 眞一 ( 群馬大学 )
宇野 毅明 ( 情報学研究所 )
2002年6月24日
コンピューテーション研究会
列挙問題
列挙問題(発生):
与えられた集合の要素を全て、ちょうど1度ずつ出力する
問題
・総数を数えたり、サンプリングをしたり、性質を調べたりと
目的が多様
・アルゴリズムをツールとして考えると、いろいろな問題に対
して、ともかく速いアルゴリズムを作っておくと良い
列挙問題、例えば
グラフの
全張木・パス・閉路・マッチング・木
多面体の
頂点・面
平面の
三角形分割・アレンジメント
全ての
2分木・文字列・置換・順列・平面グラフ・連結グラフ
最適化問題の
最適解・極大解・実行可能解
2連結平面3角グラフ
平面グラフ:
枝が交差させずに平面埋込できるグラフ
3角グラフ:
全ての面が(外側の面を除いて)
三角形になる平面グラフ
2連結3角グラフ:
3角グラフで、カット頂点がないもの
根付き2連結3角グラフ:
2連結3角グラフの、外周上の辺の
1つが根に指定されているもの
2連結3角グラフ列挙の研究
根付き:
96 D. Avis
01 中野
一つあたり O( n2 )
一つあたり O( 1 )
根無し
98 B.D.McKay
01 中野
一つあたり O( n2 ) ?
一つあたり O( r2n )
今回:根無し
一つあたり O( r n )
01年のアルゴリズム(根付き)
逆探索: 列挙する対象間に親子関係を定義し、導出される
木を深さ優先探索して全ての要素を出力する方法
・ 頂点数 n のグラフの親を、頂点数が n-1 のグラフで定める
・ 頂点数3のグラフ(3角形)を根とする木になる
計算量
木の深さ優先探索にかかる時間を算定すればよい
・ ほとんどの内点は子供を2人以上持つ
 頂点数 ≦ 3 × 頂点数 n のグラフ数
・ 枝の移動 = O(1)
より、1つあたり O(1) 時間で列挙できる
根無しの列挙
・ 根付きではないものを列挙するには、
重複した出力をやめれば良い
・ 今までの出力を保存してチェック ・・・ × メモリ爆発
・ 根だけ違うグラフに順序を付け、最小のものだけ出力
グラフと根が与えられたときに、過去の出力を参照せずに、
そのグラフを出力するかどうかを決める必要がある
文字列を与える
中野01 では:
・ 根付きグラフに文字列を与える
(異なる根・グラフに異なる文字列)
・ 同じグラフの中で、最小文字列を与える根だけを出力
・ グラフが出てきたら、他の枝を根としたときの文字列を計
算し、自分が最小なら出力する
・ 対称なグラフは1度しか出力されないので、それらに関し
て異なる文字列を与える必要はない
計算時間
・ 1つのグラフ&根に対して、文字列を計算するのに O(n)
・ 全ての根に対して計算すると O(r n)
・ 1つのグラフは最大で r 回出力される
(1つ根無しグラフは、r 個それぞれの外周辺を根とした根
付きグラフになる)
つまり、1つの根無しグラフのために最大 r 回の計算
・ 結局、1つの根無しグラフあたり O(r2n)
高速化をしたい
・根付きの列挙が1つあたり O(1) であるのに対して、
根無しの列挙は1つあたり O(r2n)
根付きのほうが r 倍程度、総数が多いことを考慮しても、
少々遅いのではないか?
-- 是非高速化を行いたい
・ うまいアイディアが出てくれば、他の平面グラフオブジェク
ト(木とか2分木とか3角グラフとか)の列挙も高速化できる
かもしれない
今回の方針
・ 1つの根無しグラフのために最大 r 回の計算をしている、
というところは、手を付けない
・ 全ての根に対して文字列の計算をすると O(rn)、という、
ここを速くしてみよう
結果:
・ 異なる文字列を与える方法を考案した
・ 最小の文字列を与える根を O(n) 時間で求められる
(最小でない根の文字列の計算をさぼっている)
見方を変えると
今回扱う問題は、
-------------平面2連結グラフ  そのグラフの外周上の辺
という写像を設計したい
ただし、高速に求められないと意味がない
( O(r n) より速く )
---------------というものである
外周面 D0 を定義
・ 外周上の点に接する面(3角形)からなるグラフを D0 とする
・ D0を取り除いて残ったグラフを内部とする
※ 内部は、いくつかの2連結3角グラフになる
まず、3角形のタイプ分け
・ 取り除いた、それぞれの3角形を、全ての頂点が外周に
乗っているか、外周に乗っているか、内部と接しているか、な
どで10通りに分ける
それぞれのタイプに文字を割当てる
・ 外周に接する3角形に、最小の文字を割当てる
3角形にパラメータを与える
・ 2箇所以上の外周に接している面には、外周に再び自分
が現れるまでの
・ 頂点のみで接しているものには、辺をはさんで反対側の
三角形の頂点までの
(時計回りでの)外周の辺数をパラメータとして与える
文字列とパラメータが決まると、D0 の形は一通りに定まる
根に文字列を与える
各根に対して、その根(辺)からスタートして、
時計回り順に D0 の3角形の
(3角形のタイプ と パラメータ の組)
を並べた物を、根の (D0 に関する)文字列とする
内部の文字列を与える
内部の3角形が作るグラフについても、根に近い連結成分
から順に、根に最も近い辺を根として、同様に文字列を計算
し、再帰的に付け加えて、根の文字列を定義する
文字列とグラフ&根が対応
・グラフと根から、文字列が唯一的に決まる
・文字列を与えると、グラフと根が唯一的に決まる
2つの (グラフと根)に対して、
文字列が同じ  グラフと根が同型
文字列が異なる  グラフか根が異なる
辞書順で最小の根を探す
各根について、その根の文字を計算して、辞書順で最小の
ものを見つける
‥‥ O(r n)時間かかる
それぞれの根について、頭から1文字ずつ順に文字列を計
算していき、途中で辞書順最小ではなくなったものは、候補
から除去する
単純に計算すると
もしも比較をしている途中で文字列同士が重ならなければ、
計算時間はO( n )
文字列が重なってしまう(オーバーラップする)ときの計算時
間を省略する方法を考える
文字列の先頭に反復数を書く
文字列が取り除かれたとき、そのときの反復数を、文字の
先頭に書き込む
※ そこから、その文字数先までは辞書順で最小、ということ
を保障している
1
2
オーバーラップの処理1
・ 文字列同士がオーバーラップするときは、前の文字列の先頭
に後ろの文字列の末尾が重なる
・ 外周に接している3角形には、最小の文字を与えていたので、
この時点で重なっていない文字列は、候補から外れる
・文字列が鎖のように重なったときは、各文字列は、末尾の部分
まで、辞書順で最小になる
ABCDE ABCDE ABCDE ABCDE Z
○
×
×
×
オーバーラップの処理2
・ 重なった部分に数字 k が書かれている(消去された文字列)も
のは、 その k 文字先まで辞書順最小
・ 以上から、もっとも長くまで辞書順で最小のもののみが生き残
り、その他は候補からはずれる
※ (生き残りの長さをkとすると) k 文字先まで探索を省ける
5
ABCDE ABCDE Z
○
2
ABCDE AB Z
×
計算量
文字列に1文字付け加えると、
・ 文字がひとつ新たに探索される、か
・ 重なった場合には候補がひとつ消える
ので、根の文字列の中で D0 に関する部分で最小なものを
求めるのは、 D0 に含まれる3角形数の線形時間でできる
・内部のグラフについても、
同じことを再帰的にする
計算時間: 3角形の数の線形= O( n )
まとめ
・ 2連結3角形グラフに対して、その根の一つを決定的に指
定する O( n ) 時間のアルゴリズムを開発した
・ その結果、2連結3角形グラフの列挙アルゴリズムがの計
算時間が、 1つあたり O(r2n) から O( r n ) になった
・ その他のグラフの列挙アルゴリズムにも適用できそうであ
る
(2辺連結3角形グラフ、3角形グラフは、すぐにできそう)
ダウンロード

power point