2

如何在不使用数组且仅列出 ocaml 中的折叠的情况下找到最长的公共子序列

4

1 回答 1

2

这是动态编程的一个经典例子：可以很容易地递归指定要实现的函数，但是与递归调用对应的子问题有很多重叠。一个简单的递归实现将通过重新计算这些子问题来做无用的工作，从而导致指数运行时间，而记忆化或不同的方法会导致多项式算法。

维基百科上给出的最长公共子序列（LCS）问题的公式 如下（伪代码）：

LCS(X,Y,0,0) = []
LCS(X,Y,i,j) =
  if X[i] = Y[j] then X[i]::LCS(X,Y,i-1,j-1)
  else longest(LCS(X,Y,i-1,j), LCS(X,Y,i,j-1))

当转换为将列表而不是数组和索引作为参数时，您有以下公式（仍然是伪代码）：

LCS([], []) = []
LCS([x],[]) = []
LCS([], [y]) = []
LCS(x::xs, y::ys) =
  if x = y then x::LCS(xs, ys)
  else longest(LCS(x::xs, ys), LCS(xs, y::ys))

从中得到一个 OCaml 实现应该很容易（我假设这是一个练习，会让你自己来解决），但这将是一个指数算法，O(2^N) 在输入的最坏情况下运行时间 length N。

要查看示例中效率低下的原因，假设输入是[x;y;z]并且[x';y';z']与x不同x'。lcs [x;y;z] [x';y';z']将进行两次递归调用，一次lcs [y;z] [x';y';z']和一次lcs [x;y;z] [y';z']。但随后这两个电话将分别拨打两个电话，lcs [z] [x';y';z']第lcs [y;z] [y';z'] 一个电话lcs [y;z] [y';z']，lcs [x;y;z] [z']第二个电话。请注意，它们都进行了递归调用lcs [y;z] [y';z']，因此将计算两次。对于足够长的输入，其他子调用会被重新计算任意多的时间。

避免这种低效率的解决方案是构建一个只计算每个结果一次的数据结构。执行此操作的传统方法是使用可变的 2D 矩阵来存储结果，但不允许使用它。您可以使用函数式数据结构来存储结果，方法是计算对应于的列表列表

[
  [lcs [x;y;z] [x';y';z']; lcs [x;y;z] [y';z']; lcs [x;y;z] [z']; lcs [x;y;z] [];]; 
  [lcs [y;z] [x';y';z'];   lcs [y;z] [y';z'];   lcs [y;z] [z'];   lcs [y;z] [];];
  [lcs [z] [x';y';z'];     lcs [z] [y';z'];     lcs [z] [z'];     lcs [z] [];];
  [lcs [] [x';y';z'];      lcs [] [y';z'];      lcs [] [z'];      lcs [] [];];
]

找到一种简单的递归方法来计算这个结果列表似乎是一个有趣的高级练习。例如，您可以递归地计算第 4 边的这个“正方形”，通过计算边 3 的右下角子正方形，然后将其折叠（作为列表列表）以计算结果正方形的左侧，然后折叠它的行（列表列表的头部）来计算结果正方形的顶部。更一般地说，您可以定义一个函数，该函数lcs_results xs ys采用两个长度序列M并N返回与MxN将由 计算的所有子结果相对应的列表列表lcs xs ys，以这种方式组织。

但是，我假设您只是在寻找简单的指数公式（再次，看起来像一个教学练习）。

于 2013-02-15T09:23:25.707 回答