boolean-logic - BDD或FDD中“路径”的含义和意义是什么？

Question

我读了一篇名为基于功能决策图的多级逻辑综合的论文，它是关于功能决策图（FDD）的，它是二元决策图（BDD）的一种变体。在这一段中，有一段提到了“路径”：

作为一个重要的结果，可以观察到，即使节点数量几乎相同，与 BDD 相比，我们也减少了路径数量（参见表 1）。由于路径的数量等于规范的两级 RME 的 pi 项的数量，这意味着函数表示的复杂性降低。

我猜“路径”是指 BDD 或 FDD 中从根到终端的道路数量。

例如：

这个例子的路径是9（你可以检查一下）。

我的问题是这个参数或特征“路径”的意义是什么？

Answer 1

是的，路径是从根到叶的任何单一方式。粗略地说，决策图中的路径集可以看作是完全描述函数的最小变量值集。

例如，您可以绘制一个保留所有变量和所有路径的决策图。您可以看到其中一些是冗余的（可能从一个节点两个链接都到同一个节点）。在这种情况下，我们正在浪费内存。

决策图的整个目标是以最紧凑和最有效（操作明智）的方式表示布尔函数。作者很高兴，因为他们找到了一种更紧凑的方式，不知道效率。