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) を計算することは不可能です。多数の入力に対して F(x,y) の計算を回避し、F(X,Y) の正確な推定値を取得できる DP のおおよそのバージョンはありますか。

同様の例は、2 つの非常に長く類似した文字列 (例: 類似した DNA 配列) に対する文字列マッチング アルゴリズム (レーベンシュタイン距離) です。このような場合、対角スコアのみが重要であり、対角から遠いエントリは最終的な距離には寄与しません。対角外のエントリの計算を回避するにはどうすればよいですか?

PS: 境界ケース (x < k および y < k の場合) は無視してください。

4

2 に答える 2

1

次の手法を問題にどのように適応させるか正確にはわかりませんが、1 次元だけで作業している場合は、級数の n 番目の項を計算するための O(k 3 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×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) を取得します。ただし、2 つの異なる行列の乗算を行うのではなく、代わりに x に A 2を乗算して x'' を取得することもできます。より一般的には、数列の項 n を取得したい場合、A n xを計算してから、ベクトルの適切な要素を調べることができます。

ここで、行列の乗算が結合的であるという事実を利用して、効率的に A nを計算できます。具体的には、二乗を繰り返す方法を使用して、合計 O(log n) の行列乗算でA nを計算できます。行列が kxk の場合、 n 番目の項を計算するには、合計 O(k 3 log n) の作業に対して各乗算に O(k 3 ) の時間がかかります。

残りは、実際にこの行列 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 |

詳細については、線形代数による線形再帰の解決に関するウィキペディアのエントリ、または上記のアルゴリズムを実装する私自身のコードを参照してください。

唯一の問題は、多次元で作業しているときにこれをどのように適応させるかです。各行の計算をそれ自体の線形再帰として扱い、一度に 1 行ずつ処理することで、これを行うことは確かに可能です。具体的には、最初の k 行の n 項をそれぞれ O(k 3 log n) 時間で計算でき、合計 O(k 4 log n) 時間で最初の k 行を計算できます。その時点から、古い値を再利用することにより、前の行に関して連続する各行を計算できます。計算する行が n 行ある場合、関心のある最終値を計算するための O(k 4 n log n) アルゴリズムが得られます。これが以前に行っていた作業に比べて小さい場合 (O(n 2 k 2)、私は信じています)、これは改善される可能性があります。n は 100 万程度で、k は約 10 であると言っているので、これは単純なアプローチよりもはるかに高速であるように思われます。

そうは言っても、この問題を行ごとに進めるのではなく、多次元で同様の行列トリックを使用することによって、この問題をより迅速に解決する方法があったとしても、私は驚かないでしょう。

お役に立てれば！

于 2012-01-25T00:25:26.680 に答える
0

特定の問題について詳しく知らなくても、一般的なアプローチは、トップダウンの動的計画法アルゴリズムを使用して中間結果をメモすることです。そうすれば、実際に使用される値のみを計算します (繰り返し計算を避けるために結果を保存します)。

于 2012-01-24T22:03:59.567 に答える