用CUDD实现BDD/ZDD的交集

Question

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

我正在考虑使用CUDD包来完成这个任务。

举个例子：

所有具有hamming距离>= 2和1100 =的4位字符串

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

所有具有hamming距离>= 2和0000 =的4位字符串

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

集合的交叉元素(我想要的)：

{0011,0101,0110,1010,1001 }

据我所知，我需要能够首先用布尔函数(f=a，b，c，d)来表示那些组合()集合，以表示它们对应的BDD，并将它们转换为ZDD，然后找到交集？有CUDD软件包经验的人，请帮助。

Answer 1

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

但是，您还可以首先计算交集(逻辑和)，然后将结果转换为ZDD。

然而，你所说的“找出十字路口”是什么意思--你想用它做什么呢？把所有元素都打印出来？数数元素的数量？根据您的目标是什么，对ZDDs的翻译可能是不必要的(或者完全使用CUDD )。