logo标签列表

零压缩二叉决策图计算连接的算法

algorithmbinary-decision-diagram
5
算法是如何计算两个零压缩二进制决策图的联接？
我已经搜索了几个小时，但仍然找不到。根据我所知，Knuth的书中也没有这个算法，尽管它确实给出了结果的定义。
我不想浪费时间去研究具体的实现细节，因为这些细节会分散我的注意力。
ZDD的联接是“{ a ∪ b | a ∈ f and b ∈ g }”。
请原谅我，这里的“join”具体指什么？并集？交集？还是其他什么？ - hmakholm left over Monica
@Henning Makholm：不是这样，它是所有来自一个ZDD的集合a和另一个ZDD的集合b的所有组合的并集的集合。 - harold
好的，那超出了我的能力范围。当我学习BDD时，每个BDD都编码了一个单独的集合（由位串组成），而不是一组集合。这可能是一个简化版本。 - hmakholm left over Monica
1个回答
5
在我的《计算机程序设计艺术》第4A卷的副本中，这个确切的问题被提出为7.1.4节中的练习205。它与前两个问题有关，但所有三个问题的答案都在书的后面。您可能想将其作为资源进行检查。 我曾经参加过Knuth几年前的一次演讲，他在讨论ZDD及其算法，包括如何进行join操作。如果您感兴趣，我相信该讲座已被记录并应该在线here。 希望这能帮到你！
谢谢，我忘了看书的那一部分。 - harold
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接