Най-дълга обща подпоследователност: Python, C++ Пример

Какво е най-дългата обща подпоследователност?

Най-дългата обща подпоследователност (LCS) означава, че ще ви бъдат дадени два низа, шаблона или поредици от обекти. Сред тези две поредици или низове трябва да намерите най-дългата подпоследователност от елементи в един и същи ред, присъстващи и в двата низа или шаблона.

Пример

Например, са предоставени два низа. Да предположим, че:

Образец_1 = „RGBGARGA“
Pattern_2 = „BGRARG“

• От pattern_1 могат да се генерират последователности като „RGB“, „RGGA“, „RGAR“. За да създадете последователност, трябва да запазите относителната позиция на всеки символ в низа.
• От pattern_2 можем да генерираме последователности като „BGR“, „BRAG“, „RARG“. Последователности могат да бъдат генерирани, стига да запазят относителната позиция на оригиналния низ.

Терминът относителна позиция означава ред.

Например, „BRG“ е валидна последователност, защото „B“ се е появило първо, след това „R“ и накрая „G“ в оригиналния низ pattern_2. Ако обаче последователността е „RBRG“, тя не е валидна, защото в оригиналния низ (pattern_2) „B“ е първо.

Имаме две опции за намиране на най-дългата обща подпоследователност от дадените две последователности или масиви.

• Наивен метод
• Решение за динамично програмиране: Най-дългата обща подпоследователност е известна още като LCS.

Наивното решение има по-голяма времева сложност и не е оптималното решение. Използвайки решението за динамично програмиране (DP), преодоляваме проблема със сложността.

Наивен метод

Наивният метод е прост подход към проблема, независимо от времевата сложност и други фактори за оптимизация. В повечето случаи той се състои от „груба сила“, множество цикли и рекурсивни извиквания. Терминът „груба сила“ означава преминаване през всички възможни модели за даден проблем.

Пример

От горния пример за pattern1 и pattern2, нека приемем, че pattern1 има дължина m, а pattern2 има дължина n. За да проверим всеки възможен случай, трябва да оценим всяка възможна подпоследователност от pattern1 с pattern2.

Ето един прост низ от 4 букви „ABCD“. Например, трябва да създадем поредица от „ABCD“. Можем да вземем или даден символ, или не. Това означава, че за всеки символ имаме два варианта:

• Символът ще бъде добавен към подпоследователността.
• Символът няма да бъде добавен към подпоследователността.

Тук изображенията показват всички последователности, които можем да направим от низа „ABCD“.

Последователност с 1 символ:

Поредици с 2 знака:

Поредици с 3 знака:

От горната диаграма се виждат 14 поредици. Ако не вземем никакви букви, т.е. празен низ, общият брой поредици ще бъде 15. Освен това, самият низ „ABCD“ е поредица. Така че общият брой поредици е 16.

Така че е възможно да се генерират 2^4 или 16 подпоследователности от „ABCD“. След това, низ с дължина m ще има обща подпоследователност от 2^m.

За всяка подпоследователност трябва да я проверим за целия шаблон2. Това ще отнеме O(n) време. O(n) означава функцията на сложност, която изчислява времето, необходимо за изпълнение.

Така общата времева сложност става O(n*2^m). За примера, който видяхме по-горе, стойността на m=8 и n=5.

Ето стъпките на наивния метод:

Стъпка 1) Вземете последователност от шаблон1.
Стъпка 2) Съпоставете последователността от стъпка 1 с шаблон 2.
Стъпка 3) Ако съвпада, запазете подпоследователността.
Стъпка 4) Ако в шаблон 1 са останали още последователности, тогава преминете отново към стъпка 1.
Стъпка 5) Отпечатайте най-дългата подпоследователност.

Оптимална подструктура

Терминът „оптимална подструктура“ означава, че оптимално решение може да се намери чрез решаване на подзадачите. Например, в горния пример имаме модел1 и модел2.

Стъпка 1) Вземете първите два знака от всеки шаблон.

Стъпка 2) Вземете третия до петия знак от всеки модел.

Стъпка 3) Продължете по същия начин с останалите знаци.

Рекурсивна структура на LCS проблем

Намираме НСК на подниз (низ, генериран от оригинален низ). След това записваме дължината на НСК на поднизовете.

