影響最大化問題

Last updated Unknown Edit Source

• 有向グラフと情報伝達確率が与えられて、「影響拡散」$σ(S)$を最大化させる
  • $σ(S)$は複雑なのでBDDでは解けない(NP困難)が、$1-1/e$ [近似]は可能 #近似アルゴリズム
• あるノードSから別のノードへのパスの集合は組み合わせ爆発起こす
  • なので、これをBDD

    BDD

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

    1/3/2023

    に落とし込むことによって回避
    • 離散構造処理

      離散構造処理

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

      1/3/2023

      技術のパターン(フレームワーク)に沿う
  • 決定グラフ（BDD含む）の基本演算を用いれば、σ(S)の最大化ができる

#離散アルゴリズム