Cudd_PrintMinterm，访问乘积总和中的单个最小项

Question

这可能是本论坛常驻 CUDD/BDD 专家 @DCTLib 的问题，但如果其他人有见解，当然欢迎！

考虑给定的最小项，例如： 0--0---0--0---0----11 1 .

我需要单独取每个最小项并将“1”替换为 P(x_i)（我正在处理变量的概率），0 替换为 1-P(x_i)和“-”与 1。然后我将最小项内的因子相乘，P(x_i)...(1-P(x_j)) 并将它们全部加起来以获得顶级事件。（对应于最小项的概率的和积）

我需要一个一个地处理它们的原因是我正在处理大文件，这些文件会破坏 memory.Once 我有超过 80-100 个变量，你在 TB OoM对于整个 minterm 文本文件转储大小。我想取每个最小项，将其添加到运行总和中，并在添加后删除它，如果可能的话。

希望这是明确的，但如果不是，可能需要一些迭代。谢谢，

Answer 1

这里有几个选项：

a) 您似乎已经在 BDD 上有一个输出为 Cudd_PrintMinterm 的文本文件。计算最小项值的总和实际上不是 CUDD 问题。只需解析行 one-by-one 并即时计算总和：

std::ifstream inFile("minterms.txt");
std::string currentLine;
double sumSoFar = 0;
while (std::getline(inFile,currentLine)) {
     // Process the line "currentLine"
};
if (inFile.fail()) throw "Oopsie";

但您也可以在 python 中执行此操作。您可能需要使用这种方法来提高数值精度。

b) 按照问题描述的方式，无需遍历最小项，而是可以为每个 BDD 节点 n 分配一个概率 p(n)，并计算到根 BDD 节点的概率。你这样做的方法是通过为 TRUE 叶子分配概率 1，为 FALSE 叶子分配概率 0，并为每个内部节点 (t,e,x) 分配 TRUE 后继 t、ELSE 后继 e 和变量 x compute

p(n) = p(t)*p(x) + p(e)*(1-p(x))

那么p(root)就是你要找的。这种方法更优雅，但需要您编写一个（通常是递归的）过程来处理 BDD 结构本身。这里有一个计算令人满意的分配的示例（使用封装 CUDD 自身类型的数据类型）：https://github.com/VerifiableRobotics/slugs/blob/master/src/BFAbstractionLibrary/BFCudd.cpp

Cudd_PrintMinterm，访问乘积总和中的单个最小项

Cudd_PrintMinterm, accessing the individual minterms in the sum of products

cudd