平面三角分割グラフを列挙する アルゴリズムの改良 中野 眞一 （ 群馬大学 ） 宇野 毅明 （ 情報学研究所 ） 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 回出力される （１つ根無しグラフは、r 個それぞれの外周辺を根とした根 付きグラフになる） つまり、1つの根無しグラフのために最大 r 回の計算 ・ 結局、1つの根無しグラフあたり O(r２n) 高速化をしたい ・根付きの列挙が1つあたり O(1) であるのに対して、 根無しの列挙は1つあたり O(r２n) 根付きのほうが 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)時間かかる それぞれの根について、頭から１文字ずつ順に文字列を計 算していき、途中で辞書順最小ではなくなったものは、候補 から除去する 単純に計算すると もしも比較をしている途中で文字列同士が重ならなければ、 計算時間はO( n ) 文字列が重なってしまう（オーバーラップする）ときの計算時 間を省略する方法を考える 文字列の先頭に反復数を書く 文字列が取り除かれたとき、そのときの反復数を、文字の 先頭に書き込む ※ そこから、その文字数先までは辞書順で最小、ということ を保障している 1 2 オーバーラップの処理１ ・ 文字列同士がオーバーラップするときは、前の文字列の先頭 に後ろの文字列の末尾が重なる ・ 外周に接している3角形には、最小の文字を与えていたので、 この時点で重なっていない文字列は、候補から外れる ・文字列が鎖のように重なったときは、各文字列は、末尾の部分 まで、辞書順で最小になる ABCDE ABCDE ABCDE ABCDE Z ○ × × × オーバーラップの処理２ ・ 重なった部分に数字 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角形グラフの列挙アルゴリズムがの計 算時間が、 １つあたり O(r2n) から O( r n ) になった ・ その他のグラフの列挙アルゴリズムにも適用できそうであ る （2辺連結3角形グラフ、3角形グラフは、すぐにできそう）
© Copyright 2024 ExpyDoc
