问题标签 [binary-decision-diagram]

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

背景：我在 Python 中看到了一些工具来完成这项任务，例如，带有scikit-learn 的决策树 (DTs) ，但我还没有看到任何用于 BDD 的工具。

例如，我想做的是以下内容：

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

问题：如何从使用 Python 包dd建模的二元决策图中计算最小割集 (MCS) ？

定义：简而言之，基于下面的示例，MCS是导致输出 1 的一组最小且唯一的事件。

例子：

给定图中的二元决策图：

只有三个 MCS：

1. {BE1 & BE2}
2. {BE1 & BE3 & BE4}
3. {BE1 & BE3 & BE5}

笔记：

• 割集是{BE1 & BE2 & BE3 & BE4}，但它不是最小的，因为它是由第一个和第二个割集组成的。
• 割集仅由输出为 1 的节点组成。因此，MCS 是 {BE1 & BE3 & BE4} 而不是 {BE1 & ¬BE2 & BE3 & BE4}。

对于 BDD，您可以使用以下代码（基于此出版物）：

输出应该是这样的：

我正在尝试以以下格式打印决策树的输出： 在此处输入图像描述

我将决策树存储为嵌套字典。我正在尝试对字典使用嵌套循环但没有结果。

在此处输入图像描述

请让我知道如何实现这一目标的任何想法？

输出必须看起来像这样

二元决策图 (BDD)

二叉搜索树 (BST)

上面的代码显示了如何创建 BST。但是，我希望我的程序表现得像 BDD 图像中显示的真值表。

两张图的区别：

1. BDD 图像中的虚线表示“0”，实线表示用户输入中的“1”。
2. 对于 BST，当用户输入小于根节点时，它代表左树。
3. BDD 的根节点是字符串“x1”，而 BST 的根节点是 int 8。

例如，如果用户输入字符串“000”、“011”、“110”和“111”，则这些叶节点将具有字符串“1”。

***输入将附加到名为值的字符串向量中。因此，values[0] 代表“000”等等。***

我的问题是：

1. 我应该如何重写ordered_insertion_tree 函数？最初我使用 int 来比较值，但现在它已更改为 std::string ，我不知道如何进行比较。
2. 如何更改节点的值？从代表第一个整数的“x1”，到代表n个整数的“x2”...“xn”，最后到代表真值表的0/1。

感谢您的阅读！

我正在使用 CUDD C++ 接口。我发现关于 C++ 库的信息非常少，但对于 C 语言来说非常详尽和丰富。

我有几个问题：

1. 如何获取 BDD 节点的两个子节点？C++ 接口的 C 中 Cudd_T(node) 和 Cudd_E(node) 的对应物是什么？
2. C++ 接口中 Cudd_NodeReadIndex(node) 的对应物是什么？

提前谢谢！

我生成了一个 if else 形式的决策树。有什么方法可以将它转换为 sklearn 中的树形，以便我可以在树上使用各种其他函数，例如 accuracyscore()？

我知道用 BDD/CuDD 描述组合电路很常见。但是是否可以将 BDD 用于 DFF/Latch 等时序逻辑电路？似乎不可能？或者可能只是忽略 CK/D 时序要求并将它们视为简单逻辑？我相信合成算法使用了一些技术来处理

有什么相关的论文/书吗？来自伯克利的 ABC 包裹会这样做吗？