A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会.

Presentation on theme: "A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会."— Presentation transcript:

1 A Simple Constant Time Enumeration Algorithm for Free Trees 中野 眞一 宇野 毅明 群馬大学 情報学研究所 2003 年 9 月 19 日 アルゴリズム研究会

2 結果 頂点数が n 、 直径が k である根無し木を １つあたり 定数時間 で出力するアルゴリズムを構築した １つあたり 定数時間 で出力するアルゴリズムを構築した ・ ・ 同型な木を 2 回出力することはない ・ ・ １つ出力してから次を出力するまで、定数時間 「 free tree 」 は、「根の無い木」のことです

3 研究背景 列挙の研究は面白い ・ ・ キレイな結果の出る問題が残っている （アルゴリズム的な研究がされつくしていない） ・ ・ 近年、工学的な応用が増えた （計算機パワーの増大＆アルゴリズムの進展で、 列挙という手法を使ったモデルを解けるように なった） － － データの生成、解候補の作成、ものの特徴付け、な ど

4 問題：根無し木の列挙 問題： 頂点数が n 、直径が k の根無し木を列挙せよ ただし、同型なものは同一視せよ。

5 根無し木の列挙 既存研究： ・ ・ 1 つあたり定数時間。 ・ ・ ただし、複雑でよく分からない ・ ・ Delay （次の出力までの時間）は定数でない

6 問題の難しさ ・ バックトラック法 ・ 通常、この手の列挙問題にはバックトラック法が使 われる ・ ・ 例えば、 1 頂点から子供を付け足していき、 n 頂点、 直径 k になったら出力して引き返し、他の位置に子供を 付け足す。 ⇒ ⇒ 木をメモリに蓄える際に、どうしても根（のような もの）と兄弟の順番が決まる。 ⇒ ⇒ 同型なものが たくさん出てしまう

7 難しさを避ける 作戦： 根無し木に対して、ある標準的な「根の与え方」「子供 の順序の与え方」を定める（標準形） － － 根無し木と標準形は 1 対 1 対応する ・ ・ あとは、標準形を列挙しましょう （※） （※ 以後、直径 k を偶数とする）

8 根の与え方 センター 木のセンターを根とする センター センター： 最も遠い頂点までの距離が最も短い頂点 （つまりは真ん中） 直径が偶数だと、唯一的に定まる

9 順番を与える： depth sequence depth sequence ： 左を優先して深さ優先探索し、訪れた頂点の深さを pre-order で並べたもの ２つの木が順番も含めて同型 ⇔ depth sequence が等しい 0,1,2,3,3,2,2,1,2,3 0,1,2,2,3,3,2,1,2,3 0,1,2,3,1,2,3,3,2,2

10 left heavy embedding L(v) ： v から下の部分木の depth sequence bro(v ) ： v の左隣の兄弟 T が Left-heavy embedding ： ⇔ 任意の頂点 v について、 L(bro(v)) ≧ L(v) ・ left heavy embedding で、子供の順番を与える 0,1,2,3,3,2,2,1,2,3 0,1,2,2,3,3,2,1,2,3 0,1,2,3,1,2,3,3,2,2 辞書順： 長いほうが大きい

11 標準形ができました ・ ・ 根無し木に対して (1) センターを根にする (2) Left-heavy embedding になるように順番をつける として標準形（根付き順序木）が得られる ・ あとは、頂点数が n 、直径が k である、標準形（ left- heavy embedding ）を列挙しましょう

12 left heavy embedding の親 left-heavy embedding T の親 ： T の（根の子供でない）最も右の葉を取り、 根の子供にした木 ⇒ 親も left-heavy embedding ただし、直径が変わってしまう場合は、右から 2 番目をと る 22131 0,1,2,3,3,2,1,2,3, 2,1 0,1,2,3,3, 2,1,2,3,1, 1 0,1,2,3, 3,1,2,3,1,1, 1 T 親親の親

13 Family tree Left-heavy embedding の親子関係をグラフで表現 ・これを深さ優先探索する ・標準形 T の子供が作れれば 探索できる 頂点数 7 、 直径 4 の場合

14 left heavy embedding の子 ・ T の子供 S は T の根の子供を 1 つとり、（深さ 2 以上 の）最も右の葉になるように付けたもの ・逆は、成り立つとは限らない。しかし、 「ある頂点 v の深さ以下であれば子供になる」 という性質が成り立つ v v しかも、子供の v は、親の v の次か、加えた頂点の直左 T 子供 O(1) 時間で 更新できる O(1) 時間で 作れる １つ定数時間 で列挙できる

15 Delay を定数にする ・ 「深さが奇数の反復は、再帰呼び出しの前に出力」 「深さが偶数の反復は、再帰呼び出しの後に出力」 とすると、次の出力までの計算時間が定数（３反復以下） になる 再帰構造

16 2 つのセンターを１つの頂点のように扱い、同様の議論をする （根の子供の順番付けに関して例外処理が必要） 直径が奇数の場合 ・ センター ・ センターが２つになる

17 まとめと今後の展開 ・頂点数 n 、直径 k の根無し木を列挙する、次の出力 まで定数時間であるアルゴリズムを提案した ・ まず直径が偶数の場合のアルゴリズムを作り、直径 が奇数の場合は、それを拡張した今後は： ・ 平面に埋め込んだ木や、木以外のグラフオブジェク トも（簡単なアイディアで）列挙したい