binary - 使用 CUDD 的 BDD/ZDD 交集

Question

我有一些组合，我想找出其中两个之间的交集函数。然后我想在 ZDD 中表示相交的结果。

我正在考虑使用CUDD 包来做到这一点。

一个例子：

汉明距离 >= 2且1100 =的所有 4 位字符串

{ 0001, 0010, 0011,0101, 0110, 0111, 1001, 1010, 1011 }

汉明距离 >= 2且0000 =的所有 4 位字符串

{ 0011, 0101, 0110, 1001, 1010, 0111, 1011, 1101, 1110 }

集合的相交元素（我想要的）：

{0011, 0101, 0110, 1010, 1001 }

据我了解，我需要能够首先表达这些组合集，使用布尔函数，例如（ f = abcd ）来表示它们相应的 BDD，将它们转换为 ZDD，然后找出交集？有CUDD包经验的人请帮忙。

Answer 1

你的推理是正确的。您可以先构建两个字符串集对应的 BDD，将它们转换为 ZDD，然后构建交集（逻辑与）。

但是，您也可以先计算交集（逻辑与），然后将结果转换为 ZDD。

然而，不清楚你所说的“找出交叉点”是什么意思——你想用它做什么？打印出所有元素？计算元素的数量？根据您的目标，转换为 ZDD 可能是不必要的（或完全使用 CUDD）。