Рубрики

Самая длинная общая подпоследовательность | ДП-4

Мы обсудили свойства перекрывающихся подзадач и оптимальной подструктуры в наборе 1 и наборе 2 соответственно. Мы также обсудили один пример проблемы в наборе 3 . Давайте обсудим проблему Longest Common Subsequence (LCS) как еще одну примерную проблему, которая может быть решена с помощью динамического программирования.

Постановка задачи LCS: Учитывая две последовательности, найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность — это последовательность, которая появляется в том же относительном порядке, но не обязательно является смежной. Например, «abc», «abg», «bdf», «aeg», «acefg» и т. Д. Являются подпоследовательностями «abcdefg».

Чтобы выяснить сложность подхода грубой силы, нам нужно сначала узнать количество возможных различных подпоследовательностей строки с длиной n, т. Е. Найти количество подпоследовательностей с длинами в диапазоне от 1,2, .. n-1 , Напомним из теории перестановок и комбинаций, что число комбинаций с 1 элементом равно n C 1 . Количество комбинаций с 2 элементами: n C 2 и т. Д. И т. Д. Мы знаем, что n C 0 + n C 1 + n C 2 +… n C n = 2 n . Таким образом, строка длиной n имеет 2 n -1 различных возможных подпоследовательностей, так как мы не рассматриваем подпоследовательность длиной 0. Это означает, что временная сложность подхода грубой силы будет O (n * 2 n ). Обратите внимание, что требуется O (n) время, чтобы проверить, является ли подпоследовательность общей для обеих строк. Эта временная сложность может быть улучшена с помощью динамического программирования.

Это классическая проблема информатики, основа diff (программа сравнения файлов, которая выводит различия между двумя файлами) и имеет приложения в биоинформатике.

Примеры:
LCS для входных последовательностей «ABCDGH» и «AEDFHR» — это «ADH» длины 3.
LCS для входных последовательностей «AGGTAB» и «GXTXAYB» — это «GTAB» длины 4.

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

1) Оптимальная подструктура:
Пусть входными последовательностями являются X [0..m-1] и Y [0..n-1] длин m и n соответственно. И пусть L (X [0..m-1], Y [0..n-1]) будет длиной LCS двух последовательностей X и Y. Ниже приводится рекурсивное определение L (X [0 .. m-1], Y [0..n-1]).

Если последние символы обеих последовательностей совпадают (или X [m-1] == Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = 1 + L (X [0..m-2], Y [0..n-2])

Если последние символы обеих последовательностей не совпадают (или X [m-1]! = Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = MAX (L (X [0..m-2], Y [0..n-1]), L ( X [0..m-1], Y [0..n-2]))

Примеры:
1) Рассмотрим входные строки «AGGTAB» и «GXTXAYB». Последние символы совпадают для строк. Таким образом, длина LCS может быть записана как:
L («AGGTAB», «GXTXAYB») = 1 + L («AGGTA», «GXTXAY»)

2) Рассмотрим входные строки «ABCDGH» и «AEDFHR. Последние символы не совпадают для строк. Таким образом, длина LCS может быть записана как:
L («ABCDGH», «AEDFHR») = MAX (L («ABCDG», «AEDFH R »), L («ABCDG H », «AEDFH»))

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

2) Перекрывающиеся подзадачи:
Ниже приводится простая рекурсивная реализация проблемы LCS. Реализация просто следует рекурсивной структуре, упомянутой выше.

C ++

/ * Наивная рекурсивная реализация задачи LCS * /
#include <bits/stdc++.h>

using namespace std;

  

int max(int a, int b); 

  
/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

int lcs( char *X, char *Y, int m, int n ) 

    if (m == 0 || n == 0) 

        return 0; 

    if (X[m-1] == Y[n-1]) 

        return 1 + lcs(X, Y, m-1, n-1); 

    else

        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b) 

    return (a > b)? a : b; 

  
/ * Код водителя * /

int main() 

    char X[] = "AGGTAB"

    char Y[] = "GXTXAYB"

      

    int m = strlen(X); 

    int n = strlen(Y); 

      

    cout<<"Length of LCS is "<< lcs( X, Y, m, n ) ; 

      

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

/ * Наивная рекурсивная реализация задачи LCS * /
#include<bits/stdc++.h>

  

int max(int a, int b);

  
/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

