问题标签 [binary-decision-diagram]

我有使用JavaBDD的 BDD 表示，我需要将其转换为连接范式，以便能够将它与另一个工具结合使用。我想知道实现转换的最佳方法是什么。提取 DNF 似乎很简单（只需提取到“1”的所有路径），但我不确定什么是解决 CNF 的最佳方法。任何想法将不胜感激。

我正在用Java实现。

目前，我正在尝试使用 BDD（二进制决策图）将关系存储在数据结构中。

例如 R={(3,2),(2,0)} 和相应的 BDD：

出于这个原因，我一直在寻找具有 BDD 功能的库来帮助我。

我发现了两种可能性：JavaBDD 和 JDD。

但是在这两种情况下，我都不明白如何将简单的整数编码为 BDD，因为我如何或何时给出整数的值？或者，如果 BDD 用整数表示，这意味着什么？

在这两种情况下，都有如下方法：

或者

我怎样才能像我的例子一样简单地创建一个 BDD？

非常感谢！！

我正在使用 CUDD 包进行 BDD 操作。我想知道是否有人知道传递特定变量顺序以指示程序在构建 BDD 时使用此顺序的方法。我正在使用变量数量相对较少的布尔函数。

事实上，即使有一种方法可以将特定的输入变量传递给程序以作为 BDD 的根，这也符合我的目的。如果有人知道如何做到这一点，那么我将非常感谢您的帮助。我浏览了文档，但没有发现任何与此相关的内容。也许我错过了什么。

我正在使用 Cudd 包http://vlsi.colorado.edu/~fabio/CUDD/ 首先我得到一个错误状态“死计数！=删除”所以我开始调试，我遇到了一个我无法理解的问题。

以下代码将一个十进制值作为输入，它应该使用 nodes_vector 中的变量将相应的 BDD 返回到该十进制值。

在某些情况下，我得到结果节点和 tmp3 节点的参考值为零，但我不明白在我调用“Cudd_ref(tmp3)”后怎么会发生这种情况

我将不胜感激对此的任何解释，以及为什么我会在循环中得到“死计数！=已删除”错误，尽管在该循环的第一次迭代中我没有收到“死计数！=已删除”错误。

将 {<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 与输入的结合来重建预期的关系。

总之，问题是：必须对 R 的表示执行哪些 BDD 操作才能获得仅具有唯一元组的 BDD。

请注意，这是对这个问题的概括

编辑1： 以下代码反映了我到目前为止的实现。但是，我想知道是否有可能获得更高效的版本。为简单起见，我有意省略了计算表的处理（对于获得更好的时间复杂度至关重要）。另外，我使用 &, | 和 ！表示 BDD 上的合取、析取和补码操作。

EDIT2：在尝试了三种不同的实现之后，仍然存在一些性能问题。让我来描述他们三个。

1. 我的方法的 AC 实现，让我称之为参考实现4。
2. 用户 meolic 在接受的答案3中提出的实现。
3. 两者之间的混合方法和可用2。

本次更新的目标是分析一下使用这三种方法的结果。由于此时时间度量似乎会误导判断它们，因此我决定在一组不同的度量上评估实现。

• 递归调用
• 缓存命中
• 抽象简单。无需存在抽象即可解决函数调用的次数。
• 抽象复合体：需要存在抽象解决函数调用的次数。
• 存在抽象：对存在抽象的调用次数。

实现 1 的结果：（21123 毫秒）：唯一抽象统计：递归调用：1728549.000000 缓存命中：638745.000000 非抽象：67207.000000 简单抽象：0.000000 复杂抽象：0.000000 现有抽象：1593430.000000

实现 2 的结果：（运行时间：54727 毫秒）唯一抽象统计：递归调用：191585.000000 缓存命中：26494.000000 简单抽象：59788.000000 复杂抽象：12011.000000 现有抽象：24022.000000

实现 3 的结果：（运行时间：20215 毫秒）唯一抽象统计：递归调用：268044.000000 缓存命中：30668.000000 简单抽象：78115.000000 复杂抽象：46473.000000 现有抽象：92946.000000

编辑 3：根据 ITE 5实施每个逻辑操作后获得以下结果。

1. uniqueAbstractRecRef (21831 ms) 唯一抽象统计：总调用：1723239 优化调用：0 总存在抽象调用：30955618 对存在抽象的唯一抽象调用：2385915 总 ite 调用：3574555 在总时间中，uniqueAbstractRecRef 需要 4001 毫秒 (12.4%)

2. uniqueAbstractSERec (56761 ms) 唯一抽象统计：总调用：193627 优化调用：60632 总存在抽象调用：16475806 对存在抽象的唯一抽象调用：24304 总 ite 调用：1271844 在总时间中，uniqueAbstractSERec 需要 33918 ms (51.5%)

3. uniqueAbstractRec (20587 ms) 唯一抽象统计：总调用：270205 优化调用：78486 总存在抽象调用：13186348 对存在抽象的唯一抽象调用：93060 总 ite 调用：1256872 在总时间中，uniqueAbstractRec 需要 3354 ms (10.6%)

我不知道如何用归约二元决策图 (ROBDD) 解决 8 皇后难题。我用谷歌搜索了它，但找不到问题的良好解释。所以，这里的问题 - 到目前为止，我已经发现 ROBDD 会有 n*n 输入变量或状态。现在，我怎样才能真正创建一个能够解决 8 皇后谜题的 ROBDD 呢？

1. ROBDD 如何找到这个问题的解决方案？
2. 我无法弄清楚上述问题的图形表示
3. 它实际上如何产生最小数量的节点？
4. 输入变量的顺序如何？
5. 它是如何减少的？

解释将帮助我更好地理解问题。

给定一个二元决策图，如何将其转换为真值表？它的确切算法是什么？我已经尝试了很长时间。这是一个可以遵循的示例：

资料来源：维基百科。

（虚线边代表 0；实线边代表 1。）

如何将决策表转换或可视化为决策树图，是否有解决它的算法，或可视化它的软件？

例如，我想在下面可视化我的决策表：http: //i.stack.imgur.com/Qe2Pw.jpg

与固定长度位数组相比，为什么将 16 位有符号整数变量表示为区间（-32768..32767）时性能会显着下降？

检查预处理的 NuSMV/NuXMV 模型可以观察到区间类型转换为枚举。

然而，BDD 的统计数据并未显示任何相关信息。

我正在使用一些名称和其他功能来预测 y（二进制类）。名称特征是名称的子字符串。我正在使用 Python Scikit-learn。

这是 X 的一小部分：

然后我使用 dictvectorization 将 X 向量化为这个......

问题是我完全忘记了新 X 代表什么。而且由于我需要提出一个决策树图，所以我只能得到这些我无法解释的结果。

我的python代码：