作者：Julien Clément,Antoine Genitrini
摘要：任何布尔函数都对应于完整的完整二进制决策树。该树又可以以最大的紧凑形式表示为直接非循环图（ textsc {dag}），其中共同子树被分解和共享，仅保留每个唯一子树的一个副本。这产生了着名且广泛使用的结构，称为简化有序二元决策图（ textsc {robdd}）。我们建议重新审视经典压缩过程，以提供一种新的方法来枚举给定大小的 textsc {robdd}，而不考虑完全展开的树和压缩步骤。我们的方法还为 textsc {robdd}的集合提供了一个无人值守的过程。作为副产品，我们为 textsc {robdd}获取一个随机的统一且详尽的采样器，用于给定数量的变量和大小。为了提高效率，我们的算法依赖于预计算步骤。最后，我们提供了一些关键的想法，将方法扩展到其他压缩策略，与 textsc {bdd} s的变体（即 textsc {qbdd} s和 textsc {zbdd} s）相关。
原文标题：Binary Decision Diagrams: from Tree Compaction to Sampling
原文摘要：Any Boolean function corresponds with a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a direct acyclic graph (textsc{dag}) where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (textsc{robdd}). We propose to revisit the classical compaction process to give a new way of enumerating textsc{robdd}s of a given size without considering fully expanded trees and the compaction step. Our method also provides an unranking procedure for the set of textsc{robdd}s. As a by-product we get a random uniform and exhaustive sampler for textsc{robdd}s for a given number of variables and size. For efficiency our algorithms rely on a precomputation step. Finally, we give some key ideas to extend the approach to other strategies of compaction, in relation with variants of textsc{bdd}s (namely textsc{qbdd}s and textsc{zbdd}s).
地址：https://arxiv.org/abs/1907.06743
