あみだくじを数え上げる 省領域アルゴリズム ◯中嶋章裕，斎藤寿樹，山口一章，増田澄男 （神戸大学） 1
あみだくじ 2 研究室掃除分担 中嶋行本 斎藤 先生 塚本 机 黒板なし その他 全部 寺脇 空調 上の要素を並べ替え ↓ 下の要素と順番に対応付け
あみだくじ 上の順列を下の順列に置換
あみだくじ 順列の置換を行う ネットワーク Bar は 2 要素を入れ替え る 離散数学，群論分野 で重要 降順に並んだ順列を 昇順に置換する最小 標準形あみだくじは Primitive Sorting Network と等価 Bar 縦線本数： n=4 Line
最小標準形 5 ・最小形 ・標準形 ・最小標準形 最小形かつ標準形なあみだくじ あみだくじを完成させる為に 最低限必要な bar の本数 bar の置き方を規定する
最小形 6 ．．．．．．
最小形 7 ．．．．．． 最小形
最小標準形 8 ・最小形 ・標準形 ・最小標準形 最小形かつ標準形なあみだくじ あみだくじを完成させる為に 最低限必要な bar の本数 bar の置き方を規定する bar を置ける位置 ☓ ☓
最小標準形 9 ・最小形 ・標準形 ・最小標準形 最小形かつ標準形なあみだくじ あみだくじを完成させる為に 最低限必要な bar の本数 bar の置き方を規定する bar を置ける位置 ☓ ☓ ☓ ☓
標準形 10 標準形ではない標準形
あみだくじの数え上げ問 題 同じ置換を表すあみだくじは複数存在 降順あみだくじは Primitive Sorting Network と対応 11 縦線本数 n = 4 の最小標準形あみだくじ 最小標準形の降順あみだくじを数え上げる
あみだくじの総数 12 n#LaddersDate May May Jan Oct Aug Aug ？
あみだくじの総数 13 n#LaddersDate May May Jan Oct Aug Aug ？ 本研究とは独立して MDD を用いて数え上げ (Nov.2013) πDD MDD 先を越された (´ ・ ω ・｀ )
多値決定グラフ (MDD, Multi-valued Decision Diagram) 14 Non-reduced MDDReduced MDD MDD: 多値論理を表現する根付き有向グラフ
あみだくじと MDD 15 b1 b2 b3 τ3 τ2 τ1 b1 b2 b3 τ1τ3 τ2 τ1 τ2τ3 b3 τ3 τ2 b2 b3 τ2 τ1 τ3 ・・・・・・・・・・ 1
従来法とその問題点 MDD の深さ中央付 近で大量のメモリ を消費 16 ボトルネック 深さ深さ ノード数 深さ トップダウン的に構築 各深さでのノードを全てメモリ上に保持
提案法 17 深さ ノード数 トップダウン的に構築 1 st Phase 2 nd Phase 3 rd Phase 分割構築
計算機実験結果 C1MDD size (1 st Phase) MDD size (2 nd Phase) time 縦線本数 =9 CPU: Intel C2D 1.6GHz, Mem: 4GB, OS: MacOSX 10.8
計算機実験結果 19 *n=13 のみ CPU: Intel(R) Xeon(R) Mem: 128GB, OS: CentOS6.5 計算機サーバで実験 分割開始深さ 2 の MDD ノード数 22GB←100GB 以上
計算機実験結果 20 *n=13 のみ CPU: Intel(R) Xeon(R) Mem: 128GB, OS: CentOS6.5 計算機サーバで実験 分割開始深さ 2 の MDD ノード数 22GB←100GB 以上 分割数をより多くするこ とで， 40 〜 50MB まで削減可能 （理論上）
まとめ 多値決定グラフの分割構築により，メモリ使用量を 効率的に削減できた 課題 分割された MDD を更に分割し，メモリをより削減 分割フェーズの高速化 並列化など 21
MDD 規則 22 等価なノードの共有簡約化規則
あみだくじ 同一水平線上には必ず 1 本 だけ bar が入る bar は隣り合う line を繋ぐ bar は水平に繋ぐ 降順に並んだ順列を昇順 に置換す
あみだくじと MDD 24 b1 b2 b3 τ1τ3 τ2 τ1 τ2τ3 b3 τ3 τ2 b2 b3 τ2 τ1 τ3 ・・・・・・・・・・ 1 それぞれのノードには， 根からのパスを保持させ る． b4 ノードの構築には， b3 ノードのみ必要 ↓ b1 ， b2 はいらないので消せ る
降順あみだくじを数える前に 25 書き方を変えると同じ → どう区別する？