标签: binary-decision-diagram

简化有序二元决策图(ROBDD)是多变量布尔函数的有效数据结构f(x1,x2,...,xn).我想获得一个直觉如何,他们是有效的.

例如,对于数据压缩,我们知道具有低熵的数据(一些符号比其他符号更频繁地出现,多次重复)可以很好地压缩,而完全随机数据不能被压缩.

是否有类似的直觉来估计ROBDD如何有效地表示给定的布尔公式？有关此主题的任何文献(最好是在线)？

我们认为位矩阵(nxm)是包含n行的大小为m的常规数组整数.

我查看了Hacker's Delight和其他来源,我发现的算法是相当专业的:方形矩阵的大小为2,8x8,32x32,64x64(这是正常的,因为机器是这样构建的).

我想到了一个更通用的算法(对于任意的n和m),在更糟糕的情况下,它是预期的复杂性(我认为),但是对于包含大多数相似列的矩阵,或者比那些更多的零,算法似乎有点更有趣(在极端情况下,如果矩阵一遍又一遍地包含相同的线,则它是线性的).它遵循一种二元决策图操作.

输出不是转置矩阵,而是压缩转置矩阵:对列表(V,L),其中L是int_m,表示应该包含int_n的转置矩阵的行(通过设置相应位置的位) V.没有出现在任何一对中的转置矩阵的线用0填充.

例如,对于矩阵

1010111
1111000
0001010

有转置

110
010
110
011
100
101
100

算法输出(010,0100000)(011,0001000)(100,0000101)(101,0000010)(110,1010000),一个读取对(100,0000101),意思是"值100放在第5和转置矩阵的第7行".

这是算法(用伪OCaml/C编写)和上述例子中算法进展的图片.

我们将根据三元组(index_of_current_line,V,L)运行,这是类型的(int, int_n, int_m),其中int_n是n位宽整数的类型,并且int只是一个足够容纳n的机器整数.该函数获取这些三元组的列表,矩阵,行数和输出的累加器(对的列表(int_m,int_n))并在某个时刻返回该累加器.

list of (int_n, int_m) transpose(list of triple t, 
                                int_m[n] mat, 
                                int n,  
                                list of (int_n, int_m) acc)

转置函数的第一个调用是

transpose([(0, 0, 2^m-1)], mat, n, []).

取"&","|" "xor"是通常的逐位操作

