代码之家 › 专栏 › 技术社区 › sirius

BDDs或FDDs中“路径”的含义和意义是什么?

binary-decision-diagram booleanquery boolean-operations boolean-logic

1

sirius · 技术社区 · 7 年前

我读了一篇论文,名叫 Multilevel logic synthesis based on functional decision diagrams ,这是关于功能决策图(FDD),它是二进制决策图(BDD)的一种变体。在这篇文章中,有一段提到了“路径”:

一个重要的结果是,即使我们得到的节点数减少了路径与…相比 BDD(见表1)。因为路径数等于规范二级RME的pi项,这意味着函数表示的复杂性。

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

例如:

本例的路径是9(您可以对此进行检查)。

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

1 回复 | 直到 7 年前

1

Lorenzo 7 年前

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

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

决策图的全部目标是以最紧凑和最有效(操作方面)的方式表示布尔函数。作者们很高兴,因为他们找到了一种更简洁的方法,不知道效率如何。