二进制决策图：从树压缩到采样

作者：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