在BDD表示的关系中扩展查找唯一元组

Question

将{<1,2>,<1,3>,<1,7>,<0,4>}视为关系R的元组集合.现在考虑R(通过其隶属函数)表示为BDD.也就是说,表示R的BDD取决于变量{x1,x2,y1,y2,y3},其中{x1,x2}用于表示每个元组的第一个元素,{y1,y2,y3}用于表示第二个要素.

现在,考虑在第一个元素中查找具有唯一值的元组集的问题.对于上面的关系,该集合将是{<0,4>}.所有其他元素都被丢弃,因为它们是第一个组件中具有1的多个值.

作为第二个例子,考虑与元组{<1,2>,<1,3>,<1,7>,<2,3>,<2,5>,<0,4>}的关系.在这种情况下,预期结果仍为{<0,4>},因为2作为第一个元素出现不止一次.

该问题还可以被视为抽象出变量{y1,y2,y3},使得仅保留{x1,x2}的唯一值.利用该结果,可以通过计算所得BDD与输入BDD的结合来重建预期关系.

总之,问题是:哪些是必须在R的表示上执行的BDD操作,以获得仅具有唯一元组的BDD.

请注意,这是此问题的一般化

编辑1: 以下代码反映了我到目前为止的实现.但是,我想知道是否有可能获得更高效的版本.为简单起见,我故意省略了计算表的处理(这对于获得更好的时间复杂度至关重要).另外,我使用&,| 而且!表示对BDD的连接,分离和补充操作.

BDD uniqueAbstract(BDD f, BDD cube) {
  if ((f.IsZero() || f.IsOne()) && !cube.IsOne())
    return zero();
  BDD T = high(f);
  BDD E = low(f);
  if(level(f) == level(c)) { // current var is abstracted
    BDD uniqueThen = uniqueAbstract(T, high(c));
    BDD existElse = existAbstract(E, high(c));

    BDD existThen = existAbstract(T, high(c));
    BDD uniqueElse = uniqueAbstract(E, high(c));

    return (uniqueThen & !existElse) | (uniqueElse & !existThen)
  } else {
    BDD uniqueThen = uniqueAbstract(T,c);
    BDD uniqueElse = uniqueAbstract(E,c);
    return ite(top(f), uniqueThen, uniqueElse);
  }
}

编辑2:尝试三种不同的实现后,仍然存在一些性能问题.让我来描述其中的三个.

1. AC实现我的方法,让我称之为参考实现4.
2. 用户在接受的答案3中提出的实施方案.
3. 两者之间的混合方法和可用的2.

此更新的目的是分析使用这三种方法的结果.由于时间测量在此时似乎具有误导性来判断它们,我决定评估不同措施的实施.

• 递归调用
• 缓存命中
• 抽象简单.在不需要存在抽象的情况下解决函数调用的次数.
• Abstract complex:解决函数调用需要存在抽象的次数.
• 存在摘要:对存在抽象的调用次数.

实现结果1:(21123 ms):唯一抽象统计:递归调用:1728549.000000缓存命中:638745.000000非抽象:67207.000000抽象简单:0.000000抽象复杂:0.000000存在摘要:1593430.000000

执行结果2 :(运行时间:54727 ms)独特抽象统计:递归调用:191585.000000缓存命中:26494.000000抽象简单:59788.000000抽象复杂:12011.000000存在摘要:24022.000000

实施结果3 :(运行时间:20215毫秒)独特抽象统计:递归调用:268044.000000缓存命中:30668.000000抽象简单:78115.000000抽象复杂:46473.000000存在摘要:92946.000000

编辑3:在实施ITE 5的每个逻辑操作后获得以下结果.

1. uniqueAbstractRecRef(21831 ms)唯一抽象统计:总调用:1723239优化调用:0总存在抽象调用:30955618存在唯一抽象调用abstract:2385915总调用次数:3574555在总时间中,uniqueAbstractRecRef需要4001 ms(12.4%)

2. uniqueAbstractSERec(56761 ms)独特抽象统计:总调用:193627优化调用:60632存在的抽象调用总数:16475806存在唯一抽象调用abstract:24304总调用次数:1271844在总时间中,uniqueAbstractSERec需要33918 ms(51.5%)

3. uniqueAbstractRec(20587 ms)唯一抽象统计:总调用:270205优化调用:78486存在的抽象调用总数:13186348存在唯一抽象调用abstract:93060总调用次数:1256872在总时间中,uniqueAbstractRec需要3354 ms(10.6%)

Answer 1

如果变量以 x1 和 x2 位于 BDD 顶部的方式排序，则存在简单且有效的解决方案。

考虑 BDD 作为第二个例子。

您可以（按广度优先顺序）遍历它的前两层以获得四个子 BDD。每一种可能的组合都有一个x1,x2。其中三个子 BDD 的根为 a y1，第四个为空（常量 False）。

现在，您可以计算每个子 BDD 中的元素数量（算法 C，来自 Knuth 的第 4 卷分册 1，位技巧与技术；二元决策图）。

如果子 BDD 中的元素数量大于 1，则将其删除（从父节点直接到 的快捷方式False），否则保持原样。

通过在计算元素时记住部分结果，可以单遍运行该算法。