Document

A Simple Algorithm for Generating
Unordered Rooted Trees
中野眞一
群馬大学
宇野毅明
情報学研究所
（総研大の博士課程に入
学したい人募集中）
2003年5月23日アルゴリズム研究会
研究背景
列挙の研究は面白い
・キレイな結果の出る問題が残っている
（アルゴリズム的な研究がされつくしていない）
・近年、工学的な応用が増えた
（計算機パワーの増大＆アルゴリズムの進展で、
列挙という手法を使ったモデルを解けるようになった）
問題：根付き木の列挙
問題：頂点数が1からnまでの根付き木を列挙せよ。
ただし、根が同一かつ同型なものは同一視せよ。
例えば、1頂点から子供を付け足していくバックトラック法で
列挙できるが、同型なものをたくさん出力してしまう
応用：グラフマイニング
問題：入力した根付き木の中に頻出する（α回以上現れる）
根付き木を列挙せよ
解法：１頂点からなる木を１つずつ大きくしていき、頻出す
れば出力、頻出でなくなったら引き返す、というバックトラック
型の探索をする
入力した木
順序木と無順序木
順序木：各頂点に、その子供の順序が与えられている木
⇒ 無順序木：順序が与えられていない木
２つの順序木が同型
⇔ 根と、順序を保存する同型写像が存在
これらは無順序木として同型だが、順序木としては異なる
順序木のdepth sequence
順序木のdepth sequence：
左を優先して深さ優先探索し、訪れた頂点の深さをpreorderで並べる
２つの順序木が同型 ⇔ depth sequence が等しい
0,1,2,3,3,2,2,1,2
0,1,2,2,3,3,2,1,2
0,1,2,1,2,3,3,2,2
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,2
0,1,2,2,3,3,2,1,2
0,1,2,1,2,3,3,2,2
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
0, 1,2,3,3,2 ,1,2,2
P(T)
0, 1,2,3,3,2, 1,2
Family tree
Left-heavy embedding の親子関係をグラフで表現
・これを深さ優先探索する
・木Tの子供が作れれば
探索できる
left heavy embedding の子
・ Tの子供 S は、 RP(T) の右に葉をつけたもの
・逆は、成り立つとは限らない
RP(S)の任意の頂点 v について、L(v) ≦ L(bro(v))
⇔ S が left heavy embedding
子供の候補はn個
⇔ S は T の子供
子供のチェック
多項式時間
T
S
多項式時間で列挙可能
もう少しがんばる
子供になる条件１
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
子供になる条件２
v* ： prefix となるものの中で最も浅い頂点
copydepth： v* の深さ
v*について先の条件が成り立てば
任意の vi について成り立つ
深さ1からcopydepthまでの
葉を付けたものが子供
v*
d1
copy depth の保持
・付け足した頂点 u の深さが d1 と同じ
⇒ L(v* ) が L(bro(v* )) の prefix かつ一番浅い
⇒ d1 の次の頂点の深さが copy depth
・ d1より浅い
⇒ u はprefix
その他は prefix でない
⇒ u の深さが copy depth
d1
bro(vi )
vi
アルゴリズムをまとめると
T: 木, d：copy depth、 L: T の depth sequence,
根付き木( T, v )
1: T を出力（前の出力との差分）
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)
n頂点の根付き木の列挙
問題：頂点数がちょうど n の根付き木を列挙せよ
⇒ 根付き木を列挙し、頂点数が n のもののみ出力
計算量は？
＃頂点数nの根付き木
≧ α＃頂点数n-1の根付き木
ならば、1つあたり定数時間
（ #頂点数nの根付き木）を押さえる
問題：頂点数n-1 の木から、それ固有の、頂点数nの木を2つ
作る
⇒
＃頂点数nの根付き木
≧
２× ＃頂点数n-1の根付き木
まとめと今後の展開
・頂点数が 1 から n の根付き木を列挙する、1つ当たり定数
時間のアルゴリズムを提案した
・このアルゴリズムの計算時間が頂点数が n の根付き木に
たいしても、1つ当たり定数時間であることを証明した
今後は：
・グラフマイニングに応用したい
・根のついていない木、平面に埋め込んだ木なども、同じよ
うに列挙したい

Download Report