Najdłuższy wspólny podciąg: Python, C++ Przykład

Jaki jest najdłuższy wspólny podciąg?

Najdłuższy wspólny podciąg (LCS) oznacza, że ​​otrzymasz dwa ciągi/wzorce/sekwencje obiektów. Spośród tych dwóch sekwencji/ciągów należy znaleźć najdłuższy podciąg elementów w tej samej kolejności, występujący w obu ciągach lub wzorach.

Przykład

Na przykład dostępne są dwa ciągi znaków.

Załóżmy, że

Wzór_1 = „RGBGARGA”
Wzór_2 = „BGRARG”

• Ze wzoru_1 można utworzyć sekwencje takie jak „RGB”, „RGGA”, „RGAR”. Aby utworzyć sekwencję, należy zachować względną pozycję każdego znaku w ciągu.
• Z wzorca_2 możemy wygenerować sekwencje takie jak „BGR”, „BRAG”, „RARG”. Sekwencje można tworzyć, o ile zachowują względną pozycję oryginalnego ciągu.

Termin pozycja względna oznacza porządek.

Na przykład „BRG” jest prawidłową sekwencją, ponieważ w oryginalnym ciągu znaków wzorzec_2 pojawiło się najpierw „B”, następnie „R”, a następnie „G”. Jeśli jednak sekwencja to „RBRG”, jest ona nieprawidłowa. Ponieważ w oryginalnym ciągu znaków (wzorzec_2) „B” jest na pierwszym miejscu.

Mamy dwie możliwości znalezienia najdłuższego wspólnego podciągu z podanych dwóch sekwencji lub tablic.

• Naiwna metoda
• Rozwiązanie do programowania dynamicznego: najdłuższy wspólny podciąg jest również znany jako LCS.

Naiwne rozwiązanie ma większą złożoność czasową i nie jest rozwiązaniem optymalnym. Używając Dynamic Programming Solution (DP) pokonujemy problem złożoności.

Metoda naiwna

Metoda naiwna to proste podejście do problemu, niezależne od złożoności czasowej i innych czynników optymalizacyjnych.

Metoda naiwna składa się z „Brute Force”, wielu pętli i w większości przypadków metod rekurencyjnych.

Termin brutalna siła oznacza przejście przez wszystkie możliwe wzorce dla danego problemu.

Przykład

Na podstawie powyższego przykładu wzoru1 i wzoru2 załóżmy, że wzór1 ma długość m, a wzór2 ma długość n. Aby sprawdzić każdy możliwy przypadek, musimy ocenić każdy możliwy podciąg wzorca 1 za pomocą wzorca 2.

Oto prosty 4-literowy ciąg „ABCD”. Na przykład musimy utworzyć sekwencję z „ABCD”. Albo możemy przyjąć postać, albo nie. Oznacza to, że dla każdej postaci mamy dwie możliwości.

Są to:

• Znak zostanie dodany do podciągu.
• Znak nie zostanie dodany do podciągu.

Tutaj rysunki pokazują wszystkie sekwencje, które możemy ułożyć ze ciągu „ABCD”.

Sekwencja z 1 znakiem:

Sekwencje z 2 znakami:

Sekwencje z 3 znakami:

Z powyższego diagramu wynika, że ​​jest 14 sekwencji. Jeśli nie weźmiemy liter, w zasadzie pustego ciągu, całkowita liczba sekwencji wyniesie 15. Co więcej, sam ciąg „ABCD” jest sekwencją. Zatem całkowita liczba ciągów wynosi 16.

Zatem możliwe jest wygenerowanie 2⁴ lub 16 podciągów z „ABCD”. Następnie ciąg o długości m będzie musiał sumować podciąg liczby 2^m.

Dla każdego podciągu musimy sprawdzić cały wzorzec2. Zajmie to 0(n) czasu. 0(n) oznacza funkcję złożoności, która oblicza czas potrzebny na wykonanie.

Całkowita złożoność czasowa staje się zatem O(n*2^m). Dla przykładu widzieliśmy powyżej wartość m=8 i n=5.

Oto kroki metody naiwnej:

Krok 1) Weź sekwencję ze wzoru 1.
Krok 2) Dopasuj sekwencję z kroku 1 do wzoru 2.
Krok 3) Jeśli pasuje, zapisz podciąg.
Krok 4) Jeśli we wzorze 1 pozostało więcej sekwencji, przejdź ponownie do kroku 1.
Krok 5) Wydrukuj najdłuższy podciąg.

Optymalna podkonstrukcja

Termin optymalna podstruktura oznacza, że ​​optymalne rozwiązanie (proste) można znaleźć poprzez rozwiązanie podproblemów. Na przykład w powyższym przykładzie mamy wzór1 i wzór2.

Krok 1) Weź pierwsze dwa znaki z każdego wzoru

Krok 2) Weź od trzeciego do piątego znaku z każdego wzoru.

Krok 3) Postępuj podobnie z pozostałymi znakami.

Znajdujemy LCS w podciągu (ciąg wygenerowany z oryginalnego ciągu). Następnie prowadzimy zapis długości LCS podciągów.

Oto kolejna interesująca właściwość nakładające się podproblemy. Mówi się, że problem ma nakładające się podproblemy, jeśli sformułowanie problemu można podzielić na małe podproblemy i użyć go kilka razy w programie.

Poniższy diagram pokazuje, że algorytm rekurencyjny wywoływał funkcję z tym samym parametrem kilka razy.

Przyjrzyjmy się na przykład drzewu rekurencji.