int lcs( char *X, char *Y, int m, int n )

{

   if (m == 0 || n == 0)

     return 0;

   if (X[m-1] == Y[n-1])

     return 1 + lcs(X, Y, m-1, n-1);

   else

     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

}

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b)

{

    return (a > b)? a : b;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  char X[] = "AGGTAB";

  char Y[] = "GXTXAYB";

  

  int m = strlen(X);

  int n = strlen(Y);

  

  printf("Length of LCS is %d", lcs( X, Y, m, n ) );

  

  return 0;

}

Джава

/ * Наивная рекурсивная реализация проблемы LCS в Java * /

public class LongestCommonSubsequence

{

  

  / * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

  int lcs( char[] X, char[] Y, int m, int n )

  {

    if (m == 0 || n == 0)

      return 0;

    if (X[m-1] == Y[n-1])

      return 1 + lcs(X, Y, m-1, n-1);

    else

      return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

  }

  

  / * Функция полезности для получения максимум 2 целых чисел * /

  int max(int a, int b)

  {

    return (a > b)? a : b;

  }

  

  public static void main(String[] args)

  {

    LongestCommonSubsequence lcs = new LongestCommonSubsequence();

    String s1 = "AGGTAB";

    String s2 = "GXTXAYB";

  

    char[] X=s1.toCharArray();

    char[] Y=s2.toCharArray();

    int m = X.length;

    int n = Y.length;

  

    System.out.println("Length of LCS is" + " " +

                                  lcs.lcs( X, Y, m, n ) );

  }

  
}

  
// Этот код предоставлен Сакет Кумар

питон

# Наивная рекурсивная реализация проблемы LCS на Python

  

def lcs(X, Y, m, n):

  

    if m == 0 or n == 0:

       return 0;

    elif X[m-1] == Y[n-1]:

       return 1 + lcs(X, Y, m-1, n-1);

    else:

       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

  

  
# Драйвер программы для проверки вышеуказанной функции

X = "AGGTAB"

Y = "GXTXAYB"

print "Length of LCS is ", lcs(X , Y, len(X), len(Y))

C #

/ * C # Наивная рекурсивная реализация задачи LCS * /

using System;

  

class GFG

{

      

  

    / * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

    static int lcs( char[] X, char[] Y, int m, int n )

    {

        if (m == 0 || n == 0)

        return 0;

        if (X[m - 1] == Y[n - 1])

        return 1 + lcs(X, Y, m - 1, n - 1);

        else

        return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));

    }

      

    / * Функция полезности для получения максимум 2 целых чисел * /

    static int max(int a, int b)

    {

        return (a > b)? a : b;

    }

      

    public static void Main()

    {

        String s1 = "AGGTAB";

        String s2 = "GXTXAYB";

      

        char[] X=s1.ToCharArray();

        char[] Y=s2.ToCharArray();

        int m = X.Length;

        int n = Y.Length;

      

        Console.Write("Length of LCS is" + " " 

                      +lcs( X, Y, m, n ) );

    }

}
// Этот код предоставлен Sam007

PHP

<?php 
// Наивный рекурсивный PHP
// реализация проблемы LCS

function lcs($X, $Y, $m, $n)

    if($m == 0 || $n == 0) 

    return 0; 

    else if ($X[$m - 1] == $Y[$n - 1]) 

        return 1 + lcs($X, $Y

                       $m - 1, $n - 1); 

    else

        return max(lcs($X, $Y, $m, $n - 1), 

                   lcs($X, $Y, $m - 1, $n)); 

}

  
// Код драйвера

$X = "AGGTAB";

$Y = "GXTXAYB";

echo "Length of LCS is ";

echo lcs($X , $Y, strlen($X),

                  strlen($Y)); 

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Length of LCS is 4

Временная сложность описанного выше наивного рекурсивного подхода в худшем случае составляет O (2 ^ n), а худший случай возникает, когда все символы X и Y не совпадают, т. Е. Длина LCS равна 0.
Учитывая вышеописанную реализацию, ниже приведено дерево частичной рекурсии для входных строк «AXYT» и «AYZX».

                         lcs("AXYT", "AYZX")
                       /                 
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /                              /               
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

