Най-дълга обща подпоследователност: 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.

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

Наивен метод

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

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

Терминът груба сила означава преминаване през всички възможни модели за даден проблем.

Пример

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

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

Те са:

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

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

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

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

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

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

И така, възможно е да генерирате 2⁴ или 16 подпоследователности от “ABCD”. След това, низ с дължина от m ще трябва да има обща подпоследователност от 2^m.

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

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

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

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

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

Терминът оптимална подструктура означава оптимално решение (просто), което може да бъде намерено чрез решаване на подпроблемите. Например в горния пример имаме pattern1 и pattern2.

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

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

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

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

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

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

Например, нека видим дървото на рекурсията.

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

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

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

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

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

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

Псевдо код:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Изход:

Lenght of LCS is:  5

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

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

Ще използваме 2D масив с размери mxn, където m и n са дължините на pattern1 и pattern2.

За 2D масив, можем да използваме структури от данни List в python или векторни/масивни структури от данни в C++.

Псевдо код за 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) чрез увеличаване на предварително изчисления LCS, който присъства в индекса (i-1,j-1) (от предишния ред).

Стъпка 3) Ако не съвпада, тогава ще вземем максималния LCS на съседните два индекса. И по този начин трябва да попълним всички стойности в 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 & lt; n + 1; i++) {
    for (int j = 0; j & lt; 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 в метода DP. При рекурсивния метод може да имаме припокриващи се подпроблеми.

В този алгоритъм за динамично програмиране ние използваме 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
• Ако шаблон1[i] не е равен на шаблон2[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.

Oбобщение

• Методът DP има по-ниска времева сложност; това е O(mn), където m и n са дължината на входния низ или масив.
• DP е по-бърз подход от рекурсивния, с времевата сложност на O(n*2^m).
• Динамичното програмиране (DP) не е оптимизирано за памет. Използвахме 2D масив с дължина m*n. И така, пространствената сложност е (m*n).
• Рекурсивен метод, в най-лошия сценарий най-голямата памет, която ще заема, ще бъде m+n, общо взето общата дължина на въведения низ.
• Днешният модерен компютър е достатъчен, за да се справи с това количество памет.