動態規劃近似

我想用動態規劃來計算函數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

動態規劃近似

回答

相關問題