W ciemnym polu można zauważyć zachodzące na siebie podproblemy. („RG”, „RA”), („RG”, „R”) i inne są wywoływane kilkakrotnie.

Aby to zoptymalizować, mamy podejście Programowanie dynamiczne (DP).

Metoda rekurencyjna najdłuższej sekwencji komunikacyjnej

Wykres pokazany powyżej jest metodą rekurencyjną. Każda funkcja rekurencyjna ma przypadek podstawowy umożliwiający przerwanie rekurencji lub rozpoczęcie powrotu ze stosu.

W tej implementacji użyjemy przypadku podstawowego. Zatem, algorytm wygląda następująco:

• Jeśli wszystkie elementy przed ostatnim elementem są zgodne, zwiększ długość o jeden i wróć
• Przekaż do funkcji dwa wzorce i przyjmij maksymalną wartość zwrotu
• Jeśli jeden wzór ma zerową długość, nie mamy żadnego podciągu do porównania. W tym przypadku zwróć 0. Jest to podstawowy przypadek rekurencji.

Pseudo kod:

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)

wdrożenie w 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;
}

Wyjście:

Length of LCS is: 5

Implementacja w Pythonie

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)))

Wyjście:

Lenght of LCS is:  5

Metoda programowania dynamicznego najdłuższego wspólnego podciągu (LCS)

Programowanie dynamiczne oznacza optymalizację zwykłej metody rekurencyjnej. Na przykład, jeśli zobaczymy wykres podejścia rekurencyjnego lub naiwnego, zobaczymy, że istnieje kilka takich samych wywołań funkcji. Metoda programowania dynamicznego rejestruje wszystkie obliczenia w tablicy i wykorzystuje je w razie potrzeby.

Użyjemy tablicy 2D o wymiarach mxn, gdzie m i n to długości wzorca1 i wzorca2.

W razie zamówieenia projektu Tablica 2Dmożemy używać struktur danych List w Pythonie lub struktur danych wektorowych/tablicowych w C++.

Pseudokod dla LCS przy użyciu 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]

Oto tabela LCS używana jako struktura danych tablicowych 2D w podejściu do programowania dynamicznego.

Omówmy logikę, którą tutaj zastosowaliśmy. Kroki to:

Krok 1) Jeśli i lub j wynosi zero, bierzemy pusty ciąg z podanych dwóch ciągów i próbujemy znaleźć wspólne podciągi. Ponieważ jednak podciąg, który bierzemy, jest pusty, długość podciągu wynosi 0.

Krok 2) Jeśli pasują dwa znaki, przypiszemy wartość do indeksu (i,j), zwiększając wcześniej obliczony LCS, który jest obecny w indeksie (i-1,j-1) (z poprzedniego wiersza).

Krok 3) Jeśli nie pasuje, weźmiemy maksymalny LCS z dwóch sąsiednich indeksów. W ten sposób musimy wypełnić wszystkie wartości w tablicy 2D.

Krok 4) Na koniec zwrócimy wartość ostatniej komórki tablicy 2D.

Zasadniczo cała wartość w tablicy 2D zawiera długość wspólnych podciągów. Spośród nich ostatnia komórka zawiera długość najdłuższego wspólnego podciągu.

wdrożenie w 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;
}

Wyjście:

Length of LCS: 5

wdrożenie w 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))

Wyjście:

Length of LCS: 5

Zatem oba ciągi mają najdłuższy wspólny podciąg o długości 5.

Krótko mówiąc, po prostu obliczamy każde zadanie raz w metodzie DP w metodzie DP. W metodzie rekurencyjnej możemy mieć nakładające się podproblemy.

W tym algorytmie programowania dynamicznego używamy macierzy 2D. Podane zostaną dwa ciągi znaków (zakładając, że oba mają długość n). Wtedy miejsce potrzebne w tablicy wynosi nx n. Jeśli ciągi znaków są wystarczająco duże, będziemy potrzebować zoptymalizowanej pod kątem pamięci wersji rozwiązania DP.

Uproszczona logika przyjęta w kodzie to:

• Zadeklaruj tablicę 2D DP[m][n].
• Wypełnij pierwszy wiersz i pierwszą kolumnę tablicy DP wartością 0.
• Weź i i j dla iteracji.
• Jeśli wzór1[i] jest równy wzorcowi2[j], zaktualizuj DP[i][j] = DP[i-1][j-1] + 1
• Jeśli wzór1[i] nie jest równy wzorcowi2[j], wówczas DP[i][j] będzie maksymalną wartością pomiędzy DP[i-1][j] a DP[i][j-1].
• Kontynuuj, aż i i j dotrą do m i n.
• Ostatni element, czyli DP[m-1][n-1], będzie zawierał długość.

Tutaj jest on adresowany jako DP[m-1][n-1], ponieważ indeks tablicy zaczyna się od 0.

Podsumowanie

• Metoda DP charakteryzuje się mniejszą złożonością czasową; wynosi ona O(mn), gdzie m i n to długość ciągu wejściowego lub tablicy.
• DP jest szybszym podejściem niż rekurencyjne, ze względu na złożoność czasową O(n*2^m).
• Programowanie dynamiczne (DP) nie jest zoptymalizowane pod kątem pamięci. Użyliśmy tablicy 2D o długości m*n. Zatem złożoność przestrzenna wynosi (m*n).
• Metoda rekurencyjna, w najgorszym przypadku najwyższa pamięć, jaką zajmie, będzie wynosić m+n, czyli w zasadzie całkowita długość wprowadzonego ciągu.
• Dzisiejszy nowoczesny komputer jest w stanie obsłużyć taką ilość pamięci.