Как найти самую длинную общую подпоследовательность в экспоненциальном времени?

Question

Я могу сделать это надлежащим образом, используя динамическое программирование, но я не могу понять, как это сделать за экспоненциальное время.

Я ищу, чтобы найти наибольшую общую подпоследовательность между двумя строками. Примечание: я имею в виду подпоследовательности, а не подстроки, символы, которые составляют последовательность, не обязательно должны быть последовательными.

Answer 1

Просто замените поиск в таблице в вашем динамическом программном коде на рекурсивные вызовы. Другими словами, просто реализуйте рекурсивную формулировку задачи LCS :

EDIT

В псевдокоде (фактически, почти на 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))

Answer 2

Строка A и Строка B. Рекурсивный алгоритм, может быть, он наивный, но он прост:

Посмотрите на первую букву А. Это будет либо в общей последовательности, либо нет. При рассмотрении опции «not» мы обрезаем первую букву и вызываем рекурсивно. При рассмотрении опции «находится в общей последовательности» мы также обрезаем ее, и мы также обрезаем ее от начала буквы 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 меньше самой длинной найденной длины.

Answer 3

Допустим, у вас есть две строки a и b длины n. Самая длинная общая подпоследовательность будет самой длинной подпоследовательностью в строке a, которая также присутствует в строке 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

Answer 4

Для достижения экспоненциального времени достаточно сгенерировать все подпоследовательности обоих массивов и сравнить каждый из них друг с другом. Если вы соответствуете двум одинаковым, проверьте, если их длина больше, чем текущий максимум. Псевдокод будет:

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++;

Это абсолютно не оптимально . Это даже не пытается. Однако вопрос об очень неэффективном алгоритме, поэтому я его предоставил.

Answer 5

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) подпоследовательностей.

Answer 6

По сути, если вы не используете парадигму динамического программирования - вы достигнете экспоненциального времени. Это потому, что, не сохраняя ваши частичные значения - вы пересчитываете частичные значения несколько раз.