平面三角分割グラフを列挙す るアルゴリズムの改良 中野 眞一 （ 群馬大学 ） 宇野 毅明 （ 情報学研究 所 ） 2002 年 6 月 24 日 コンピューテーション研究会.

Presentation on theme: "平面三角分割グラフを列挙す るアルゴリズムの改良 中野 眞一 （ 群馬大学 ） 宇野 毅明 （ 情報学研究 所 ） 2002 年 6 月 24 日 コンピューテーション研究会."— Presentation transcript:

1 平面三角分割グラフを列挙す るアルゴリズムの改良 中野 眞一 （ 群馬大学 ） 宇野 毅明 （ 情報学研究 所 ） 2002 年 6 月 24 日 コンピューテーション研究会

2 列挙問題 列挙問題（発生）： 与えられた集合の要素を全て、ちょうど 1 度ずつ出力 する問題 ・総数を数えたり、サンプリングをしたり、性質を調 べたりと目的が多様 ・アルゴリズムをツールとして考えると、いろいろな 問題に対して、ともかく速いアルゴリズムを作ってお くと良い

3 列挙問題、例えば グラフの 全張木・パス・閉路・マッチング・木 多面体の 頂点・面 平面の 三角形分割・アレンジメント 全ての 2 分木・文字列・置換・順列・平面グラフ・連結グラ フ 最適化問題の 最適解・極大解・実行可能解

