7

自枚举 pangrams 的 wiki 文章指出，它们是使用二元决策图计算的。我一直在阅读有关 BDD 的文章，据我了解，您需要将一些问题表示为布尔函数，然后才能为其构造 BDD。

我该怎么做呢？

几天来我一直在考虑这个问题，我很确定您可以使用简单的编码来表示布尔函数的输入：

10000 01010 01011 10101 ...
16A's 10B's 11C's 21D's ...

因此，对于以“16 个 A，10 个 B，11 个 C，21 个 D”开头的 pangram，您可以将其表示为 10000010100101110101...

这意味着布尔函数中有 26 * 5 = 130 个变量，假设您将字符的最大频率限制为 32 次出现。

输出应该是表示是否是自枚举pangram，即句子是否描述了它自己的频率集。

为此，在此过程中肯定需要一个（或多个）哈希表。

所以对于字母 E，哈希表可能会开始：

one   -> 1
two   -> 0
three -> 2
four  -> 0
five  -> 1
...

在二进制中，可能看起来像：

1   -> 1
10  -> 0
11  -> 10
100 -> 0
101 -> 1

如果来自 E 哈希表的所有查找的总和等于 E 对应的五个输入位，则自枚举 pangram 的该部分是正确的。如果所有部分都正确，则布尔函数应产生 1，否则为 0。

我相当确定我可以弄清楚如何使用布尔函数进行加法以及如何检查两个数字是否相等。但是，我不知道从哪里开始将哈希表表示为布尔函数。此外，将所有部分连接在一起可能会让我感到困惑。

有什么想法吗？想法？合作？我想看看这是怎么回事。

提前致谢。

4

1 回答 1

1

在我看来，在这种情况下使用 BDD 只是一种表示和协助操纵用于评估的表达式的方式，例如，如果您的句子满足作为自枚举 pangram 的要求。有一些规则可以在概念上比布尔代数中的语句更容易地处理它们，因为它们比布尔符号更容易用该符号表示，就像 8000 个变量中的多项式更难处理一样它的一般形式，而不是其他一些表示它来自哪里的符号。存在用于操纵这四种中的任何一种的计算机算法，因此您最好的选择可能是查找并根据您的需要调整一种。您可能会发现此文档很有帮助。

Google也可能有助于查找其他资源。

于 2012-09-14T21:22:27.903 回答