时间戳

首页 > 解决方案 > Cudd_PrintMinterm，访问产品总和中的各个最小项

cudd - Cudd_PrintMinterm，访问产品总和中的各个最小项

问题描述

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

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

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

我需要一一处理的原因是我正在处理会炸毁内存的大文件。一旦我超过 80-100 个变量，您就处于整个 minterm 文本文件转储大小的 TB OoM 中. 如果可能，我想获取每个 minterm，将其添加到运行总和中，并在添加后将其删除。

希望这很清楚，但如果不是，可能需要一些迭代。谢谢，

标签： cudd

解决方案

你有几个选择：

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

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 节点分配 na 概率 p(n)，并计算到根 BDD 节点的概率。你这样做的方式是通过将概率 1 分配给 TRUE 叶，将概率 0 分配给 FALSE 叶，并为每个具有 TRUE 后继 t、ELSE 后继 e 和变量 x 的内部节点 (t,e,x) 计算

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

推荐阅读