algorithm - 你会如何编写一个程序来找到单词列表中最短的 pangram？

Question

给定一个包含字母 a-z 至少一次的单词列表，你将如何编写一个程序来找到最短的 pangram按字符数(不计算空格)算作单词的组合？

由于我不确定是否存在简短答案，因此这不是代码高尔夫，而只是讨论您将如何处理这个问题。但是，如果您认为您可以设法编写一个简短的程序来执行此操作，那么继续吧，这可能会变成代码高尔夫:)

Answer 1

我会通过证明该问题是 NP-hard 问题，并通过检查看起来相似的 NP-hard 问题的启发式方法来解决这个问题。

我们可以减少 Set Cover problem到我们的。 Set Cover 的不同之处在于，不是使用的字母数量被最小化，而是使用的单词数量被最小化。假设我们要解决 Set Cover 问题，给定 N 个单词，每个单词的长度都小于 M。让我们通过克隆给定的单词集来构建另一组单词，但将 N*M 个非英语字母连接到每个单词，比如说，Ж。如果我们可以构建一个需要最少符号的 pangram(在 a,b,c...x,y,z,ж 字母表上)，如果我们删除所有 Ж 字母，那将是一个包含最少单词的 pangram。

这证明了原始问题是 NP-hard，但不幸的是，我们需要将一些 NP-hard 问题简化为 以重用其(希望是已知的)启发式。 Set-Cover 具有对数近似的贪婪启发式算法，但我认为它不适用于原始问题(Set-Cover 问题的性质需要采用字母丰富的长词；这不是解决我们问题的方法)。

所以我会搜索相关的 NP-hard 问题列表，并检查是否有感兴趣的内容。这就是我处理这个问题的方式。