transpose(t, mat, n, acc) =
 match t with 
  | [] -> (* the list is empty, we're done *)
    return acc
  | (i, v, l)::tt …

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

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

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

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

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

如果 F 和 G (ZDDs) 没有共同的组合，只需将它们合并即可完成加法 (F + G)。当它们包含一些常见的组合时，我们计算以下公式：(F + G) = S + (Cx2)，其中 C = F ? G, S = (FUG) \ C …

关于二元决策图的背景可以在维基百科上找到BDD.

最简单的方法是构建BDT(二进制决策树),然后根据两个规则减少它:
- 合并任何同构子图.
- 消除两个孩子同构的任何节点.
但是与BDD相比,BDT存在一个主要问题.有没有办法在不首先构建BDT的情况下构建BDD？

如何实现二元决策图（BDD）？我想基于文化算法和 BDD 的电路故障检测来实现 BDD 的最小化。

计算两个零抑制二元决策图的连接的算法是什么？

我现在已经搜索了几个小时,我找不到它.据我所知,它并不在Knuth的书中,尽管它确实给出了结果的定义.

我宁愿不必涉及任何具体的实施; 我发现实施细节非常分散注意力.

ZDDs的加入f和g是{ a ? b | a ? f and b ? g }

将{<1,2>,<1,3>,<1,7>,<0,4>}视为关系R的元组集合.现在考虑R(通过其隶属函数)表示为BDD.也就是说,表示R的BDD取决于变量{x1,x2,y1,y2,y3},其中{x1,x2}用于表示每个元组的第一个元素,{y1,y2,y3}用于表示第二个要素.

现在,考虑在第一个元素中查找具有唯一值的元组集的问题.对于上面的关系,该集合将是{<0,4>}.所有其他元素都被丢弃,因为它们是第一个组件中具有1的多个值.

作为第二个例子,考虑与元组{<1,2>,<1,3>,<1,7>,<2,3>,<2,5>,<0,4>}的关系.在这种情况下,预期结果仍为{<0,4>},因为2作为第一个元素出现不止一次.

该问题还可以被视为抽象出变量{y1,y2,y3},使得仅保留{x1,x2}的唯一值.利用该结果,可以通过计算所得BDD与输入BDD的结合来重建预期关系.

总之,问题是:哪些是必须在R的表示上执行的BDD操作,以获得仅具有唯一元组的BDD.

请注意,这是此问题的一般化

编辑1: 以下代码反映了我到目前为止的实现.但是,我想知道是否有可能获得更高效的版本.为简单起见,我故意省略了计算表的处理(这对于获得更好的时间复杂度至关重要).另外,我使用&,| 而且!表示对BDD的连接,分离和补充操作.

BDD uniqueAbstract(BDD f, BDD cube) {
  if ((f.IsZero() || f.IsOne()) && !cube.IsOne())
    return zero();
  BDD T = high(f);
  BDD E = low(f);
  if(level(f) == level(c)) { // current var is abstracted
    BDD uniqueThen = uniqueAbstract(T, high(c));
    BDD existElse = existAbstract(E, high(c));

    BDD existThen = existAbstract(T, high(c));
    BDD uniqueElse = uniqueAbstract(E, high(c));

    return (uniqueThen & !existElse) | (uniqueElse & !existThen)
  } else {
    BDD uniqueThen = uniqueAbstract(T,c);
    BDD uniqueElse = …

是否可以从数据中学习二元决策图（BDD）（以机器学习的方式）？如果是这样，怎么办？

背景：我在 Python 中看到过一些工具可以在例如带有scikit-learn 的决策树（DT）中完成此任务，但我还没有看到任何用于 BDD 的工具。

举个例子，我想做的事情如下：

前三列对应于“输入”数据集（xi），标签为（y）。N 对应于计数，您可以使用后者来计算准确性。请注意，这不是割集矩阵。在中间，你可以看到一个对应的BDD（这是我想要获得的图），在右边是一个对应的DT。

是否有一个软件包(最好是应用程序,而不是库)从给定的真值表(以某种文本格式)创建精简二阶决策图(ROBDD)？

我正在使用 CUDD C++ 接口（https://github.com/ivmai/cudd），但几乎没有关于这个库的信息。我想知道如何根据一个变量的值删除它。

例如，我现在将下一个表存储在bdd：

|-----|-----|-----|
|  x1 |  x2 |  y  |
|-----|-----|-----|
|  0  |  0  |  1  |
|-----|-----|-----|
|  0  |  1  |  1  |
|-----|-----|-----|
|  1  |  0  |  1  |
|-----|-----|-----|
|  1  |  1  |  0  |
|-----|-----|-----|

我想bdd根据 x2 的值将前一个表分成两个单独的 s ，然后删除该节点：

如果x2 = 0：

|-----|-----|
|  x1 |  y  |
|-----|-----|
|  0  |  1  |
|-----|-----|
|  1  |  1  | …

在尝试在Windows下编译jinc并快速运行数百个编译器错误之后,我正在寻找一个可以为windows构建的高质量BDD库.最好是C或C++,但只要我能绑定它,我很高兴.

我在 haskell 程序中使用决策图库。为此，我想声明 2 种不同的（新）类型来跟踪我正在处理的决策图。我使用的库是 cudd，决策图基类型有一个 DdNode，但我的问题仅与 Haskell 相关。

newtype Bdd = ToBdd Cudd.Cudd.DdNode
newtype Zdd = ToZdd Cudd.Cudd.DdNode

通常我想在调用函数时区分它们，但现在我想使用一个不必区分这两种类型的函数。我主要尝试通过 3 种不同的方式来解决这个问题：

data Dd = ToBdd Bdd | ToZdd Zdd

printDdInfo :: Dd -> IO()
printDdInfo (ToZdd dd) = do
    putStrLn "Hello, zdd!"
    Cudd.Cudd.cuddPrintDdInfo manager dd
printDdInfo (ToBdd dd) = do
    putStrLn "Hello, bdd!"
    Cudd.Cudd.cuddPrintDdInfo manager dd

printDdInfo :: Either Bdd Zdd -> IO()
printDdInfo (ToZdd dd) = do
    putStrLn "Hello, zdd!"
    Cudd.Cudd.cuddPrintDdInfo manager dd
printDdInfo (ToBdd dd) = do …