1

我正在尝试使用动态编程计算函数 F(x,y)。功能上：

F(X,Y) = a1 F(X-1,Y)+ a2 F(X-2,Y) ... + ak F(Xk,Y) + b1 F(X,Y-1)+ b2 F (X,Y-2) ... + bk F(X,Yk)

其中 k 是一个小数（k=10）。

问题是，X=1,000,000，Y=1,000,000。因此，为 x=1..1000000 和 y=1..1000000 之间的每个值计算 F(x,y) 是不可行的。是否有一个近似版本的 DP，我可以避免为大量输入计算 F(x,y)，并且仍然可以准确估计 F(X,Y)。

一个类似的例子是两个非常长且相似的字符串（例如相似的 DNA 序列）的字符串匹配算法（Levenshtein 距离）。在这种情况下，只有对角线分数很重要，远离对角线的条目对最终距离没有贡献。我们如何避免计算非对角线条目？

PS：忽略边界情况（即当 x < k 和 y < k 时）。

4

2 回答 2

1

我不确定如何准确地使以下技术适应您的问题，但如果您只在一个维度上工作，则有一个 O(k 3 log n) 算法用于计算系列的第 n 项。这被称为线性递归，并且可以使用矩阵数学来解决。这个想法是假设你有一个定义为

  • F(1) = x_1
  • F(2) = x_2
  • ...
  • F(k) = x_k
  • F(n + k + 1) = c_1 F(n) + c_2 F(n + 1) + ... + c_k F(n + k)

例如，斐波那契数列定义为

  • F(0) = 0
  • F(1) = 1
  • F(n + 2) = 1 x F(n) + 1 x F(n + 1)

有一种方法可以将此计算视为处理矩阵。具体来说，假设我们有向量 x = (x_1, x_2, ..., x_k)^T。我们想找到一个矩阵 A 使得

Ax = (x_2, x_3, ..., x_k, x_{k + 1})^T

也就是说，我们从序列的项 1 ... k 的向量开始，然后乘以矩阵 A 后，以序列的项 2 ... k + 1 的向量结束。如果我们然后将该向量乘以 A，我们希望得到

A(x_2, x_3, ..., x_k, x_{k + 1})^T = (x_3, x_4, ..., x_k, x_{k + 1}, x_{k + 2})

简而言之，给定序列的 k 个连续项，将该向量乘以 A 就可以得到序列的下一项。

该技巧利用了我们可以将乘法与 A 分组这一事实。例如，在上述情况下，我们将原始 x 乘以 A 得到 x'（项 2 ... k + 1），然后将 x' 乘以 A得到 x''（条款 3 ... k + 2）。但是，我们也可以将 x 乘以 A 2以得到 x''，而不是进行两个不同的矩阵乘法。更一般地说，如果我们想得到序列的项 n，我们可以计算 A n x，然后检查向量的适当元素。

在这里，我们可以利用矩阵乘法是关联的这一事实来有效地计算 A n。具体来说，我们可以使用重复平方的方法，在总共 O(log n) 次矩阵乘法中计算 A n 。如果矩阵是 kxk，则每次乘法需要时间 O(k 3 )，总共需要 O(k 3 log n) 工作来计算第 n 项。

所以剩下的就是找到这个矩阵 A。好吧，我们知道我们想要从 (x_1, x_2, ..., x_k) 映射到 (x_1, x_2, ..., x_k, x_{k + 1} )，我们知道 x_{k + 1} = c_1 x_1 + c_2 x_2 + ... + c_k x_k，所以我们得到这个矩阵：

    | 0   1   0   0    ...   0 |
    | 0   0   1   0    ...   0 |
A = | 0   0   0   1    ...   0 |
    |        ...               |
    | c_1 c_2 c_3 c_4  ... c_k |

有关这方面的更多详细信息，请参阅有关使用线性代数解决线性递归的 Wikipedia 条目，或我自己的实现上述算法的代码。

现在唯一的问题是当你在多个维度上工作时如何适应它。通过将每一行的计算视为其自己的线性递归，然后一次走一行，当然可以做到这一点。更具体地说，您可以在 O(k 3 log n) 时间内计算前 k 行的第 n 项，总共需要 O(k 4 log n) 时间来计算前 k 行。从那时起，您可以通过重用旧值根据前一行计算每个连续行。如果有 n 行要计算，这会给出一个 O(k 4 n log n) 算法来计算您关心的最终值。如果这与您之前所做的工作相比很小（O（n 2 k 2），我相信），那么这可能是一种改进。既然你说 n 大约是一百万，而 k 大约是十，这似乎应该比天真的方法快得多。

也就是说，如果有一种更快的方法来解决这个问题，而不是逐行处理，而是在多个维度上使用类似的矩阵技巧，我不会感到惊讶。

希望这可以帮助！

于 2012-01-25T00:25:26.680 回答
0

在不了解您的具体问题的情况下，一般方法是使用自上而下的动态规划算法并记住中间结果。这样，您将只计算将实际使用的值（同时保存结果以避免重复计算）。

于 2012-01-24T22:03:59.567 回答