3

字谜：

字谜是一种文字游戏，是重新排列单词或短语的字母以产生新单词或短语的结果，使用所有原始字母一次；

子集和问题：

问题是这样的：给定一组整数，是否存在总和为零的非空子集？

例如，给定集合 { -7, -3, -2, 5, 8}，答案是肯定的，因为子集 { -3, -2, 5} 的总和为零。问题是NP完全的。

现在假设我们有一个包含 n 个单词的字典。现在，字谜生成问题可以描述为在字典中找到一组单词（n 个单词），这些单词用完输入的所有字母。所以它不会变成一种子集和问题。

我错了吗？

4

4 回答 4

4

这两个问题相似但不是同构的。

  • 在字谜中，字母的顺序很重要。在子集总和中，顺序无关紧要。
  • 在字谜中，必须使用所有字母。在子集总和中，任何子集都可以。
  • 在字谜中，子组必须形成从相对较小的允许单词字典（字典）中提取的单词。在子集总和中，组是不受限制的（没有允许分组的字典）。
于 2012-01-03T08:00:40.280 回答
3

如果您证明解决字谜查找（不超过多项式次数）可以解决子集和问题 - 这将是计算机科学的一场革命（您将证明 P=NP）。

显然找到字谜是多项式时间问题：

检查两条记录是否是彼此的字谜就像排序字母并比较结果字符串（即C*s*log(s)时间，其中s- 记录中的字母数）一样简单。您最多会有n这样的检查，其中n- 字典中的记录数。所以显然运行时间 ~C*s*log(s)*n受到输入大小多项式的限制 - 您的输入记录和字典相结合。

编辑：

只有当字谜查找问题被定义为在可能的完整短语的字典中查找输入短语的字谜时，上述所有内容才有效。

虽然上面原始问题中的字谜发现问题的措辞......

现在假设我们有一个包含 n 个单词的字典。现在，字谜生成问题可以描述为在字典中找到一组单词（n 个单词），这些单词用完输入的所有字母。

...似乎暗示了一些不同的东西 - 例如，字典中多个条目的某种组合也是输入的可能字谜的有效选择。

然而，这似乎立即有问题且不清楚，因为（1）通常短语不仅仅是随机单词的序列（它应该作为一个完整的短语有意义），（2）通常短语中的单词需要也是符号的分隔符 - 所以它不是清除输入中是否需要分隔符（空白字符）以允许字典中的单独条目以及单个字典条目中是否允许分隔符。

因此，在我上面的最初答案中，我应用了“语义剃刀”，将问题定义解释为唯一明确且有意义的“字谜发现”。

但我们也可以这样解释作者的定义：

给定 n 个字母序列的字典（单独的字典条目可能包含相同的序列）和一个目标字母序列 - 找到字典条目的任何子集，如果连接在一起将是目标字母序列的精确重排，或者确定这样的子集不存在.

^^^- 尽管这个问题作为“字谜查找问题”不再真正有意义，但它仍然很有趣。这与我上面考虑的问题非常不同。

还有一件事尚不清楚 - 字母表的灵活性。具体来说，问题定义还必须指定字母集是固定的还是允许在指定字典和所述字母的目标序列时为问题的每个新解决方案重新定义它。这很重要——能力和复杂性取决于此。

该问题的变体具有为每个解决方案单独定义字母表（可用字母数）的能力，实际上等效于子集和问题。这使它成为NP完全的。

我可以证明我们的问题与子集和问题的自然数变体等价，定义为

给定自然数的集合（多集）（允许重复数）和目标自然数 - 找到任何与目标数完全相加的子集合或确定此类子集合不存在。

不难看出，大多数线性步数足以将一个问题输入转换为另一个问题输入，反之亦然。因此，一个问题的解决方案恰好转化为另一个问题的一个解决方案加上主要是线性开销。

这个仅正数的子集和变体等效于作者给出的零和子集和变体（参见例如子集和维基百科文章）。

于 2012-01-03T07:51:39.917 回答
2

我认为你错了。

字谜生成必须比子集和更简单，因为我可以设计一个简单的 O(n) 算法来解决它（如定义）：

initialize the list of anagrams to an empty list
iterate the dictionary word by word
    if all the input letters are used in the ith word
        add the word to the list of anagrams

return the list of anagrams

此外，字谜由作为输入单词排列（即重新排列）的有效单词组成，而子集没有顺序概念。它们实际上可能包含比输入集（因此是子集）更少的元素，但字谜必须始终与输入单词的长度相同。

于 2012-01-03T05:42:38.377 回答
1

它不是 NP 完全的，因为给定一组字母，不管怎样，这组字谜仍然是相同的。

总是有一个单一的映射将输入 L 的字母转换为一组字谜 A。所以我们可以说 f(L) = A 对于 f 的任何执行。我相信，如果我理解正确的话，这会使函数具有确定性。Set 的顺序是不相关的，因此考虑到不同顺序的解，非确定性是无效的，它也是无效的，因为字典中的所有条目都是唯一的，因此可以确定性地排序。

于 2012-01-03T04:26:11.240 回答