是否有一个软件包（最好是应用程序，而不是库）可以从给定的真值表（以某种文本格式）创建归约有序二进制决策图（ROBDD）？
问问题
10679 次
4 回答
6
You can also try this: http://formal.cs.utah.edu:8080/pbl/BDD.php
It is the best tool for BDDs I used so far.
于 2013-06-10T14:48:39.107 回答
1
BDD 是一种内存受限的数据结构，因为它严重依赖于检测重复的子真值表。您会发现大多数 BDD 包并不完全适合大型通用真值表，而是针对非常稀疏或高度重复的表达式进行了优化。
使用标准 BDD 包，您可以使用对变量进行操作的表达式。所以你必须遍历你的真值表，为表中的 1 构造类似于和的乘积表达式。在此过程中，大多数库会动态地重新排序变量以适应内存限制，从而导致另一个巨大的减速。在大约 24 个变量之后，即使真值表非常稀疏，这些库也将开始在现代系统上运行。
如果您只是在给定一个已隐式定义其变量顺序的真值表寻找最终的 BDD 节点，您可以跳过外部库和可怕的运行时的许多复杂性，只需使用一些 Unix 文本处理工具。
关于 BDD 的一个很好的资源，Knuth 的 TAOCP v4.1b，显示了 BDD 节点及其“珠”的等价性，即非方字符串的子真值表。我将讨论一个更简单的版本，ZDD，它具有类似的结构，称为“zeads”：不完全为零的正部分子真值表。为了概括回 BDD，将管道中的 sed+grep 替换为过滤方形字符串的程序，而不是保留正部分非零字符串。
要打印真值表的所有 zead（作为 ascii '1' 和 '0' 的单行文件，最后换行），请在设置变量数和文件名后运行以下命令：
MAX=8; FILENAME="8_vars_truthtable.txt"; for (( ITER=0; ITER<=${MAX}; ITER++ )) ; do INTERVAL=$((2 ** ${ITER})); fold -w ${INTERVAL} ${FILENAME} | sed -n '1~2!p' | grep -v "^0*$" | sort -u ; done
这比 BDD 包有很多好处：
- 简单，基本上没有多余的依赖。
- 与内存中的哈希表不同，外部排序意味着没有颠簸。
- 如果您在 for 循环中分叉时了解行缓冲和磁盘缓存，则可以轻松实现并行化和可扩展。
- 如果写入中间文件排序也将并行化。
我经常将它用于最大 32 个变量的真值表，而使用 BDD 库是不可能实现的。它根本不会对内存系统征税，几乎不使用几 MB。但是，如果您有大量可用的 RAM，像 Linux 这样的体面的操作系统会很乐意将其全部用于缓存磁盘以使其更快。
于 2015-02-11T13:42:45.553 回答
1
使用任何 BDD 库，您都可以做您想做的事。当然，你必须自己写一段代码。
如果你正在寻找一个轻量级的工具，我经常使用这样的小程序来快速查看一个函数的 BDD：
于 2013-03-25T13:27:06.710 回答
0
我也搜索了类似的东西，但找不到 javascript 实现。
我现在创建了自己的模块，该模块能够从真值表中创建、最小化和排序优化 bdd。
于 2020-02-25T13:42:18.480 回答