动态规划近似

我想用动态规划来计算函数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）。

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

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

来源

2012-01-24 ElKamina

对不起，我只是不明白你在问什么。你能更具体地说明你想解决的问题是什么？ – templatetypedef

@templatetypedef现在应该更清楚了。感谢你的眼球！ – ElKamina

@Jim忽略边界情况。 – ElKamina

不知道更多关于您的具体问题，一般的做法是使用top-down dynamic programming algorithm和memoize中间结果。这样你将只计算实际使用的值（同时保存结果以避免重复计算）。

来源

2012-01-24 22:03:59

问题描述已更新。 – ElKamina

我不确定如何将以下技术适用于您的问题，但是如果您只在一个维度上工作，则计算该系列的第n项的O（算法记录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）

例如，Fibonacci序列被定义为

F（0）= 0
F（1）= 1
F（N + 2）= 1×F（N）+ 1×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 ⁿ。具体地，我们可以使用method of repeated squaring来计算^Ñ总共O（log n）的矩阵乘法。如果矩阵是的K×K，则各倍增花费时间为O（K ），总共的O（K log n）的工作来计算第n项。那么，我们知道我们想要从（x_1，x_2，...，x_k）映射到（x_1，x_2，...，x_k，x_ {x}，x_k，x_k） 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 entry on solving linear recurrences with linear algebra，或my own code that implements the above algorithm.

唯一的问题是现在你如何适应这个，当你在多个维度努力。通过将每一行的计算看作自己的线性递归，然后一次去一行，这当然是可能的。更具体地，可以计算第一k行的第n项的每个为O（K log n）的时间，总共的O（K log n）的时间来计算所述第一k行。从这一点开始，您可以通过重新使用旧值来计算前一行中的每个连续行。如果有n行要计算，这就给出了一个O（kn logn）算法来计算你所关心的最终值。如果与工作，这是小你会做之前（O（N ķ），我认为），那么这可能是一种进步。既然你说n在100万左右，k是10左右，这看起来应该比天真的方法快得多。

这么说，我也不会感到惊讶，如果有通过不继续逐行，而是采用了类似矩阵技巧在多个层面解决这一问题的一个更快的方法。

希望这会有所帮助！

来源

2012-01-25 00:25:26 templatetypedef

动态规划近似

回答

相关问题