我已经做了大量的研究以找到M = 2个序列中最长的一个,但我想弄清楚如何对M> = 2个序列做它。我被赋予N和M:M序列,并带有N个独特元素。 N是{1 - N}的集合。我曾考虑过动态编程方法,但我仍然对如何实际纳入它感到困惑。多个序列的最长公共子序列
实施例输入
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
这里的最大序列可被看作是
精通输出
长度= 3
我已经做了大量的研究以找到M = 2个序列中最长的一个,但我想弄清楚如何对M> = 2个序列做它。我被赋予N和M:M序列,并带有N个独特元素。 N是{1 - N}的集合。我曾考虑过动态编程方法,但我仍然对如何实际纳入它感到困惑。多个序列的最长公共子序列
实施例输入
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4
这里的最大序列可被看作是
精通输出
长度= 3
一个简单的想法。
对于1
和N
之间的每个数字i
,计算最后一个数字为i
的最长子序列。 (我们称之为a[i]
)
为此,我们将在第一个序列中从开始到结束遍历数字i
。如果a[i] > 1
,则有j
这样的数字,在每个序列中它在i
之前。
现在我们可以检查所有可能的值j
和(如果以前的条件成立)做a[i] = max(a[i], a[j] + 1)
。
作为最后一位,因为j
在第一个序列中出现在i
之前,这意味着a[j]
已被计算。
for each i in first_sequence
// for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order
a[i] = 1;
for each j in 1..N
if j is before i in each sequence
a[i] = max(a[i], a[j] + 1)
end
end
end
这是O(N^2*M)
,如果你事先计算位置矩阵。
我认为这大部分是正确的,但是你写的伪装很混乱。它看起来像'我'迭代序列列表,但不应该从'1'迭代到'N'?我猜你认为'sequences [0]'是第一个序列,因此包含所有元素'1 .. N',但我认为像写给'j'所写的那样更清晰。 – IVlad 2011-04-22 10:09:32
@IVlad是的,它应该迭代迭代从1到N的所有数字,但也按照正确的顺序。但是你是对的,这个伪码很混乱。我已经澄清了一点。不确定是否可以更好地呈现“订单”要求。 – 2011-04-22 10:15:19
非常感谢您,我花了一点时间来了解这里发生了什么,但现在是有道理的。 – mkobit 2011-04-30 14:37:42
您可以查看“Design of a new Deterministic Algorithm for finding Common DNA Subsequence”论文。您可以使用此算法构建DAG(第8页,图5)。从DAG中读取最大的常见不同子序列。然后尝试一种动态编程方法,使用M的值来确定每个序列需要构建多少个DAG。基本上使用这些子序列作为密钥并存储相应的序列号,然后尝试找到最大的子序列(可以大于1)。
既然你有独特的元素,@Nikita Rybak的的回答是一个一起去,但既然你提到的动态规划,这里是你如何使用DP当你有两个以上的序列:
dp[i, j, k] = length of longest common subsequence considering the prefixes
a[1..i], b[1..j], c[1..k].
dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if a[i] = b[j] = c[k]
= max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise
为了得到实际的子序列,使用从dp[a.Length, b.Length, c.Length]
开始的递归函数,基本上颠倒上述公式:如果三个元素相等,则回溯到dp[a.Length - 1, b.Length - 1, c.Length - 1]
并打印该字符。如果不是,则根据上述值的最大值进行回溯。
你可以发布你到目前为止尝试过的方法吗?从那里,我们可以指出你在正确的方向。 – 2011-04-22 04:11:57
M是子序列必须存在的序列数量? – BiGYaN 2011-04-22 04:17:06
@Jerry第一行指定N和M.这对C比赛/作业问题规范来说是正常的:) – 2011-04-22 05:17:40