你可能听说过一个众所周知的问题,那就是找到增长最快的子序列.最优算法具有O(n*log(n))复杂性.
我正在考虑在给定序列中找到所有增加的子序列的问题.我找到了一个问题的解决方案,我们需要找到一些长度为k的增加子序列,这些子序列具有O(n*k*log(n))复杂性(其中n是序列的长度).
当然,这个算法可以用于我的问题,但O(n*k*log(n)*n) = O(n^2*k*log(n))我认为解决方案具有复杂性.我认为,必须有更好的(我的意思是 - 更快)解决方案,但我还不知道.
如果您知道如何解决在给定序列中以最佳时间/复杂度找到所有增加的子序列的问题(在这种情况下,最佳=优于O(n^2*k*log(n))),请让我知道这一点.
最后:这个问题不是功课.在我的演讲中提到了一个增长最长的子序列的问题,我开始考虑给定序列中所有增加的子序列的一般概念.
在我写一些关于这个问题的文章之前,我需要告诉你:
问题:
给定:单词列表和"网格",例如:
网格(X表示任何字母):
X X
XXXX
X X
XXXX
词汇表:
ccaa
baca
baaa
bbbb
你必须找到示例"解决方案" - 是否可以将wordlist中的单词装入给定的网格？如果至少有一个解决方案,请打印一个(无论哪个正确).如果没有 - 打印消息,那就没有可能的解决方案.举个例子,有一个解决方案:
b c
baca
b a
baaa
我很难写出我已经尝试过的所有内容(因为英语不是我的母语,我也有很多错误想法的论文).
我的天真算法的工作原理如下:
第一个词需要适当的长度,所以找到任何(第一个？)单词的长度合适(我将使用给定的示例网格和单词列表来演示我的想法):
c X
cXXX
a X
aXXX
对于第一个普通字母(在2个字的交叉处)找到适合网格的任何(第一个)字(因此,在适当的位置上具有适当的长度和公共字母).如果没有这样的单词,请返回(1)并取另一个单词.在原始示例中,没有以"c"开头的单词,因此我们返回到(1)并选择下一个单词(此步骤重复几次,直到我们对第一个单词有"bbbb").现在我们有:
b X
bXXX
b X
bXXX
我们正在寻找一个以"b"开头的单词,例如:
b X
baca
b X
bXXX
一般过程:尝试找到适合给定网格的单词对.如果没有这样的话,请回到上一步并使用另一种组合 - 如果没有这样的话 - 没有解决办法.
上面的一切都是混乱的,我希望你至少能理解问题的描述.我写了一个算法草案,但我不确定它是否有效以及如何正确编码(在我的例子中:c ++).此外,有些情况(即使在上面的例子中)我们需要找到一个依赖于2个或更多其他单词的单词.
也许我只是看不到明显的东西,也许我太傻了,也许......好吧,我真的试图解决这个问题.我不太了解英语,无法准确描述我对这个问题的看法,所以我不能把所有的笔记放在这里(我试图描述一个想法而且很难).信不信由你,我花了很长时间试图找出解决方案,而我几乎什么都没有......
如果你能描述一个解决方案,或者提示如何解决这个问题,我会非常感激.