Gemma 4 12B本地部署全攻略：从量化选型到FastGPT接入
2026/10/8 18:00:05
ZDD（零抑制决策图）
082零抑制决策图
5W1H
| 维度 | 说明 |
|---|---|
| What（是什么） | 零抑制决策图（Zero-Suppressed Binary Decision Diagram，ZDD）是一种用有向无环图表示集合族（F ⊆ 2^{1…n}）的数据结构，由 Minato 于 1993 年提出。 |
| Why（为什么） | 传统 BDD 对稀疏集合族（如子集枚举、组合优化问题）非常低效。ZDD 通过"零抑制规则"消除 high 子节点为假的节点，使稀疏集合的表示极度紧凑。 |
| Who（谁） | 原创者：Shin-ichi Minato（1993）。理论来源：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 table）：
zdd_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 -std=c99 -Wall编译无警告无错误。 - 节点上限 256，变量从 1 开始编号。
- 操作深度有限（测试用例均为小规模），不需要运算缓存（memo table for operations）。
验收标准
| 编号 | 测试描述 | 期望结果 |
|---|---|---|
| TC-01 | singleton(1)的count | 1（集合{1}1 个） |
| TC-02 | union(singleton(1), singleton(2))的count | 2（集合{1}和{2}） |
| TC-03 | intersect({1,2 的子集族}, {2,3 的子集族})的count | 2（{∅, {2}}） |
| TC-04 | 3 变量全子集族count | 8（2^3） |
| TC-05 | 0-terminal count和1-terminal count | 分别为 0 和 1 |
| TC-06 | singleton(1)的节点结构 | var=1, hi=1-terminal, lo=0-terminal |
| TC-07 | find_or_create(1, ZDD_ZERO, ZDD_ONE) | 返回ZDD_ONE（零抑制消除） |
| TC-08 | union(F, F)与F的count相同 | count相等（幂等性） |
关键设计说明
ZDD 与 BDD 的区别
BDD 消除规则：hi == lo 时消除（冗余测试消除） ZDD 消除规则：hi == 0-terminal 时消除（零抑制规则）ZDD 对稀疏集合族的压缩来自：当一个集合不包含某变量时，hi 分支为 0，对应节点被零抑制消除，节省大量空间。
集合族的语义
0-terminal：空集族（不含任何集合，等价于false）1-terminal：含空集的族{∅}（等价于true）- 内部节点
(v, hi, lo)表示：hi分支：包含变量v的所有集合（再加上v）lo分支：不包含变量v的所有集合
计数公式
count(0-terminal) = 0 count(1-terminal) = 1 count(v, hi, lo) = count(hi) + count(lo)理由：内部节点将集合族分为两个不相交子族，故直接相加。