使用CUDD的BDD/ZDD交集 [英] Intersection of BDD/ZDD using CUDD

问题描述

我有一些套组合，我想找出两个说一下之间的交集函数.然后我要用ZDD表示相交的结果.

I have some sets of combinations and I want to find out the intersection function between say two of them. Then I want to represent the intersected results in ZDD.

我正在考虑使用 CUDD软件包来做到这一点.

I am thinking about using the CUDD package to do this.

一个例子:

所有具有汉明距离> = 2 和 1100 =

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

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

所有具有汉明距离> = 2 和 0000 =

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

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

集合的相交元素(我想要的):

Intersected elements of the set (what I want):

{0011，0101，0110，1010，1001}

据我了解，我首先需要能够使用布尔函数(例如)表达这些组合集. (f = a b c d)表示它们相应的BDD，将它们转换为ZDD，然后找出交集?有人对 CUDD软件包很有经验，请提供帮助.

From what I understand, I need to be able to express those sets of combinations first, with boolean functions, e.g. ( f = a b c d ) to represent their corresponding BDDs, convert them to ZDDs and then find out the intersection? Someone experienced with the CUDD package please help.

推荐答案

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

Your reasoning is correct. You can first build BDDs corresponding to the two string sets, convert them to ZDDs, and then build the intersection (logical AND).

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

However, you can also first compute the intersection (logical AND) and then translate the result to a ZDD.

但是，不清楚找出交叉路口"是什么意思-您要如何处理?打印出所有元素?计算元素数量?根据您的目标，可能不需要转换为ZDD(或完全使用CUDD).

It is however not clear what you mean by "find out the intersection" - what do you want to do with it? Print out all the elements? Count the number of elements? Depending what what is your aim, the translation to ZDDs may be unnecessary (or the use of CUDD altogether).

这篇关于使用CUDD的BDD/ZDD交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！