A Simple Algorithm for Generating Unordered Rooted Trees

Presentation on theme: "A Simple Algorithm for Generating Unordered Rooted Trees"— Presentation transcript:

1 A Simple Algorithm for Generating Unordered Rooted Trees
中野 眞一　　　　宇野 毅明 　群馬大学 　　 　情報学研究所 　　　　　　　　　　　　（総研大の博士課程に入　　　　　　　　　　　学したい人募集中） 2003年5月23日　アルゴリズム研究会

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

3 問題：根付き木の列挙 問題： 頂点数が1からnまでの根付き木を列挙せよ。 ただし、根が同一かつ同型なものは同一視せよ。
例えば、1頂点から子供を付け足していくバックトラック法で列挙できるが、同型なものをたくさん出力してしまう

4 応用：グラフマイニング 問題： 入力した根付き木の中に頻出する（α回以上現れる）根付き木を列挙せよ
問題：　入力した根付き木の中に頻出する（α回以上現れる）根付き木を列挙せよ 解法：　１頂点からなる木を１つずつ大きくしていき、頻出すれば出力、頻出でなくなったら引き返す、というバックトラック型の探索をする 入力した木

5 順序木と無順序木 順序木：各頂点に、その子供の順序が与えられている木 ⇒ 無順序木：順序が与えられていない木 ２つの順序木が同型
⇒ 　無順序木：順序が与えられていない木 ２つの順序木が同型 　⇔　 根と、順序を保存する同型写像が存在 これらは無順序木として同型だが、順序木としては異なる

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

7 left heavy embedding L(v) ： v から下の部分木の depth sequence
bro(v ) ： v の左隣の兄弟 T が Left-heavy embedding ： 　 ⇔ 任意の頂点v について、L(bro(v)) ≧　L(v) ・ left heavy embedding と無順序木は１対１対応 ⇒ left… を列挙しましょう 辞書順： 長いほうが大きい 0,1,2,3,3,2,2,1, ,1,2,2,3,3,2,1, ,1,2,1,2,3,3,2,2

8 left heavy embedding の親
left-heavy embedding T の親 P(T)　 　 ： Tの最も右の葉を取った木 RP(T) ： left heavy embedding T の最も右のパス ・ RP(T)の各頂点 v について、 L(v) の末尾が１つ削られる 　　　　　　⇒ 　P(T) は left heavy embedding T P(T) 0, 1,2,3,3,2 ,1,2, , 1,2,3,3,2, 1,2

9 Left-heavy embedding の親子関係をグラフで表現 ・これを深さ優先探索する ・木Tの子供が作れれば 探索できる
Family tree Left-heavy embedding の親子関係をグラフで表現 ・これを深さ優先探索する ・木Tの子供が作れれば 　探索できる

10 left heavy embedding の子
・ Tの子供 S は、 RP(T) の右に葉をつけたもの ・逆は、成り立つとは限らない 　　RP(S)の任意の頂点 v について、L(v) ≦ L(bro(v)) ⇔ 　 S が left heavy embedding 　⇔ 　S は T の子供 多項式時間で列挙可能 もう少しがんばる 子供の候補はn個 子供のチェック 多項式時間 T S

11 子供になる条件１ vi ： RP(T) の深さ i の頂点 ■ L(vi ) が L(bro(vi )) の prefix でない
　　　⇒ L(vi ) に何を付け足しても L(vi ) ＜ L(bro(vi )) ■ L(vi ) が L(bro(vi )) の prefix （ L(bro(vi )) = L(vi ) d1 d2 d3 … ） 付けた葉の深さが d1 以下 ⇔ L(vi ) ≦ L(bro(vi )) vi bro(vi ) ・ 任意の vi について 成り立てば、子供

12 子供になる条件２ v* ： prefix となるものの中で最も浅い頂点 copydepth： v* の深さ v*について先の条件が成り立てば
任意の vi について成り立つ v* 深さ1からcopydepthまでの 葉を付けたものが子供 d1

13 copy depth の保持 ・ 付け足した頂点 u の深さが d1 と同じ
　⇒ L(v* ) が L(bro(v* )) の prefix かつ一番浅い 　⇒ d1 の次の頂点の深さが copy depth ・ d1より浅い ⇒ u はprefix 　その他は prefix でない ⇒ u の深さが copy depth vi bro(vi ) d1

14 アルゴリズムをまとめると T: 木, d：copy depth、 L: T の depth sequence, 根付き木( T, v )
2: j := L での d の次の深さ 3: 根付き木( T+深さが j の葉, j ) 4: for i=0 to j-1 5: 　 根付き木( T+深さ i の葉, i ) ・ 1反復の計算量 ＝ O(子供の数) ⇒ 1反復あたり O(1) ・ 出力 は1反復あたり差分1 ⇒ 1回あたり O(1) ・ メモリ使用量は O(n)

15 n頂点の根付き木の列挙 問題： 頂点数がちょうど n の根付き木を列挙せよ ⇒ 根付き木を列挙し、頂点数が n のもののみ出力 計算量は？
ならば、1つあたり定数時間

16 問題： 頂点数n-1 の木から、それ固有の、頂点数nの木を2つ作る ⇒ ＃頂点数nの根付き木 ≧ ２× ＃頂点数n-1の根付き木

17 まとめと今後の展開 ・頂点数が 1 から n の根付き木を列挙する、1つ当たり定数時間のアルゴリズムを提案した
今後は： ・ グラフマイニングに応用したい ・ 根のついていない木、平面に埋め込んだ木なども、同じように列挙したい