动态规划近似

发布于 2024-12-29 01:33:55 字数 473 浏览 1 评论 0原文

我正在尝试使用动态规划计算函数 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 时）。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

[旋木] 2025-01-05 01:33:55

我不确定如何准确地使以下技术适应您的问题，但如果您仅在一个维度上工作，则有一个 O(k³ log 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² 来得到 x''，而不是进行两个不同的矩阵乘法。更一般地，如果我们想要获得序列的第 n 项，我们可以计算 Aⁿx，然后检查向量的适当元素。

在这里，我们可以利用矩阵乘法具有结合律的事实来高效地计算 Aⁿ。具体来说，我们可以使用重复平方的方法来计算Aⁿ总共 O(log n) 次矩阵乘法。如果矩阵为 kxk，则每次乘法需要花费 O(k³) 时间，总共需要 O(k³ 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 |

有关此的更多详细信息，请参阅关于用线性代数求解线性递推的维基百科条目，或我自己的实现上述算法的代码。

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

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

希望这有帮助！

I'm not sure precisely how to adapt the following technique to your problem, but if you were working in just one dimension there is an O(k³ log n) algorithm for computing the nth term of the series. This is called a linear recurrence and can be solved using matrix math, of all things. The idea is to suppose that you have a recurrence defined as

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)

For example, the Fibonacci sequence is defined as

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

There is a way to view this computation as working on a matrix. Specifically, suppose that we have the vector x = (x_1, x_2, ..., x_k)^T. We want to find a matrix A such that

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

That is, we begin with a vector of terms 1 ... k of the sequence, and then after multiplying by matrix A end up with a vector of terms 2 ... k + 1 of the sequence. If we then multiply that vector by A, we'd like to get

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

In short, given k consecutive terms of the series, multiplying that vector by A gives us the next term of the series.

The trick uses the fact that we can group the multiplications by A. For example, in the above case, we multiplied our original x by A to get x' (terms 2 ... k + 1), then multiplied x' by A to get x'' (terms 3 ... k + 2). However, we could have instead just multiplied x by A² to get x'' as well, rather than doing two different matrix multiplications. More generally, if we want to get term n of the sequence, we can compute Aⁿx, then inspect the appropriate element of the vector.

Here, we can use the fact that matrix multiplication is associative to compute Aⁿ efficiently. Specifically, we can use the method of repeated squaring to compute Aⁿ in a total of O(log n) matrix multiplications. If the matrix is k x k, then each multiplication takes time O(k³) for a total of O(k³ log n) work to compute the nth term.

So all that remains is actually finding this matrix A. Well, we know that we want to map from (x_1, x_2, ..., x_k) to (x_1, x_2, ..., x_k, x_{k + 1}), and we know that x_{k + 1} = c_1 x_1 + c_2 x_2 + ... + c_k x_k, so we get this matrix:

    | 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 |

For more detail on this, see the Wikipedia entry on solving linear recurrences with linear algebra, or my own code that implements the above algorithm.

The only question now is how you adapt this to when you're working in multiple dimensions. It's certainly possible to do so by treating the computation of each row as its own linear recurrence, then to go one row at a time. More specifically, you can compute the nth term of the first k rows each in O(k³ log n) time, for a total of O(k⁴ log n) time to compute the first k rows. From that point forward, you can compute each successive row in terms of the previous row by reusing the old values. If there are n rows to compute, this gives an O(k⁴ n log n) algorithm for computing the final value that you care about. If this is small compared to the work you'd be doing before (O(n² k²), I believe), then this may be an improvement. Since you're saying that n is on the order of one million and k is about ten, this does seem like it should be much faster than the naive approach.

That said, I wouldn't be surprised if there was a much faster way of solving this problem by not proceeding row by row and instead using a similar matrix trick in multiple dimensions.

Hope this helps!

回复收藏 0 原文