4 2 連結平面 3 角グラフ 平面グラフ： 枝が交差させずに平面埋込できるグ ラフ 3 角グラフ： 全ての面が ( 外側の面を除いて） 三角形になる平面グラフ 2 連結 3 角グラフ： 3 角グラフで、カット頂点がないもの 根付き 2 連結 3 角グラフ： 2 連結 3 角グラフの、外周上の辺の 1 つが根に指定されているもの

5 2 連結 3 角グラフ列挙の研究 根付き： 96 D. Avis 一つあたり O( n 2 ) 01 中野 一つあたり O( 1 ) 根無し 98 B.D.McKay 一つあたり O( n 2 ) ? 01 中野 一つあたり O( r 2 n ) 今回：根無し 一つあたり O( r n )

6 01 年のアルゴリズム（根付き） 逆探索： 列挙する対象間に親子関係を定義し、導出さ れる木を深さ優先探索して全ての要素を出力する方法 ・ 頂点数 n のグラフの親を、頂点数が n-1 のグラフで定 める ・ 頂点数 3 のグラフ（ 3 角形）を根とする木になる

7 計算量 木の深さ優先探索にかかる時間を算定すればよい ・ ほとんどの内点は子供を 2 人以上持つ  頂点数 ≦ 3 × 頂点数 n のグラフ数 ・ 枝の移動 = O(1) より、 1 つあたり O(1) 時間で列挙できる

8 根無しの列挙 ・ 根付きではないものを列挙するには、 重複した出力をやめれば良い ・ 今までの出力を保存してチェック ・・・ × メ モリ爆発 ・ 根だけ違うグラフに順序を付け、最小のものだけ 出力 グラフと根が与えられたときに、過去の出力を参照せずに、 そのグラフを出力するかどうかを決める必要がある

9 文字列を与える 中野 01 では： ・ 根付きグラフに文字列を与える （異なる根・グラフに異なる文字列） ・ 同じグラフの中で、最小文字列を与える根だけを 出力 ・ グラフが出てきたら、他の枝を根としたときの文 字列を計算し、自分が最小なら出力する ・ 対称なグラフは 1 度しか出力されないので、それら に関して異なる文字列を与える必要はない

10 計算時間 ・ 1 つのグラフ＆根に対して、文字列を計算するのに O(n) ・ 全ての根に対して計算すると O(r n) ・ 1 つのグラフは最大で r 回出力される （１つ根無しグラフは、 r 個それぞれの外周辺を根と した根付きグラフになる） つまり、 1 つの根無しグラフのために最大 r 回の計算 ・ 結局、 1 つの根無しグラフあたり O(r ２ n)

11 高速化をしたい ・根付きの列挙が 1 つあたり O(1) であるのに対して、 根無しの列挙は 1 つあたり O(r ２ n) 根付きのほうが r 倍程度、総数が多いことを考慮して も、少々遅いのではないか？ －－ 是非高速化を行いたい ・ うまいアイディアが出てくれば、他の平面グラフオ ブジェクト（木とか 2 分木とか 3 角グラフとか）の列挙 も高速化できるかもしれない

12 今回の方針 ・ 1 つの根無しグラフのために最大 r 回の計算をして いる、というところは、手を付けない ・ 全ての根に対して文字列の計算をすると O(rn) 、と いう、ここを速くしてみよう 結果： ・ 異なる文字列を与える方法を考案した ・ 最小の文字列を与える根を O(n) 時間で求められる （最小でない根の文字列の計算をさぼっている）

13 見方を変えると 今回扱う問題は、 -------------- 平面 2 連結グラフ  そのグラフの外周上の辺 という写像を設計したい ただし、高速に求められないと意味がない （ O(r n) より速く ） ---------------- というものである

14 外周面 D 0 を定義 ・ 外周上の点に接する面（ 3 角形）からなるグラフを D 0 とする ・ D 0 を取り除いて残ったグラフを内部とする ※ 内部は、いくつかの 2 連結 3 角グラフになる

15 まず、 3 角形のタイプ分け ・ 取り除いた、それぞれの 3 角形を、全ての頂点が外周 に乗っているか、外周に乗っているか、内部と接してい るか、などで 10 通りに分ける それぞれのタイプに文字を割当てる ・ 外周に接する 3 角形に、最小の文字を割当てる

16 3 角形にパラメータを与える ・ 2 箇所以上の外周に接している面には、外周に再び 自分が現れるまでの ・ 頂点のみで接しているものには、辺をはさんで反 対側の三角形の頂点までの （時計回りでの）外周の辺数をパラメータとして与 える 文字列とパラメータが決まると、 D 0 の形は一通りに定まる

17 根に文字列を与える 各根に対して、その根（辺）からスタートして、 時計回り順に D 0 の 3 角形の （ 3 角形のタイプ と パラメータ の組） を並べた物を、根の （ D 0 に関する）文字列とする

18 内部の文字列を与える 内部の 3 角形が作るグラフについても、根に近い連結成 分から順に、根に最も近い辺を根として、同様に文字 列を計算し、再帰的に付け加えて、根の文字列を定義 する

19 文字列とグラフ＆根が対応 ・グラフと根から、文字列が唯一的に決まる ・文字列を与えると、グラフと根が唯一的に決まる 2 つの （グラフと根）に対して、 文字列が同じ  グラフと根が同型 文字列が異なる  グラフか根が異なる

20 辞書順で最小の根を探す 各根について、その根の文字を計算して、辞書順で最 小のものを見つける ‥‥ O(r n) 時間かかる それぞれの根について、頭から１文字ずつ順に文字列 を計算していき、途中で辞書順最小ではなくなったも のは、候補から除去する

21 単純に計算すると もしも比較をしている途中で文字列同士が重ならなけ れば、 計算時間は O( n ) 文字列が重なってしまう（オーバーラップする）とき の計算時間を省略する方法を考える

22 文字列の先頭に反復数を書く 文字列が取り除かれたとき、そのときの反復数を、文 字の先頭に書き込む ※ そこから、その文字数先までは辞書順で最小、とい うことを保障している 12

23 オーバーラップの処理１ ・ 文字列同士がオーバーラップするときは、前の文字列の 先頭に後ろの文字列の末尾が重なる ・ 外周に接している 3 角形には、最小の文字を与えていた ので、この時点で重なっていない文字列は、候補から外れ る ・文字列が鎖のように重なったときは、各文字列は、末尾 の部分まで、辞書順で最小になる ABCDE ABCDE ABCDE ABCDE Z ○ × × ×

24 オーバーラップの処理２ ・ 重なった部分に数字 k が書かれている（消去された文字 列）ものは、 その k 文字先まで辞書順最小 ・ 以上から、もっとも長くまで辞書順で最小のもののみが 生き残り、その他は候補からはずれる ※ （生き残りの長さを k とすると） k 文字先まで探索を省け る 5 ABCDE ABCDE Z 2 ABCDE AB Z ○ ×

25 計算量 文字列に 1 文字付け加えると、 ・ 文字がひとつ新たに探索される、か ・ 重なった場合には候補がひとつ消える ので、根の文字列の中で D 0 に関する部分で最小なもの を求めるのは、 D 0 に含まれる 3 角形数の線形時間でで きる ・内部のグラフについても、 同じことを再帰的にする 計算時間： 3 角形の数の線形＝ O( n )

26 まとめ ・ 2 連結 3 角形グラフに対して、その根の一つを決定的 に指定する O( n ) 時間のアルゴリズムを開発した ・ その結果、 2 連結 3 角形グラフの列挙アルゴリズムが の計算時間が、 １つあたり O(r 2 n) から O( r n ) に なった ・ その他のグラフの列挙アルゴリズムにも適用できそ うである （ 2 辺連結 3 角形グラフ、 3 角形グラフは、すぐにで きそう）