2

我正在与（https://github.com/ivmai/cudd）合作，目标是执行以下重复过程：

(1) 输入：（相干，非递减）布尔函数表达式 top = a_1 a_2 a_3...+ x_1 x_2 x_3... + z_1 z_2 z_3...）。我正在使用的布尔值有数千个变量（ai...zj）和数百个术语。

(2) 处理：将布尔值转换为 BDD 以简化最小项或互斥割集（我们在可靠性世界中称之为）的计算。

(3) 输出：取一组我的最小割集（minterms）。通过将 (2) 中找到的所有小项相加来计算顶部事件概率。

我找到了一种使用劳动密集型手动 C 接口来构建布尔值的方法。我还发现了如何使用出色的 tulip-dd Py 界面来实现它，但无法像 cudd 那样进行扩展。

现在我希望通过 cudd 的 C++ 接口，我可以两全其美（我要求太多了吗？）也就是说，tulip-dd 的便利性和 cudd 的可扩展性。所以这里有一些示例代码。我失败的地方是第 3 步，打印出我以前可以在 C 中完成的最小术语。我如何使用 C++ 接口来完成它？！请参阅代码中的注释以了解我的具体想法和尝试。

int main()
{ 


/*DdManager* gbm; /* Global BDD manager. I suppose we do not use this if we use the Cudd type below.*/

/* (1-2) Declare the vars and build the Boolean. Convert Boolean to BDD */
    
    Cudd mgr(0, 0);
    BDD a = mgr.bddVar();
    BDD b = mgr.bddVar();
    BDD c = mgr.bddVar();
    BDD d = mgr.bddVar();
    BDD e = mgr.bddVar();
    BDD top = a*(b + c + d*e);

/* How to print out the equivalent to below, which prints out all minterms and their relevant vars in C. 
But the mgr below has to be a *DManager ? If so, how to convert? */

    Cudd_PrintDebug(mgr, BDD, 2, 4); 
    return 0 
}

谢谢，桂

4

1 回答 1

1

CUDD C++ 类只不过是“DdManager*”和“DdNode*”数据类型的包装器。他们确保您不会意外忘记您正在使用的 Cudd_Ref(..) 或 Cudd_RecursiveDeref(...) *DD 节点。

因此，这些类具有可用于访问基础数据类型的函数。因此，例如，如果您想在“顶部”BDD 上调用“Cudd_PrintDebug”函数，那么您可以通过以下方式执行此操作：

    Cudd_PrintDebug(mgr.getManager(), top.getNode(), 2, 4);

对您的代码的修改很少。

请注意，当使用通过“getNode”函数获得的普通 CUDD DdNode* 时，您必须手动确保不会引入节点计数泄漏。如果您以“只读方式”使用 DdNode，请仅存储与您还存储的 BDD 对象相对应的 DdNode*，并确保 BDD 对象的寿命始终比 DdNode* 指针长，但这不会发生。我只是提到这一点，因为在某些时候您可能想要遍历 BDD 的多维数据集。这些本质上不是保证最小的最小术语。CUDD 中有专门的迭代器来解决这个问题。但是，如果您真的想要 minterms，这可能不是正确的方法。

作为最后一点（在 StackOverflow 的范围之外），您写道“我正在使用的布尔值有数千个变量 (ai...zj) 和数百个术语。 ” - 不能保证将 BDD 与这么多变数是要走的路。但请尝试一下。对于基于 BDD 的方法来说，拥有数千个变量通常是有问题的。您的应用程序可能会或可能不会是此观察的例外。另一种方法可能是将原始表达式的所有小项的搜索问题编码为增量可满足性 (SAT) 解决问题。

于 2020-07-18T20:27:48.623 回答