arrays - ocaml lcs 没有像数组这样的对象

Question

如何在 ocaml 中不使用数组而仅使用列表折叠来找到最长公共(public)子序列

Answer 1

这是 Dynamic programming 的经典示例: 这 要实现的函数可以轻松地递归指定，但是 递归调用对应的子问题有很多 重叠。一个简单的递归实现会做无用的工作 重新计算这些子问题，导致运行时间呈指数增长， 而内存或不同的方法都会导致多项式 算法。

给定最长公共(public)子序列(LCS)问题的公式 on Wikipedia 如下(伪代码):

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) 长度输入的最坏情况运行时间 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'] ，因此将被计算两次。对于足够长的输入，其他子调用会重新计算任意高的时间。

避免这种低效率的解决方案是构建一个数据结构 每个结果只计算一次。传统的方法是 使用可变的二维矩阵来存储结果，但你不是 允许使用它。您可以使用函数式数据结构来存储 通过计算对应的列表列表来得出结果

[
  [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 list-of-list 对应于 lcs xs ys 计算的所有子结果，以这种方式组织。

但是，我认为您只是在寻找朴素的指数公式(同样，看起来像是一种教学 练习)。