В приведенном выше дереве частичной рекурсии lcs («AXY», «AYZ») решается дважды. Если мы нарисуем полное дерево рекурсии, то увидим, что есть много подзадач, которые решаются снова и снова. Таким образом, эта проблема имеет свойство «Перекрывающаяся подструктура», и повторного вычисления тех же подзадач можно избежать, используя Memoization или Tabulation. Ниже приведена табличная реализация проблемы LCS.

C ++

/ * Динамическое программирование C ++ реализация проблемы LCS * /
#include<bits/stdc++.h> 

using namespace std;

  

int max(int a, int b); 

  
/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

int lcs( char *X, char *Y, int m, int n ) 

    int L[m + 1][n + 1]; 

    int i, j; 

      

    / * Следуя шагам, строим L [m + 1] [n + 1] в

       снизу вверх мода. Обратите внимание, что L [i] [j]

       содержит длину LCS X [0..i-1]

       и Y [0..j-1] * /

    for (i = 0; i <= m; i++) 

    

        for (j = 0; j <= n; j++) 

        

        if (i == 0 || j == 0) 

            L[i][j] = 0; 

      

        else if (X[i - 1] == Y[j - 1]) 

            L[i][j] = L[i - 1][j - 1] + 1; 

      

        else

            L[i][j] = max(L[i - 1][j], L[i][j - 1]); 

        

    

          

    / * L [m] [n] содержит длину LCS

    для X [0..n-1] и Y [0..m-1] * /

    return L[m][n]; 

  
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b) 

    return (a > b)? a : b; 

  
// Код драйвера

int main() 

    char X[] = "AGGTAB"

    char Y[] = "GXTXAYB"

      

    int m = strlen(X); 

    int n = strlen(Y); 

      

    cout << "Length of LCS is " 

         << lcs( X, Y, m, n ); 

      

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

/ * Динамическое программирование C реализация задачи LCS * /
#include<bits/stdc++.h>

   

int max(int a, int b);

   
/ * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

int lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   int i, j;

   

   / * Следуя шагам, соберите L [m + 1] [n + 1] снизу вверх. Заметка

      что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1] * /

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

   

       else if (X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

   

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }

     

   / * L [m] [n] содержит длину LCS для X [0..n-1] и Y [0..m-1] * /

   return L[m][n];

}

   
/ * Функция полезности для получения максимум 2 целых чисел * /

int max(int a, int b)

{

    return (a > b)? a : b;

}

   
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  char X[] = "AGGTAB";

  char Y[] = "GXTXAYB";

   

  int m = strlen(X);

  int n = strlen(Y);

   

  printf("Length of LCS is %d", lcs( X, Y, m, n ) );

  

  return 0;

}

Джава

/ * Динамическое программирование Java реализация проблемы LCS * /

public class LongestCommonSubsequence

{

  

  / * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

  int lcs( char[] X, char[] Y, int m, int n )

  {

    int L[][] = new int[m+1][n+1];

  

    / * Следуя шагам, соберите L [m + 1] [n + 1] снизу вверх. Заметка

         что L [i] [j] содержит длину LCS из X [0..i-1] и Y [0..j-1] * /

    for (int i=0; i<=m; i++)

    {

      for (int j=0; j<=n; j++)

      {

        if (i == 0 || j == 0)

            L[i][j] = 0;

        else if (X[i-1] == Y[j-1])

            L[i][j] = L[i-1][j-1] + 1;

        else

            L[i][j] = max(L[i-1][j], L[i][j-1]);

      }

    }

  return L[m][n];

  }

  

  / * Функция полезности для получения максимум 2 целых чисел * /

  int max(int a, int b)

  {

    return (a > b)? a : b;

  }

  

  public static void main(String[] args)

  {

    LongestCommonSubsequence lcs = new LongestCommonSubsequence();

    String s1 = "AGGTAB";

    String s2 = "GXTXAYB";

  

    char[] X=s1.toCharArray();

    char[] Y=s2.toCharArray();

    int m = X.length;

    int n = Y.length;

  

    System.out.println("Length of LCS is" + " " +

                                  lcs.lcs( X, Y, m, n ) );

  }

  
}

  
// Этот код предоставлен Сакет Кумар

питон

# Динамическое программирование реализации задачи LCS

  

