(0) 阅读 (1058)

最短共同超序列问题 编辑

词条创建者 匿名用户

最短共同超序列问题

编辑

计算机科学中,两个序列X和Y的最短共同超序列是以X和Y为子序列的最短序列。这是一个与最长公共子序列问题密切相关的问题。给定两个序列X=<x1,...,xm>和Y=<y1,...,yn>,如果可以从U中删除项目以产生X和Y,则序列U=<u1,...,uk>是X和Y的共同超序列。最短共同超序列(SCS)是一个最小长度的共同超序列。在最短共同超序列问题中,给出了两个序列X和Y,任务是找到这些序列的最短共同超序列。一般来说,SCS不是xxx的。对于两个输入序列,SCS可以很容易地从最长的共同子序列(LCS)中形成。例如,X的最长的公共子序列在三个或更多输入序列的最短公共超序列和最长公共子序列之间没有类似的关系。(特别是,LCS和SCS不是双重问题。)然而,这两个问题都可以在以下时间内解决{displaystylen}是它们的xxx长度。是它们的xxx长度。对于任意数量的输入序列的一般情况下,该问题是NP-hard。

最短公共超弦

编辑

与此密切相关的问题是寻找一个最小长度的字符串,该字符串是有限字符串集S={s1,s2,...,sn}的超弦,这也是NP-hard。多年来,人们提出了几种恒定系数的近似方法,目前已知的最佳算法的近似系数为2.475。然而,最简单的解决方法也许是将问题重新表述为加权集合覆盖的实例,使集合覆盖实例的最优解的权重小于最短超弦S长度的两倍,然后可以使用加权集合覆盖的O(log(n))近似值来获得最短超弦的O(log(n))近似值(注意这不是一个恒定系数近似)。对于这个字母表中的任何字符串x,定义P(x)为作为x的子串的所有字符串的集合。集合覆盖的实例I被表述如下。

最短共同超序列问题

对于每一对字符串si和sj,如果si的最后k个符号与sj的前k个符号相同,则在M中添加一个字符串,该字符串由si与sj的xxx重叠部分组成。定义宇宙U{displaystyle{mathcal{U}}定义集合覆盖实例的U}的集合覆盖实例为S定义宇宙的子集为{P(x)|x∈S∪M}定义每个子集P(x)的代价为|x|,即x的长度。然后,可以用加权集合覆盖的算法来解决实例I,该算法可以输出任意的字符串x的连接,对于这些字符串,加权集合覆盖算法可以输出P(x)。

最短共同超序列问题的例子

编辑

考虑集合S={abc,cde,fab},它成为加权集合覆盖实例的宇宙。在这种情况下,M={abcde,fabc}。那么,宇宙的子集是{displaystyle{begin{aligned}{P(x)|xinScupM}&={P(x)|xin{abc,cde,fab,abcde,fabc}}={P(abc),P(cde),P(fab)。P(abcde),P(fabc)}\={{a,b,c,ab,bc,abc},{c,d,e,cd,de,cde},ldots,{f,a,b,c,fa,ab,bc,fab,abc/fabc}}\end{aligned}}}。其成本分别为3、3、3、5和4。


内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/164100/

发表评论

登录后才能评论

词条目录
  1. 最短共同超序列问题
  2. 最短公共超弦
  3. 最短共同超序列问题的例子

轻触这里

关闭目录

目录