JOIss2015-ZDD @bekasa001
- 2. ZDDの簡単な性質 ● 組合せ集合を表す 例) {ab, ac, c} (全体はa b c) ● への経路数が、 組合せ集合の組合せ数。 ● 0, 1で非対称なグラフ 0 1 a b c 1
- 3. 実装の概要 ● も、子を持たないノードとして扱う。 ● 各ノードは 1- 辺の先のポインタ 0- 辺の先のポインタ 1- 辺で接続された親のポインタの集合(std::set) 0- 辺で接続された親のポインタの集合(std::set) を持つ。 ● 1つのグラフは、一番上の頂点へのポインタで表 現される。 0 1
- 4. ● 「0, 1で非対称なグラフ」 ? 「0と1を入れ替えたら面白いかもしれない」 と考えた。 発想
- 5. ● 複数のものを選ぶ組み合わせの集合を表すZDDから、 選ばないものを選ぶ組み合わせの集合を表すZDDを 作ってみる。 例) 全体を a, b, c として、 もとの集合が{ab, ac, c}のときの{c, b, ab} ?これを「反転ZDD」と呼ぶことにする。 反転ZDD
- 10. 反転ZDD ● これらの作業を、上の頂点?辺から順に行うと 上手くいった。 ● これらのことを行っただけでは、新たな等価接 点が生まれる可能性があり、既約ZDDは得られ ない。 ● 計算量は、O(V * N)くらい?(Nは要素数)
- 11. 否定ZDD ● ある組み合わせ集合を表すZDDから、そこでふさわ しくないとされる組み合わせの集合を表すZDDを 作ってみる。 例)全体をa, b, cとして、 {ab, ac, c}に対する{λ, a, b, bc, abc} (λは空の組み合わせ) ?これを「否定ZDD」と呼ぶことにする。
- 12. 否定ZDD ● あるZDDから、その否定ZDDを作るアルゴリズムを考え る。 ● まず、一番下の と を入れ替える。 ● 次に、以下の操作を、上の頂点?辺から順に行う。 0 1
- 18. 否定ZDD ● これらのことを行っただけでは、新たな等価接 点が生まれる可能性があり、既約ZDDは得られ ない。 ● 計算量は、O(V * N)くらい?(Nは要素数)
- 20. 考察 具体例1 反転 否定 否定 反転 0 1 0 1 0 1 0 1 {ab, ac, c} {c, b, ab} {a, abc, b, bc, λ} {bc, λ, ac, a, abc} a b c a b c a b c a b c
- 22. 考察 具体例2 反転 否定 否定 反転 0 1 0 1 {a, b, c, λ} {bc, ac, ab, abc} a b c a b c 0 1 {a, b, c, λ} a b c 0 1 {bc, ac, ab, abc} a b c
- 24. まとめ ● 反転?否定すると、グラフの複雑さが変わることがあ る。以下の場合、複雑になる傾向がある。 否定 : 表している組み合わせの数が多い 反転 : 選ぶ要素の数が多い →反転?否定で得られる4つのZDDのうち、最も 単純であると思われるZDDを扱うのが良い。 ● 反転?否定に関する、美しい性質は見つけられなかっ た。(見つかると思っていたので悲しかった) 例) 反転(or否定)しても、○○の数が変わらない。 例) 反転も否定もしたZDDは、もとのZDDと○○が似てい る。 ● これよりも速いアルゴリズムがあるかもしれない。