3

最長共通部分列問題に関して、すべてのオンラインリソースで提示されている基本的なアルゴリズムは私には明らかです。このアルゴリズムの説明は次のとおりです。

ここに画像の説明を入力してください

私がはっきりしていないのは、次のようにどこにでもあるアルゴリズムの動的計画法バージョンのために提示されたアルゴリズムです。 

function LCSLength(X[1..m], Y[1..n])  
    C = array(0..m, 0..n)  
    for i := 0..m  
       C[i,0] = 0  
    for j := 0..n  
       C[0,j] = 0  
    for i := 1..m  
        for j := 1..n  
            if X[i] = Y[j]  
                C[i,j] := C[i-1,j-1] + 1  //Here shouldn't we change i?
            else  
                C[i,j] := max(C[i,j-1], C[i-1,j])  
    return C[m,n]

しかし、DPバージョンがどのように同等であるかはわかりません。私が困っているのは、DPバージョンでX[i] == Y[j]は、内側のループでそれを見つけたときに、同じでDPを計算し続けるという事実iです。つまり、内側のループの残りの部分は同じと比較し続けX[i]ます。再帰的アルゴリズムはC[i-1、j-1]を評価する必要があると言っているので、次の手順に進むべきではありませんiか？

4

2 に答える 2

5

動的計画法の背後にある考え方は、再帰関数を逆に評価し、基本ケースから始めて、入力問題全体の答えが計算されるまで、ますます大きなサブ問題の答えを繰り返し構築することです。

この関数を再帰的に評価している場合、iとjをデクリメントすることで言及した場合は、絶対に再帰します。ただし、動的計画法バージョンでは、LCS [i、j]から始めて、LCS [i-1、j-1]を評価することによって評価しようとしているわけではありません。LCS [i-1、j-1]から始めて、それを使用してLCS [i、j]を評価します。

具体的には、このコードが実行しているのは、最初に、ベースケースソリューションを直接使用して、すべてのiとjのLCS [i、0]とLCS [0、j]を計算することです。次に、LCS [0、j]がすべてのjに対して既知であるという事実を使用して、すべてのjのLCS [1、j]を計算します。次に、LCS [1、j]がすべてのjに対して既知であるという事実を使用して、すべてのjのLCS [2、j]を計算します。

その結果、LCS [i、j]を計算するときが来て、特定のケースが適用されます。アルゴリズムはiまたはjをデクリメントする必要がなく、再帰的に下に下降します。すでにLCS[i-1、j-1]が計算されているため、値を読み取って、テーブル内の残りの値を積み上げ続けることができます。

これを視覚的に確認するのが最も簡単かもしれません。文字列「canon」と「annie」のLCSを検索するとします。この2Dテーブルから始めます。

    A N N I E
  . . . . . .
C . . . . . .
A . . . . . .
N . . . . . .
O . . . . . .
N . . . . . .

最初に、すべてのiとjに対してLCS [0、j] = LCS [i、0]=0を設定します。

    A N N I E
  0 0 0 0 0 0
C 0 . . . . .
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

次に、このテーブルを行ごとに調べ、元の質問で説明されている繰り返しを使用して、欠落しているエントリを入力します。最初の行を通過するとき、文字Cを単語「ANNIE」のすべての文字と比較します。一致するものが見つからないため、常に繰り返しLCS [i、j] = max（LCS [i-1、j] + LCS [i、j-1]）を使用します。これは常にゼロと評価されるため、次のようになります。

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 . . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

このテーブルの最初の行は、文字列CのLCSの長さと、ANNIEのすべてのプレフィックスを表すため、これは理にかなっています。

次の行では、文字列CAのLCSとANNIEのすべてのサフィックスを検索しようとしています。最初のエントリはAとAの一致と見なされます。これは一致であるため、繰り返しLCS [i、j] = 1 + LCS [i-1、j-1]を使用します。これは1と評価されます。

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 . . . .
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

ここでも、「CA」と「A」のLCSがシーケンスAであり、長さが1であることに注意することで、これを健全性チェックできます。

ここで重要な詳細は、ここでiまたはjをデクリメントしないことです。 この行の残りの部分をまだ入力する必要があるので、先に進みます。

この行の残りのエントリについては、AをANNIEのすべての文字と比較し、一致しないことを確認します。したがって、繰り返しLCS [i、j] = max（LCS [i-1、j]、LCS [i、j-1]）を使用します。これは、残りから1を取得することにより、常に1と評価されます。行の。これはここに示されています：

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 . . . . .
O 0 . . . . .
N 0 . . . . .

次の行に進むと、次のようになります。

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 . . . . .
N 0 . . . . .

繰り返しますが、これは理にかなっています。「CAN」と「A」のLCSは「A」、「CAN」と「AN」のLCSは「AN」などです。

これをテーブルの残りの部分で繰り返して、次の結果のテーブルを見つけることができます。

    A N N I E
  0 0 0 0 0 0
C 0 0 0 0 0 0
A 0 1 1 1 1 1
N 0 1 2 2 2 2
O 0 1 2 2 2 2
N 0 1 2 3 3 3

そして、LCSの長さは3であり、これは正しいことです。

お役に立てれば！

于 2012-12-26T20:12:31.057 に答える
1

C [i] [j]の値は、C [ i] [j-1]、C [i-1] [j]、およびC[i-1][j-1]にのみ依存します。したがって、内側のループでC [i] [j]の値を取得すると、C[i][j]とC[i-1][であるため、C [i] [j+1]の計算を続けることができます。 j+1]とC[i-1][j]はすべてすでに計算されています。

于 2012-12-26T20:13:35.133 に答える