4

動的計画法を使用してこれを適切な方法で行うことができますが、指数時間で行う方法がわかりません。

2 つの文字列間の最大の共通サブシーケンスを探しています。注: サブシーケンスを意味し、サブストリングではなく、シーケンスを構成するシンボルが連続している必要はありません。

4

6 に答える 6

6

動的プログラミングコードのテーブル内のルックアップを再帰呼び出しに置き換えるだけです。言い換えると、LCS問題の再帰的定式化を実装するだけです。

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

編集

擬似コード（実際にはほとんどPython）：

def lcs(s1, s2):
 if len(s1)==0 or len(s2)==0: return 0
 if s1[0] == s2[0]: return 1 + lcs(s1[1:], s2[1:])
 return max(lcs(s1, s2[1:]), lcs(s1[1:], s2))
于 2012-01-25T21:24:54.650 に答える
1

文字列 A と文字列 B。再帰アルゴリズムです。単純かもしれませんが、単純です。

A の最初の文字を見てください。これは共通のシーケンスであるかどうかのどちらかです。「not」オプションを検討するときは、最初の文字を削除して再帰的に呼び出します。'is in a common sequence' オプションを検討するときは、それを削除し、B の先頭から B の同じ文字まで (同じ文字を含む) も削除します。いくつかの擬似コード:

def common_subsequences(A,B, len_subsequence_so_far = 0):
    if len(A) == 0 or len(B) == 0:
        return
    first_of_A = A[0] // the first letter in A.
    A1 = A[1:] // A, but with the first letter removed
    common_subsequences(A1,B,len_subsequence_so_far) // the first recursive call
    if(the_first_letter_of_A_is_also_in_B):
        Bn = ... delete from the start of B up to, and including,
             ... the first letter which equals first_of_A
        common_subsequences(A1,Bn, 1+len_subsequence_so_far )

それから始めて、これまでに見つかった最長のサブシーケンスを記憶することで最適化し、現在の関数がそれを超えることができない場合 (つまり、min(len(A), len(B))+len_subsequence_so_farこれまでに見つかった最長の長さよりも小さい場合) に戻ります。

于 2012-01-25T22:13:37.550 に答える
1

2 つの文字列aとblengthがあるとしnます。最長の共通サブシーケンスは、 stringaにも存在するstring の最長のサブシーケンスになりますb。

したがって、可能なすべてのサブシーケンスを反復処理して、aそれが にあることを確認できbます。

このための高レベルの擬似コードは次のようになります。

for i=n to 0
    for all length i subsequences s of a
        if s is a subsequence of b
            return s
于 2012-01-25T21:51:49.777 に答える
0

指数時間を達成するには、両方の配列のすべてのサブシーケンスを生成し、それぞれを比較するだけで十分です。同一の 2 つを照合する場合は、それらの長さが現在の最大値よりも大きいかどうかを確認します。擬似コードは次のようになります。

Generate all subsequences of `array1` and `array2`.
for each subsequence of `array1` as s1
    for each subsequece of `array2` as s2
        if s1 == s2 //check char by char
            if len(s1) > currentMax
                currentMax = len(s1)
for i = 0; i < 2^2; i++;

それは絶対に最適ではありません。しようともしない。ただし、質問は非常に非効率的なアルゴリズムに関するものであるため、提供しました。

于 2016-08-17T12:59:03.553 に答える
0

基本的に、動的プログラミング パラダイムを使用しないと、指数関数的な時間に到達します。これは、部分的な値を保存しないことにより、部分的な値を複数回再計算しているためです。

于 2012-01-25T21:49:26.370 に答える
-1 
int lcs(char[] x, int i, char[] y, int j) {
    if (i == 0 || j == 0) return 0;
    if (x[i - 1] == y[j - 1]) return lcs(x, i - 1, y, j - 1) + 1;
    return Math.max(lcs(x, i, y, j - 1), lcs(x, i - 1, y, j));
}

print(lcs(x, x.length, y, y.length);

以下は部分再帰ツリーです。

                       lcs("ABCD", "AFDX")
                      /                   \
     lcs("ABC", "AFDX")                   lcs("ABCD", "AFD")
       /            \                      /               \
lcs("AB", "AFDX") lcs("AXY", "AFD")    lcs("ABC", "AFD") lcs("ABCD", "AF")

最悪のケースは、LCS の長さが 0 の場合です。これは、共通のサブシーケンスがないことを意味します。その場合、すべての可能なサブシーケンスが調べられ、サブシーケンスがありますO(2^n)。

于 2016-08-16T08:42:57.217 に答える