A0３班 論理関数表現のモデルと シンボリックアルゴリズム 電気通信大学 北海道大学 武永 康彦 湊 真一 本研究の研究対象 論理関数のグラフ表現 グラフアルゴリズム OBDD、 二分木など シンボリック アルゴリズム OBDDなどで表現されたデータの操作に基づくアルゴリズム 研究内容 論理関数のグラフ表現の 性質、複雑さ グラフアルゴリズム OBDD等によるデータの 表現法とアルゴリズム １．論理関数のグラフ表現 ・Tree-Shellable論理関数の性質 論理関数の二分木表現の性質を解明する 信頼性計算、双対化などに有効 ０ （Ordered)Tree-Shellable論理関数: 論理関数の主項と(変数順序つき） 同数の１パスを持つ二分木で表現 できる正論理関数 x2 x1 １ x2 ０ １ x3 x4 １ １ １ １ １ １ f x1 x2 x1 x3 x2 x4 Tree-Shellable論理関数 ・ 制限のついたDNFに対するtree-shellability DNF中の同一変数の出現回数、積項の長さを制限 これらをパラメータとして考察 ・DNF中の変数の出現回数 高々i 回に制限 → 項数 i 2 を超えると tree-shellableになり得ない 定数回なら多項式時間で判定可能 Tree-Shellable論理関数 ・ 制限のついたDNFに対するTree-Shellability ・積項の長さ 定数に制限した場合の判定複雑さ tree-shellable ・・・ 多項式時間 ordered tree-shellable ・・・ NP完全 多項式時間でtree-shellabilityを判定可能な 実用的に有用なクラスの発見 ・ 正論理関数以外への拡張 パスと主項の対応が複雑 2. データのシンボリック表現とアルゴリズム ・種々のデータのOBDDなどによる表現法 ・シンボリック表現上の論理演算等の操作に基づく アルゴリズム x1 OBDD(二分決定グラフ） 論理関数のグラフ表現 ・変数順序を決めれば表現が一意 ・多くの実用的論理関数を小さく表現 ・論理演算等が高速に実行可能 OBDDに類した表現法も種々提案される ０ x2 １ １ ０ ０ x3 １ 0 1 データのシンボリック表現とアルゴリズム シンボリックグラフアルゴリズム ・区間グラフ処理のアルゴリズム ・トポロジカルソートの列挙 ・BMDによる重みつきグラフの表現 種々の計算モデルとOBDD表現 ・ZBDDによるベイジアンネットワークのコンパイル ・量子論理回路のBDD表現 ・OBDDによる画像表現とアルゴリズム など 区間グラフのOBDD表現とシンボリック アルゴリズム 区間表現に基づくOBDD表現 通常の表現（辺集合を関数で表現）に比べサイズ小 区間グラフに対する基本的操作のアルゴリズム 隣接頂点集合を求める、距離ｋ以内の頂点集合を求める、 など OBDDによるトポロジカルソートの列挙 特にデータ間の共通部分が多い場合、多数のデータを 小さなサイズで保持できる 条件を満たす解の探索が可能 実験の結果、非常に多数の解をコンパクトに表現 例：n×nグリッドグラフ n 頂点数 解の数 OBDD サイズ 2 4 2 13 3 9 42 87 4 16 24024 431 5 25 ? 1925 OBDDによるトポロジカルソートの列挙 問題点・・・単純な方法では計算途中のOBDDサイズが増大 →メモリ量、OBDD処理時間 シンボリックグラフ処理を用いて解空間をあらかじめ縮小 各頂点への最大パス長、など →計算途中の最大OBDDサイズが大幅減 ４×４、５×５グリッドグラフで８７～８８％減少 種々の列挙アルゴリズムへの応用 Compilation of Bayesian Networks Using ZBDDs 「Compilation of Bayesian Networks」: ベイジアンネットワークの確率計算式をBDDに変換し、 高速に計算。[Minato et al. IJCAI-2007] ゼロサプレス型BDD 指数関数的な長さの確率計算式が コンパクトに因数分解された表現。 一旦、ZBDDによる計算式表現を生成（＝コンパイル）できれば、 ベイジアンネットが表す各事象の発生確率を高速に計算できる。 実験の結果、数千個の変数を含む大規模なベイジアンネットを コンパイル可能に 論理関数処理技術の新しい展開（確率モデル計算の連携） Compilation of Bayesian Networks Using ZBDDs ベイジアンネット 線形確率計算式 （指数サイズ） MLF(B) b1 0 b2 1 0 0 b(0.2) b(0.8) 因数分解表現 （ZBDD) 1 0 1 b(0.2) 1 b(0.8) a1 a2 a(0.4) 条件付確率テーブル a(0.6) 0 1 量子論理回路のBDD表現 量子論理回路のBDD表現（DDMF, QMDD)の表現能力の 考察とCADへの応用 （奈良先端・山下先生のA07班との連携） 現実的な量子論理回路の設計検証技術を提供 超低消費電力回路や光論理回路設計への 応用の可能性 OBDDによる画像表現とアルゴリズム データによっては小さなサイズで表現でき、 圧縮したデータのまま、全ての画素に同時に同じ処理を 実行可能 ・ 画像の表現法 座標(x,y)の濃度が z zk 1 z1 z0 OBDD表現 f ( x, y, z ) 1 SBDD表現 fi ( x, y ) 1 (0 i k 1) 整数値をもつデータの表現、処理手法 閾値処理、平行移動、輪郭抽出、フィルタ処理など ３．グラフアルゴリズム パラメータ化グラフ上の基本的グラフ問題 一般にはNP困難だが、特定のグラフクラスに 対しては多項式時間で解ける問題が多い ↓ あるクラスのグラフに「近い」グラフでは？ 「近さ」をパラメータとし、パラメータ付き計算量 の観点から評価 パラメータ化グラフ上のグラフアルゴリズム C＋ke(-ke)グラフ：Cグラフに辺(モジュレータ)をk本追加 (削除)して得られるグラフ ・ 比較可能+keグラフ、比較可能-keグラフの 頂点彩色問題など ・ Chordal+k１e-k2eグラフの頂点彩色問題 比較可能+keグラフ、-keグラフの 頂点彩色問題 比較可能グラフ 推移的な辺の方向付けが可能な無向グラフ 頂点彩色問題は多項式時間で解ける 頂点彩色問題の計算量 ・ 比較可能+keグラフ k=1 多項式時間 k=2 NP完全 ・ 比較可能-keグラフ k=1 多項式時間 a b c d e 比較可能+keグラフ、-keグラフの 頂点彩色問題 比較可能+1eグラフの彩色 推移的なグラフを求める 比較可能グラフでモジュレー タの両端が必ず同色 ⇔彩色数1増 モジュレータ 比較可能+2eグラフ 彩色数が１増えるか、 ２増えるか、ともにNP完全 彩色数の増加しない例(ハッセ図） Chordal+k1e-k2eグラフの 頂点彩色問題 辺の追加と削除を同時に考えたグラフに対する おそらく初めての結果 Fixed parameter tractableアルゴリズムを設計 Chordal+keグラフに対するアルゴリズム tree-decompositionを利用 →削除された辺に対する処理を可能に Fixed parameter tractable:問題のサイズn、 パラメータkに対し、O( f (k )nc ) 時間で解ける まとめ ・論理関数のグラフ表現の性質の解明 グラフ表現と主項など他の表現との関連 ・データのOBDDなどによる表現法とその応用 シンボリックアルゴリズムの設計手法 様々な分野への応用の可能性を探る ・基本的グラフ問題のアルゴリズム パラメータ化計算量
© Copyright 2024 ExpyDoc
