6

I'm trying to implement univariate polynomials using ZDDs, as suggested in a comment in an other question.

I've read the paper of S. Minato(you may download it here), but I don't understand how to implement the operations on these ZDDs.

この論文の考え方は、変数として使用して多項式を表すことができるということx^(2^i)です。たとえば、 のx^5 + x^3 + xように書き換えることができます。変数x^4x^1 + x^2x^1 + x^1ごとにノードを作成x^(2^i)し、乗算された "1 エッジ" 変数と加算された "0 エッジ" 変数を接続すると、その多項式を表すグラフを簡単に取得できます。 . ZDD は、グラフに何らかの条件を適用するこの種のグラフです (詳細については、湊の記事と BDD に関するウィキペディアのページを参照してください)。

係数は、2 のべき乗の合計を使用して同様に表すことができます (たとえば、5 = 2^2 + 2^0すべて2^iが変数であり、ノードは同じ方法で 1 エッジと 0 エッジで接続されます)。

さて、私の問題は、2 つの ZDD を加算するアルゴリズムです。アルゴリズムは非常に単純に見えます。

F と G (ZDDs) に共通する組み合わせがない場合、それらをマージするだけで加算 (F + G) を完了できます。それらにいくつかの一般的な組み合わせが含まれている場合、次の式を計算します: (F + G) = S + (Cx2)、ここで C = F ∩ G、S = (FUG) \ C . このプロセスを繰り返すことで、最終的に共通の組み合わせがなくなり、手順が完了します。

問題は、「C」と「S」を効率的に見つけるにはどうすればよいかということです。

著者は乗算のコードを提供していますが、以前のアルゴリズムを実装すれば、コードは実際には簡単です。また、これらのアルゴリズムは提供されていないため、乗算も「役に立たない」ものです。

また、「マージ」ZDD の概念は十分に説明されていませんが、変数の順序が一貫していなければならないという事実を考慮すると、グラフをマージする方法は 1 つしかなく、この順序を維持するためのルールはおそらく単純です。十分です（まだ形式化していませんが、これらが何であるかについては大まかな考えがあります）。

4

1 に答える 1

5

「マージ」とは、ミナトがユニオン（アルゴリズム）を意味します。これは、例からもわかります。

4 * y     = { { 2^2, y } }
x         = { { x } }
4 * y + x = { { 2^2, y }, { x } }

内部セットは製品を表し、ZDD 全体はそれらの製品の合計を表すという考え方です。そのため、さらにいくつかのセットで OR (別名ユニオンまたはマージ) すると、効果的に追加されます。

完全な合計アルゴリズムは、実際には(A xor B) + 2 * (A and B)(再帰的に) おなじみのビットごとの加算アルゴリズムと同等ですが、 のようxorに書かれてい(A or B) without (A and B)ます。

これはまた、一般的な組み合わせがない場合に単純に和集合を取っても問題ない理由を明らかにしていA and Bます。A xor BA or B

OR、AND、XOR、および BUTNOT のアルゴリズムについては、The Art of Computer Programming volume 4、セクション 7.1.4で詳しく説明されています(質問 199 への回答が関連しています)。それらすべての一般的な考え方は、変数を含むすべてのセットと変数を含まないvすべてのセットを別々に表す 2 つのサブグラフを考慮することです(一方または両方の引数で が最上位の変数である場合、どちらも簡単に見つかります)。低い子と高い子または入力自体)、結果を結合します。vv

Union(F, G) =
  if (F = ∅) return G
  if (G = ∅) return F
  if (F = G) return F
  if (cache contains "F ∪ G" or "G ∪ F")
    return cached value

  if (F.v = G.v) result = MakeNode(F.v, F.lo ∪ G.lo, F.hi ∪ G.hi)
  if (F.v > G.v) result = MakeNode(G.v, F ∪ G.lo, G.hi)
  if (F.v < G.v) result = MakeNode(F.v, F.lo ∪ G, F.hi)

  cache result as "F ∪ G"
  return result

Intersect(F, G) =
  if (F = ∅ or G = ∅) return ∅
  if (F = G) return F
  if (cache contains "F ∩ G" or "G ∩ F")
    return cached value

  if (F.v = G.v) result = MakeNode(F.v, F.lo ∩ G.lo, F.hi ∩ G.hi)
  if (F.v > G.v) result = F ∩ G.lo
  if (F.v < G.v) result = F.lo ∩ G

  cache result as "F ∩ G"
  return result
于 2012-10-03T11:03:25.793 に答える