Найдовша загальна підпослідовність: Python, C++ Приклад

Що таке найдовша спільна підпослідовність?

Найдовша загальна підпослідовність (LCS) означає, що вам буде надано два рядки/шаблони/послідовності об’єктів. Серед цих двох послідовностей/рядків вам потрібно знайти найдовшу підпослідовність елементів в одному порядку, присутніх в обох рядках або шаблонах.

Приклад

Наприклад, є два рядки.

Припустимо,

Шаблон_1 = “RGBGARGA”
Шаблон_2 = «BGRARG»

З шаблону_1 можна створити такі послідовності, як «RGB», «RGGA», «RGAR». Щоб створити послідовність, вам потрібно зберегти взаємну позицію кожного символу в рядку.
З шаблону_2 ми можемо створити такі послідовності, як «BGR», «BRAG», «RARG». Послідовності можна створювати, якщо вони зберігають відносну позицію вихідного рядка.

Термін відносне розташування означає порядок.

Наприклад, «BRG» є правильною послідовністю, оскільки спочатку з’явилося «B», потім «R», а потім «G» у вихідному рядку pattern_2. Однак якщо послідовність є «RBRG», вона недійсна. Тому що в оригінальному рядку (шаблон_2) першим стоїть «B».

У нас є два варіанти пошуку найдовшої спільної підпослідовності з заданих двох послідовностей або масивів.

Наївний метод
Рішення для динамічного програмування: найдовша загальна підпослідовність також відома як LCS.

Наївне рішення має більшу часову складність і не є оптимальним рішенням. Використовуючи рішення для динамічного програмування (DP), ми долаємо проблему складності.

Наївний метод

Наївний метод – простий підхід до проблеми незалежно від часової складності та інших факторів оптимізації.

Наївний метод складається з «грубої сили», кількох циклів, рекурсивних методів у більшості випадків.

Термін груба сила означає проходження всіх можливих шаблонів для даної проблеми.

Приклад

З наведеного вище прикладу pattern1 і pattern2 припустимо, що pattern1 має довжину m, а pattern2 має довжину n. Щоб перевірити всі можливі випадки, нам потрібно оцінити кожну можливу підпослідовність шаблону1 з шаблоном2.

Ось простий рядок із 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) Візьміть послідовність із шаблону1.
Крок 2) Зіставте послідовність із кроку 1 із шаблоном 2.
Крок 3) Якщо збігається, то збережіть підпослідовність.
Крок 4) Якщо в шаблоні 1 залишилося більше послідовності, перейдіть до кроку 1 знову.
Крок 5) Вивести найдовшу підпослідовність.

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

Термін оптимальна підструктура означає, що оптимальне (просте) рішення можна знайти шляхом розв’язання підпроблем. Наприклад, у наведеному вище прикладі ми маємо шаблон1 і шаблон2.

Крок 1) Візьміть перші два символи з кожного шаблону

Крок 2) Візьміть третій-п’ятий символи з кожного шаблону.

Крок 3) Продовжуйте аналогічно з іншими символами.

Оптимальна підструктура — Рекурсивна структура задачі LCS

Ми знаходимо LCS у підрядку (рядку, згенерованому з оригінального рядка). Потім ми ведемо запис довжини LCS підрядків.

Ось ще одна цікава властивість перекриваються підпроблеми. Кажуть, що проблема має підпроблеми, що перекриваються, якщо формулювання проблеми можна розбити на невеликі підпроблеми та використати кілька разів у програмі.

На діаграмі нижче показано, що рекурсивний алгоритм кілька разів викликав функцію з одним і тим же параметром.

Для прикладу розглянемо дерево рекурсії.

У рамці темного кольору ви можете помітити підпроблеми, що збігаються. («RG», «RA»), («RG», «R») та інші викликаються кілька разів.

Для оптимізації цього у нас є підхід Динамічне програмування (ДП).

Рекурсивний метод найдовшої послідовності зв’язку

Наведений вище графік є рекурсивним методом. Кожна рекурсивна функція має базовий випадок для розриву рекурсії або початку повернення зі свого стеку.

Для цієї реалізації ми будемо використовувати базовий випадок. Отже, алгоритм виглядає наступним чином:

Якщо всі елементи перед останнім елементом збігаються, збільште довжину на одиницю та поверніться
Передайте функції два шаблони та візьміть максимальне значення повернення
Якщо один шаблон має нульову довжину, то у нас немає підпослідовності для порівняння. У цьому випадку повертає 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 — довжини шаблону1 і шаблону2.

для 2D масив, ми можемо використовувати структури даних List у python або структури даних vector/array у 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, яка використовується як структура даних двовимірного масиву для підходу динамічного програмування.

Давайте обговоримо логіку, яку ми тут використали. Кроки:

Крок 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. У рекурсивному методі ми можемо мати підпроблеми, що перекриваються.

У цьому алгоритмі динамічного програмування ми використовуємо двовимірну матрицю. Буде подано два рядки (припустимо, що обидва мають довжину n). Тоді необхідний простір у масиві становить nx n. Якщо рядки достатньо великі, нам знадобиться оптимізована для пам’яті версія рішення DP.

Спрощена логіка, яка була використана в коді:

Оголошення двовимірного масиву DP[m][n].
Заповніть перший рядок і перший стовпець масиву DP 0.
Візьміть i та j для ітерації.
Якщо шаблон1[i] дорівнює шаблону2[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(mn), де m і n - довжина вхідного рядка або масиву.
DP є швидшим підходом, ніж рекурсивний, з часовою складністю O(n*2^m).
Динамічне програмування (DP) не оптимізоване пам'ять. Ми використали 2D-масив довжиною m*n. Отже, складність простору становить (m*n).
Рекурсивний метод, у найгіршому випадку, найбільший обсяг пам’яті, який він займатиме, буде m+n, тобто загальна довжина введеного рядка.
Сучасного комп’ютера достатньо для роботи з таким об’ємом пам’яті.

Що таке найдовша спільна підпослідовність?

Приклад

Наївний метод

Приклад

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

СТАТТІ ПО ТЕМІ

Рекурсивний метод найдовшої послідовності зв’язку

Реалізація в C++

Реалізація на python

Метод динамічного програмування найдовшої спільної підпослідовності (LCS)

Реалізація в C++

Реалізація в Python

Підсумки

Підпишіться на розсилку