def lcs(X , Y):

    # найти длину строк

    m = len(X)

    n = len(Y)

  

    # объявление массива для хранения значений dp

    L = [[None]*(n+1) for i in xrange(m+1)]

  

    "" "Следующими шагами создайте L [m + 1] [n + 1] снизу вверх

    Примечание: L [i] [j] содержит длину LCS из X [0..i-1]

    и Y [0..j-1] "" "

    for i in range(m+1):

        for j in range(n+1):

            if i == 0 or j == 0 :

                L[i][j] = 0

            elif X[i-1] == Y[j-1]:

                L[i][j] = L[i-1][j-1]+1

            else:

                L[i][j] = max(L[i-1][j] , L[i][j-1])

  

    # L [m] [n] содержит длину LCS из X [0..n-1] & Y [0..m-1]

    return L[m][n]

# конец функции lcs

  

  
# Драйвер программы для проверки вышеуказанной функции

X = "AGGTAB"

Y = "GXTXAYB"

print "Length of LCS is ", lcs(X, Y)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// Динамическое программирование C # реализация
// проблемы LCS

using System;

  

class GFG

{

  

    / * Возвращает длину LCS для X [0..m-1], Y [0..n-1] * /

    static int lcs( char[] X, char[] Y, int m, int n )

    {

        int [,]L = new int[m+1,n+1];

      

        / * Следующие шаги построить L [m + 1] [n + 1]

        в моде снизу вверх. Заметка

        что L [i] [j] содержит длину

        LCS из X [0..i-1] и Y [0..j-1] * /

        for (int i = 0; i <= m; i++)

        {

            for (int j = 0; j <= n; j++)

            {

                if (i == 0 || j == 0)

                    L[i, j] = 0;

                else if (X[i - 1] == Y[j - 1])

                    L[i, j] = L[i - 1, j - 1] + 1;

                else

                    L[i, j] = max(L[i - 1, j], L[i, j - 1]);

            }

        }

        return L[m, n];

    }

      

    / * Функция полезности для получения максимум 2 целых чисел * /

    static int max(int a, int b)

    {

        return (a > b)? a : b;

    }

      

    // Код драйвера

    public static void Main()

    {

          

        String s1 = "AGGTAB";

        String s2 = "GXTXAYB";

      

        char[] X=s1.ToCharArray();

        char[] Y=s2.ToCharArray();

        int m = X.Length;

        int n = Y.Length;

      

        Console.Write("Length of LCS is" + " " +lcs( X, Y, m, n ) );

    }

}
// Этот код предоставлен Sam007

PHP

<?php 
// Динамическое программирование C #
// реализация проблемы LCS

function lcs($X , $Y)

{
// найти длину строки

$m = strlen($X); 

$n = strlen($Y) ;

  
// объявляем массив для
// сохраняем значения dp

  
/ * Следующие шаги построить L [m + 1] [n + 1]
в моде снизу вверх.
Примечание: L [i] [j] содержит длину
LCS из X [0..i-1] и Y [0..j-1] * /

for ($i = 0; $i <= $m; $i++) 

for ($j = 0; $j <= $n; $j++) 

    if ($i == 0 || $j == 0) 

    $L[$i][$j] = 0; 

  

    else if ($X[$i - 1] == $Y[$j - 1]) 

    $L[$i][$j] = $L[$i - 1][$j - 1] + 1; 

  

    else

    $L[$i][$j] = max($L[$i - 1][$j],

                     $L[$i][$j - 1]); 


  
// L [m] [n] содержит длину
// LCS из X [0..n-1] & Y [0..m-1]

  

return $L[$m][$n];

}

  
// Код драйвера

$X = "AGGTAB";

$Y = "GXTXAYB";

echo "Length of LCS is ";

echo lcs($X, $Y); 

  
// Этот код добавлен
// от Shivi_Aggarwal
?>


Выход:

Length of LCS is 4

Сложность по времени в приведенной выше реализации равна O (mn), что намного лучше, чем сложность по времени в наивнейшей рекурсивной реализации в худшем случае.

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

Вы также можете проверить оптимизированную для пространства версию LCS по адресу
Космическое оптимизированное решение LCS

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Последние статьи на основе LCS!

Ссылки:
http://www.youtube.com/watch?v=V5hZoJ6uK-s
http://www.algorithmist.com/index.php/Longest_Common_Subsequence
http://www.ics.uci.edu/~eppstein/161/960229.html
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Рекомендуемые посты:

Самая длинная общая подпоследовательность | ДП-4

0.00 (0%) 0 votes