找到包含指定集合中每个字符的单词的最短组合

Question

我得到了一个数组（我们称之为a1）的单词（如“狗”，“鱼”，“运行”，“编程”任何东西） 。

我可以将a1中的任何单词与任何其他单词结合在一起（例如，您可以将“狗”和“编程”组合成“狗编程”），然后再一次，直到字符串获取真的很大。我还得到了一个字符串的数组（例如“de”，“s”，“x？”，“umh”，他们可能几乎是任何东西）。保证a2中没有任何字符串不能在a1的任何字符串中找到。

我在找的是最短的字符串（在创建该字符串时需要多少个组合，而不是多少个字符串包含的字符），它包含了a2中的所有字符串。如果有多个字符串都具有最小长度，我可以选择任何字符串，然后从程序中退出。

现在，我不认为我可以蛮力这个，因为即使数组相对较小，实际上有无数的组合这些单词的选项，但我很想被证明是错误的！

有没有什么好的方法来获得最短的字符串，肯定会产生最短的结果，或者我必须使用启发式算法来搜索很短的字符串？

编辑：我试着从a1中挑选一个字符串，从a2覆盖大多数字符串，然后从a2中删除这些项目，然后重新开始，但它不起作用！它产生相当好的结果，但不是最好的。

Answer 1

如果您将示例中的单词与短划线相结合，例如

dog + programming + sky = dog-programming-sky 

和A2中的字不包含破折号，那么它是一个刚刚成立-COVER伪装，NP完全优化问题。然后，您可以使用SET-COVER提供的任何解决方案策略来解决问题。 SET-COVER有一个快速近似算法，但如果你想拥有绝对最小的解决方案，你需要求助于最坏情况的指数算法。

如果您将没有短划线的单词组合起来，例如

dog + programming + sky = dogprogrammingsky 

那么问题就更加困难，因为现在例如即使它不是任何组成字符串的子字符串，也会在组合字词中找到“ogpro”。