ZDD零抑制决策图082零抑制决策图5W1H维度说明What是什么零抑制决策图Zero-Suppressed Binary Decision DiagramZDD是一种用有向无环图表示集合族F ⊆ 2^{1…n}的数据结构由 Minato 于 1993 年提出。Why为什么传统 BDD 对稀疏集合族如子集枚举、组合优化问题非常低效。ZDD 通过零抑制规则消除 high 子节点为假的节点使稀疏集合的表示极度紧凑。Who谁原创者Shin-ichi Minato1993。理论来源Donald Knuth《The Art of Computer Programming》第四卷 Fascicle 1B。When何时ZDD 适用于需要高效枚举、计数子集族的场合尤其是 n 较大但实际集合稀疏时。Where在哪里应用于组合优化、图路径枚举、布尔函数压缩表示、数据挖掘中的频繁项集挖掘。How如何节点结构{var, hi, lo}零抑制规则若hi 0-terminal消除节点直接返回lo操作通过 Shannon 展开递归实现union、intersect计数通过记忆化递归count(v,hi,lo) count(hi) count(lo)。需求定义功能需求ZDD 节点池初始化预分配固定大小256 节点的静态节点池编号 0 为 0-terminal编号 1 为 1-terminal。零抑制唯一表unique tablezdd_find_or_create(var, hi, lo)实现零抑制规则若hi ZDD_ZERO直接返回lo。节点共享线性搜索确保相同{var, hi, lo}的节点只存一份。singleton(var)创建单元素集合族{{var}}的 ZDD。union(a, b)计算两个 ZDD 表示集合族的并通过 Shannon 展开递归实现。intersect(a, b)计算两个 ZDD 表示集合族的交通过 Shannon 展开递归实现。count(node)通过记忆化递归计算 ZDD 表示的集合数量。all_subsets(vars, n)辅助函数构建 n 个变量的全子集族 ZDD用于测试。非功能需求不使用math.h或-lm。C99 标准gcc -stdc99 -Wall编译无警告无错误。节点上限 256变量从 1 开始编号。操作深度有限测试用例均为小规模不需要运算缓存memo table for operations。验收标准编号测试描述期望结果TC-01singleton(1)的count1集合{1}1 个TC-02union(singleton(1), singleton(2))的count2集合{1}和{2}TC-03intersect({1,2 的子集族}, {2,3 的子集族})的count2{∅, {2}}TC-043 变量全子集族count82^3TC-050-terminal count和1-terminal count分别为 0 和 1TC-06singleton(1)的节点结构var1, hi1-terminal, lo0-terminalTC-07find_or_create(1, ZDD_ZERO, ZDD_ONE)返回ZDD_ONE零抑制消除TC-08union(F, F)与F的count相同count相等幂等性关键设计说明ZDD 与 BDD 的区别BDD 消除规则hi lo 时消除冗余测试消除 ZDD 消除规则hi 0-terminal 时消除零抑制规则ZDD 对稀疏集合族的压缩来自当一个集合不包含某变量时hi 分支为 0对应节点被零抑制消除节省大量空间。集合族的语义0-terminal空集族不含任何集合等价于false1-terminal含空集的族{∅}等价于true内部节点(v, hi, lo)表示hi分支包含变量v的所有集合再加上vlo分支不包含变量v的所有集合计数公式count(0-terminal) 0 count(1-terminal) 1 count(v, hi, lo) count(hi) count(lo)理由内部节点将集合族分为两个不相交子族故直接相加。