6

我正在尝试使用 ZDD 实现单变量多项式，正如另一个问题的评论中所建议的那样。

我读过 S. Minato 的论文（你可以在这里下载），但我不明白如何在这些 ZDD 上实现操作。

论文中的想法是多项式可以用x^(2^i)变量来表示。例如x^5 + x^3 + x可以重写为x^4x^1 + x^2x^1 + x^1，如果您为每个x^(2^i)变量创建节点并与相乘的“1-edge”变量和相加的“0-edge”变量连接，您可以轻松获得表示该多项式的图形. ZDD 是在图上强制执行某些条件的此类图（有关更多信息，请阅读 Minato 的文章和关于 BDD的维基百科页面）

系数可以类似地使用 2 的幂和来表示（例如5 = 2^2 + 2^0等。每个2^i都是变量，并且节点以相同的方式与 1 和 0 边连接）。

现在，我的问题是添加两个 ZDD 的算法。算法看起来很简单：

如果 F 和 G (ZDD) 没有共同的组合，则加法 (F + G) 只需合并即可完成。当它们包含一些常见的组合时，我们计算以下公式： (F + G) = S + (Cx2)，其中 C = F ∩ G, S = (FUG) \ C 。通过重复这个过程，最终会用尽常见的组合并完成该过程。

问题是：如何有效地找到“C”和“S”？

作者提供了乘法的代码，但是一旦你实现了前面的算法，代码实际上是微不足道的。而且由于没有提供这些算法，因此乘法运算也是“无用的”。

此外，“合并”ZDD 的概念也没有得到很好的解释，尽管考虑到变量的顺序应该是一致的，只有一种方法可以将图合并在一起，而且维持这种顺序的规则可能很简单够了（我还没有将它们正式化，但我对它们有一个粗略的了解）。

4

1 回答 1

5

使用“合并”，Minato 表示联合（算法）。您也可以从示例中看到这一点：

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

这个想法是内部集合代表产品，整个 ZDD 代表这些产品的总和，所以如果你只是在更多集合中进行 OR（也称为联合或合并），它们就会被有效地添加。

The complete summation algorithm actually just does (A xor B) + 2 * (A and B) (recursively) which is equivalent to the familiar bitwise addition algorithm, but the xor was written as (A or B) without (A and B).

That also makes it obvious why simply taking the union is OK when there are no common combinations - if A and B is empty, A xor B is the same as A or B and the "carry" is zero.

The algorithms for OR, AND, XOR and BUTNOT are explained in detail in The Art of Computer Programming volume 4, section 7.1.4 (the answer to question 199 is relevant). The general idea for all of them is that they consider the two sub-graphs that represent all the sets with the variable v and all the sets without the variable v separately (which are both trivially found if v is the topmost variable in one or both arguments as either the low and high children or the input itself), and then combining the result.

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 回答