Bluemo's Brain

Search

Search IconIcon to open search

BDD

Last updated Dec 16, 2022 Edit Source

    • 二分決定グラフ

      グラフ

      プロットするグラフと、のグラフの二つの意味がある このscrapboxでは、のグラフを指す 使用頻度/リンクされる価値はこっちの方が高いかなーと プロットするグラフは、とかの言葉を使う https://ja.wikipedia.org/wiki/グラフ理論 種類 密vs疎 ...

      1/3/2023

    • 論理関数 = 0/1の組み合わせに対して0/1を返す物

    • 論理関数をBDDで表せる

    • BDDで、AND, OR, XORなどが表現できる

      • 変数の数nに比例する大きさのBDDになる
      • 最後の出力の0と1を置き換えてあげれば、NAND, NORなども表現できる

    • BDDは、変数の順序によってもサイズが大きく変わる

    • BDDは、簡約化・圧縮できる

    • [ZDD]

      • 通常のBDD

        BDD

        二分決定 = 0/1の組み合わせに対して0/1を返す物 論理関数をBDDで表せる https://ja.wikipedia.org/wiki/二分決定図 より BDDで、AND, OR, XORなどが表現できる ...

        1/3/2023

        と少し違う圧縮方法
        • 少し違うというか、BDDより多くのものを圧縮する
      • BDDの圧縮基準に加え、1の場合に最終出力0に向かう場合もその変数自体を消しちゃう
      • 最終出力が1の場合のみ気にしたい場合に有効
        • ex: 商店の購買データ
      • 疎な集合（ほとんどの到着点が0）の場合に著しい効果が出る（コンパクトに表現できる）

    • 一言でいうと

      • BDD: Dont’careを省略、密な論理関数に向いてる
      • ZDD: 負の出現を省略、疎な論理関数に向いてる

    • 論理関数からBDD(もしくはZDD)を作りたい場合

      • BDTを作ってから圧縮すれば、当然作れる
      • ただ、この圧縮を毎回やってると計算量/メモリ量が大変なことになる
      • なので、直接論理式から圧縮されたBDDを生成したい
      • やりかた
        • ボトムアップ方式: 各変数を小さいBDDとして、二つのBDD同士をAND,NOT,OR演算で組み合わせて最終的なBDDを作る
        • トップダウン方式: BDTを作る過程で、（1を使った回数を数えたりして）作りながら圧縮していく

    • 離散構造処理

      離散構造処理

      フレームワーク 離散構造処理技術 = + 構造とは ...

      1/3/2023

      技術のフレームワーク上では、BDD,ZDD等の決定グラフは「索引構造」にあたる

      • 論理演算、数え上げ、線形関数最大化、サンプリングなどの「基本演算」のやりかた
        • shannon decompositionで分解して、常に1/0を返すffにたどり着くまで再帰的に演算していく
        • Shannon Decomposition: fa=(¬xi∧fa0)∨(xi∧fa1)f_a = (\lnot x_i \land f_{a0}) \lor (x_i \land f_{a1})
          • 要は、二分木の一分岐を数学的に表したもの
          • faf_aとfa′f_{a\prime}の演算を、decompositionした上で再帰的にうことができる

    • 応用先

      • 初期は集積回路の設計問題のためのアルゴリズム
      • 最近は処理能力の向上によって、めちゃでかいBDD

        BDD

        二分決定 = 0/1の組み合わせに対して0/1を返す物 論理関数をBDDで表せる https://ja.wikipedia.org/wiki/二分決定図 より BDDで、AND, OR, XORなどが表現できる ...

        1/3/2023

        が扱えるように
        • 経路探索
        • スーパーマーケットの売り上げデータから良く売れる商品パターンを探す
        • 交通事故データーから危険な要素の組み合わせを調べる
      • 組み合わせ爆発お姉さん

        組み合わせ爆発お姉さん

        https://www.youtube.com/watch?v=ge8vy4tc_kQ で3,4回引用されてた 大人気 なんなら製作した人が、まさかのの講師だった 教授 良く考えればまさかでもないか のの恐ろしさがわかる ...

        1/3/2023

        問題の解法もZDDを使う
        • blu3mo.iconn=26までの世界記録を争う話がすごい楽しそうw #離散アルゴリズム 情報科学の達人.icon

    Backlinks

    • 影響最大化問題

      影響最大化問題

      と情報伝達が与えられて、「影響拡散」σ(S)σ(S)を最大化させる σ(S)σ(S)は複雑なのでBDDでは解けない([NP困難]])が、1−1/e1-1/e[[近似]は可能 #近似アルゴリズム あるノードSから別のノードへのパスの集合は起こす なので、これをに落とし込むことによって回避 技術のパターン(フレームワーク)に沿う 決定グラフ（BDD含む）のを用いれば、σ(S)の最大化ができる #離散アルゴリズム...

      1/3/2023

    • 離散構造処理

      離散構造処理

      フレームワーク 離散構造処理技術 = + 構造とは 例: (ZDD, とか) ただの「を表す」だったものを、圧縮して扱いやすくした「」が、ZDDなど 基本演算とは 索引構造を扱う演算 ex: 決定グラフの基本演算: 論理演算、数え上げ、線形関数最大化、サンプリング、etc 応用する方法: 問題を既知の索引構造に落とし込んで、それに対していろいろな基本演算を組み合わせる #離散アルゴリズム...

      1/3/2023

    • BDD

      BDD

      二分決定 = 0/1の組み合わせに対して0/1を返す物 論理関数をBDDで表せる https://ja.wikipedia.org/wiki/二分決定図 より BDDで、AND, OR, XORなどが表現できる 変数の数nに比例する大きさのBDDになる ...

      1/3/2023

    Interactive Graph

    BDDグラフ/論理関数/簡約化/圧縮/ZDD/冗長/計算量/メモリ量/論理式/ボトムアップ/トップダウン/フロンティア法離散構造処理/決定グラフ/再帰/交通事故組み合わせ爆発お姉さん/グラフ理論/関数グラフ/統計グラフKinetoの弾性同期アルゴリズムNoSQLScrapboxのグラフ時系列表示Scrapboxは言語が持つ構造に沿って情報を管理できるグラフの性質検査グラフ型ToDoアプリ凝集型クラスタリング性質検査組み合わせ的相関検定関数型言語離散アルゴリズム離散構造データ構造影響最大化問題AtCoderで困ったらアニメーションタスクを書き出して漸進的に上に登る作業管理レンダリング画像処理の近似計算競技プログラミング計算機のエネルギー消費公理東大1S1数理科学基礎：微分積分<論文ログ> 技術と芸術が不可分な新たな表現様式「デバイスアート」GKADC言語/索引構造/基本演算/索引/二分木mock upモデリング言語モデル/湊 真一/組み合わせ爆発/計算時間