Ето още един интересен имот застъпванеping подпроблемиКазва се, че проблемът има припокриванеping подзадачи, ако формулировката на проблема може да бъде разделена на малки подзадачи и използвана няколко пъти в програмата.

Диаграмата по-долу показва, че рекурсивният алгоритъм е извикал функцията с един и същи параметър няколко пъти.

Например, разгледайте дървото на рекурсията. В тъмно оцветената кутия можете да забележите припокриванеping подзадачи. („RG“, „RA“), („RG“, „R“) и други се извикват няколко пъти.

За да оптимизираме това, имаме подхода на Динамично програмиране (DP).

Рекурсивен метод на най-дългата обща подпоследователност

Графиката, показана по-горе, е рекурсивен метод. Всяка рекурсивна функция има базов случай, за да прекъсне рекурсията или да започне връщане от стека си.

За тази имплементация ще използваме базов случай. Така че, алгоритъм е като следното:

• Ако всички елементи преди последния елемент съвпадат, тогава увеличете дължината с едно и върнете резултата.
• Предайте два шаблона на функцията и вземете максималната стойност на връщането.
• Ако един шаблон има нулева дължина, тогава нямаме подпоследователност за сравнение. Върнете 0 в този случай. Това е основният случай на рекурсията.

Прякор Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

Изпълнение в C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Изход:

Length of LCS is: 5

Изпълнение в Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Изход:

Length of LCS is:  5

Метод на динамично програмиране на най-дългата обща подпоследователност (LCS)

Динамичното програмиране означава оптимизиране на обикновения рекурсивен метод. Например, ако разгледаме графиката на рекурсивния или наивен подход, можем да видим, че има няколко еднакви извиквания на функции. Методът на динамично програмиране записва всички изчисления в масив и ги използва повторно, когато е необходимо.

Ще използваме 2D масив с размери mxn, където m и n са дължините на pattern1 и pattern2. За a 2D масив, можем да използваме структури от данни List в Python или векторни/масивни структури от данни в C++.

Прякор Code за LCS, използващ DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Ето таблицата LCS, която се използва като 2D масивна структура от данни за подхода на динамично програмиране.

Нека обсъдим логиката, която използвахме тук. Стъпките са:

Стъпка 1) Ако i или j е нула, вземаме празен низ от дадените два низа и се опитваме да намерим общите подпоследователности. Тъй като обаче поднизът, който вземаме, е празен, дължината на подпоследователността е 0.

Стъпка 2) Ако два символа съвпадат, ще присвоим стойността на индекса (i,j), като увеличим предварително изчислената НСК, която присъства в индекса (i-1,j-1) (от предишния ред).

Стъпка 3) Ако не съвпада, тогава ще вземем максималната НСК на двата съседни индекса. И по този начин трябва да запълним всички стойности в 2D масива.

Стъпка 4) Накрая ще върнем стойността на последната клетка от 2D масива.

По принцип всички стойности в 2D масива съдържат дължината на общите подпоследователности. Сред тях последната клетка съдържа дължината на най-дългата обща подпоследователност.

Изпълнение в C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Изход:

Length of LCS: 5

Изпълнение в Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Изход:

Length of LCS: 5

И така, и двата низа имат най-дългата обща подпоследователност с дължина 5.

Накратко, ние просто изчисляваме всяка задача веднъж в метода DP. В рекурсивния метод може да имаме припокриване.ping подпроблеми.

В този алгоритъм за динамично програмиране ние използваме 2D матрица. Ще бъдат дадени два низа (да приемем, че и двата имат дължина n). Тогава необходимото пространство в масива е nx n. Ако низовете са достатъчно големи, ще ни трябва оптимизирана за памет версия на DP решението.

Опростената логика, която беше взета в кода, е:

• Декларирайте 2D масив DP[m][n].
• Попълнете първия ред и първата колона на DP масива с 0.
• Вземете i и j за итерацията.
• Ако pattern1[i] е равно на pattern2[j], тогава актуализирайте DP[i][j] = DP[i-1][j-1] + 1.
• Ако pattern1[i] не е равно на pattern2[j], тогава DP[i][j] ще бъде максималната стойност между DP[i-1][j] и DP[i][j-1].
• Продължете, докато i и j достигнат m и n.
• Последният елемент, DP[m-1][n-1], ще съдържа дължината.

Тук е адресиран като DP[m-1][n-1], защото индексът на масива започва от 0.

Въпроси и Отговори