グラフの列挙 中野 眞一 （群馬大学） 2015/9/28 列挙学校 1 列挙アルゴリズム設計技法 ・（新種発見） ・分割探索 ・辞書（Gray） ・逆探索 ・家系木 ・etc. 2015/9/28 いつ終わる？ タイプごとに 順番に 親戚関係で 列挙学校 2 グラフのクラス ・木 ・平面グラフ ・矩形描画 2015/9/28 列挙学校 3 木に関する用語 家系図とみなす 親、子、兄弟、先祖、子孫 根 葉 2015/9/28 点の高さ、深さ 根は深さ０ 葉は高さ０ 列挙学校 4 木 ・根つき木 or ・順序木 or ・子の個数 自由木 順序なし木 任意 or ちょうど２ or 高々2 or 少なくとも２ 対応 2015/9/28 列挙学校 長男 と すぐ下の弟 5 木の列挙（辞書法） ・根つき順序木 ・深さ優先横断(downとupを記録) DUDUDDUDUDUUDU m辺の木を2m文字に符号化 2015/9/28 列挙学校 6 木の列挙（辞書法） ・５辺の順序木の辞書 に最初に掲載されている木は？ DDDUDUUU 2015/9/28 列挙学校 DDUDUDUU 7 木の列挙（辞書法） ・５辺の順序木の辞書 に最初に掲載されている木は？ DDDDDUUUUU ・2番目の木は？ ・３番目の木は？ ・次は？次は？ 2015/9/28 列挙学校 8 木の列挙（辞書法） ・５辺の順序木の辞書 DDDDDUUUUU DDDDUDUUUU DDDDUUDUUU DDDDUUUDUU DDDDUUUUDU DDDDUUUUUD だめ 2015/9/28 列挙学校 9 木の列挙（辞書法） ・５辺の順序木の辞書 DDDDDUUUUU U??? D DDDDUDUUUU D U DDDDUUDUUU D U U DDDDUUUDUU DDDDUUUUDU DDDDUUUUUD だめ( ( ( ( ) ) ) ) ) ( 2015/9/28 列挙学校 10 演習１ ・５辺の順序木の辞書を完成せよ ・ｍ辺の順序木の辞書を出力する アルゴリズムを設計せよ ・ｍ辺かつL葉の順序木の列挙アルゴ リズムを設計せよ ・ｍ辺かつ高さがｈの順序木の列挙ア ルゴリズムを設計せよ 2015/9/28 列挙学校 11 演習２ ・５辺の順序なし木の辞書を完成せよ ・ｍ辺の順序なし木の辞書を出力する アルゴリズムを設計せよ ・ｍ辺かつL葉の順序なし木の列挙ア ルゴリズムを設計せよ ・ｍ辺かつ高さがｈの順序なし木の列 挙アルゴリズムを設計せよ 2015/9/28 列挙学校 12 演習３ ・順序木の他の符号化法を設計せよ ・その符号に基づき順序木の辞書 を出力するアルゴリズム を設計せよ ・幅優先横断(子の個数を記録) 11110001110000 2015/9/28 列挙学校 13 もっと学びたい方へ The Art of Computer Programming, Fascicle 4: Generating All Trees -- History of Combinatorial Generation (Art of Computer Programming) Donald E. Knuth (2006/2/14) Addison-Wesley $19.99 ISBN-10: 0321335708 2015/9/28 列挙学校 14 木の列挙（家系木法） ・根つき順序木 2015/9/28 列挙学校 15 木の列挙（家系木法） ・高々ｍ辺の 順序木の 集合には 木の構造 がある 2015/9/28 ・深さｋ ｋ辺の木 列挙学校 16 木の列挙（家系木法） 指定した 木の子を 再帰的に 列挙する ・深さｋ ｋ辺の木 2015/9/28 列挙学校 17 順序木の列挙（家系木法） Shin-ichi Nakano "Efficient Generation of Plane Trees“ Information Processing Letters, Vol.84, no. 3, pp.167-172 (2002). 子のリスト 2015/9/28 親 列挙学校 18 順序なし木の列挙（家系木法） Shin-ichi Nakano and Takeaki Uno, “Constant Time Generation of Trees with Specified Diameter”, Proc. of WG 2004 LNCS, 3353, pp.33-45 (2004). Left Heavy のみ列挙 2015/9/28 Left Heavy ？ 列挙学校 19 演習４ ・Left Heavyを定式化せよ ・Left Heavyな順序木を列挙するアル ゴリズムを設計せよ （順序なし木の列挙） 2015/9/28 列挙学校 20 （内部）極大平面グラフ ・内面がすべて三角 ・３Dワイヤモデル 外点 ｒ個 内点 ｖ個の グラフをすべて 列挙せよ 2015/9/28 列挙学校 21 極大平面グラフ 2015/9/28 対角スイッチ 列挙学校 22 極大平面グラフ 対角スイッチ ・点vの回りに ４点a,b,c,dがある ・辺vb もしくは vc d は対角スイッチ c できる ・Wagner定理[1936] b v 任意の２つの a 極大平面グラフは 対角スイッチのみで互いに変換可能 2015/9/28 列挙学校 23 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす d d c v c b v a 2015/9/28 b a 列挙学校 24 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす 3次 3次 3次 3次 3次 ？ 3次 3次 2015/9/28 ?次 ?次 列挙学校 25 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす 3次 3次 3次 3次 3次 ？ 3次 3次 2015/9/28 ?次 ?次 列挙学校 a 26 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす a 2015/9/28 列挙学校 27 極大平面グラフ 対角スイッチ 最後の処理 2015/9/28 列挙学校 28 極大平面グラフ 対角スイッチ 任意の外点r個 内点ｖ個のグラフ 根 2015/9/28 列挙学校 29 極大平面グラフの列挙 対角スイッチ+Wagner定理 Avis 96 O(n2) 時間/each 2015/9/28 カノニカル順序 Li & Nakano 01 O(1) 時間/each 列挙学校 30 極大平面グラフのカノニカル順序 7 7 6 6 5 6 6 44 5 3 1 2 44 5 3 1 2 1 2015/9/28 1 2 家系木 3 2 3 1 44 3 44 2 列挙学校 31 演習5 直径ｋ 葉L個のキャタピラ （葉をすべて除くとパスになる木） を列挙するアルゴリズムを設計せよ 根なしに注意 (Kikuchi他 COCOON 03) 2015/9/28 列挙学校 32 フロアプラン 90度 回転 ・すべての面が四角形 ・回転 同じ or 異なる ・４次点 あり or なし ・面積関係なし 上と同じ ４次点 左の２つの図は 矩形分割としては同じ フロアプランとしては異なる 2015/9/28 列挙学校 33 フロアプランの左上の面を順次除去 2015/9/28 列挙学校 家系木 34 フロアプランの左上の面を順次除去 親 子のリスト 2015/9/28 列挙学校 35 フロアプランの家系木 2015/9/28 列挙学校 （S.Yoshii 2002 図) 36 演習6 内面の個数がｎのフロアプラン を列挙するアルゴリズムを設計せよ O(1)時間/each (Nakano ISAAC 01) 2015/9/28 列挙学校 37 フロアプランの列挙（回転を同じとする場合） 家系木 ９０度回転で得られる４つフロアプランの内１つのみを出力 2015/9/28 列挙学校 38 演習7 内面の個数がｎのフロアプラン を列挙するアルゴリズムを設計せよ ただし、９０度回転で得られる ４つのフロアプランは同一とみなす O(n)時間/each （Nakano ISAAC 01) 2015/9/28 列挙学校 39 一様ランダム生成（順序木） 大量メモリ＋前処理 なら簡単 一覧辞書＋乱数でＯＫ メモリ小かつ前処理なしで 一様ランダム生成したい。。。 2015/9/28 列挙学校 40 一様ランダム生成（順序木） Dyckパス 2015/9/28 列挙学校 41 一様ランダム生成（順序木） サイクルシフト 2015/9/28 ・ｍ辺の順序木はm+1個の Dとm個のUの文字列に対 応する ・各文字列をサイクルシフト して得られる2m+1個の文 字列のうち１個だけが順序 42 列挙学校 木に対応する 順序木 サイクルシフト ３文字シフト 順序木に対応 ４文字シフト １文字シフト ５文字シフト ２文字シフト ６，７，８文字シフト 2015/9/28 列挙学校 43 順序木 サイクルシフト ・m+1個のDとm個のUの文 字列を一様ランダム生成 ・サイクルシフトして得られ る１個を選ぶ ・順序木として出力 ・1,2,…,2m+1の順列を一 様ランダム生成 ・1,2,..m+1をDに, 他をUに 置き換え 2015/9/28 列挙学校 選択 選択 選択 44 演習8 m 辺 かつ L 葉の 順序木を一様ランダムに生成する アルゴリズムを設計せよ （理系への数学 ２００８年７月号掲載予定 中野） 2015/9/28 列挙学校 45 演習∞ 高速に列挙できる対象を列挙せよ 高速に一様ランダム生成できる対象 を列挙せよ 2015/9/28 列挙学校 46
© Copyright 2024 ExpyDoc
