4

a1我得到了一个非常大的单词数组(我们称之为)(比如dog, fish, run,programming任何东西)。

我可以将任何单词 outa1与任何其他单词组合(例如,您可以组合dogand programminginto dog-programming),然后一次又一次,直到字符串变得非常大。

我还有一个a2字符串数组(我们称之为 )(例如de, s, x?, umh,它们几乎可以是任何东西)。保证在a2a1 的任何字符串中都没有找不到的字符串。

我正在寻找的是包含所有字符串的最短字符串(就创建该字符串所需的组合数量而言最短,而不是该字符串包含多少字符)a2。如果有多个字符串都具有最小长度,我可以选择任何一个,然后退出程序。

现在,我不认为我可以暴力破解,因为即使数组相对较小,也有几乎无穷无尽的组合单词的选择,但我很想被证明是错误的!

有什么好的方法可以得到最短的字符串,肯定会产生最短的结果,还是我必须使用启发式算法来搜索相当短的字符串?

我尝试从 a1 中挑选一个覆盖 a2 中大多数字符串的字符串,然后从 a2 中删除这些项目,然后重新开始,但它不起作用!它产生了很好的结果,但不是最好的。

4

1 回答 1

3

如果您将单词与示例中的破折号结合起来,例如

dog + programming + sky = dog-programming-sky

并且A2中的单词不包含破折号,那么它只是一个变相的SET-COVER,一个NP完全优化问题。然后,您可以使用任何可用于 SET-COVER 的解决方案策略来解决问题。SET-COVER 有一个快速逼近算法,但如果你想得到绝对最小的解决方案,你需要求助于最坏情况的指数算法。

如果您将单词组合在一起而不使用破折号,例如

dog + programming + sky = dogprogrammingsky

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

于 2010-01-07T18:49:14.430 回答