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 znaków, wzory lub sekwencje obiektów. Spośród tych dwóch ciągów znaków lub sekwencji musisz znaleźć najdłuższy podciąg elementów w tej samej kolejności, występujący w obu ciągach znaków lub wzorcach.

Przykład

Na przykład podano dwa ciągi znaków. Załóżmy, że:

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

• Z wzorca pattern_1 można tworzyć sekwencje takie jak „RGB”, „RGGA”, „RGAR”. Aby utworzyć sekwencję, należy zachować względną pozycję każdego znaku w ciągu.
• Z wzorca pattern_2 możemy generować sekwencje takie jak „BGR”, „BRAG”, „RARG”. Sekwencje mogą być generowane pod warunkiem, że zachowują względną pozycję oryginalnego ciągu znaków.

Termin pozycja względna oznacza porządek.

Na przykład „BRG” jest poprawną sekwencją, ponieważ w oryginalnym ciągu znaków pattern_2 najpierw pojawiło się „B”, potem „R”, a potem „G”. Jednak jeśli sekwencją jest „RBRG”, nie jest ona poprawna, ponieważ w oryginalnym ciągu znaków (pattern_2) najpierw pojawiło się „B”.

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.

Rozwiązanie naiwne ma większą złożoność czasową i nie jest rozwiązaniem optymalnym. Korzystając z metody programowania dynamicznego (DP), rozwiązujemy problem złożoności.

Metoda naiwna

Metoda naiwna to proste podejście do problemu, niezależnie od złożoności czasowej i innych czynników optymalizacyjnych. W większości przypadków polega ona na „brutalnej sile”, wielokrotnych pętlach i wywołaniach rekurencyjnych. Termin „brutalna siła” oznacza przechodzenie 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, czteroliterowy ciąg „ABCD”. Na przykład, musimy utworzyć sekwencję z „ABCD”. Możemy wybrać znak lub nie. Oznacza to, że dla każdego znaku mamy dwie możliwości:

• 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 ​​istnieje 14 sekwencji. Jeśli nie weźmiemy żadnych liter, czyli po prostu pustego ciągu, liczba sekwencji wyniesie 15. Co więcej, sam ciąg „ABCD” jest sekwencją. Zatem liczba sekwencji wynosi 16.

Zatem możliwe jest wygenerowanie 2^4 lub 16 podciągów z „ABCD”. Następnie ciąg o długości m będzie miał całkowity podciąg wynoszący 2^m.

Dla każdego podciągu musimy sprawdzić cały wzorzec2. Zajmie to O(n) czasu. O(n) oznacza funkcję złożoności obliczającą czas potrzebny na wykonanie.

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

Oto kroki metody naiwnej:

Krok 1) Weź sekwencję ze wzorca 1.
Krok 2) Dopasuj sekwencję z kroku 1 do wzorca 2.
Krok 3) Jeśli pasuje, zapisz podciąg.
Krok 4) Jeśli we wzorcu 1 pozostały jeszcze jakieś sekwencje, przejdź ponownie do kroku 1.
Krok 5) Wydrukuj najdłuższy podciąg.

Optymalna podkonstrukcja

Termin „optymalna podstruktura” oznacza, że ​​optymalne rozwiązanie można znaleźć, rozwiązując podproblemy. Na przykład, w powyższym przykładzie mamy wzorzec 1 i wzorzec 2.

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.

Struktura rekurencyjna problemu LCS

Znajdujemy LCS podciągu (ciągu wygenerowanego z ciągu oryginalnego). Następnie zapisujemy długość LCS podciągów.

Oto kolejna interesująca właściwość zakładkaping podproblemyMówi się, że problem ma nakładanie sięping podproblemy, jeżeli opis problemu można rozbić na małe podproblemy i użyć go kilkakrotnie w programie.

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

Na przykład spójrz na drzewo rekurencji. W ciemnym polu możesz zauważyć nakładanie sięping podproblemy. („RG”, „RA”), („RG”, „R”) i inne są wywoływane kilkakrotnie.

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

Metoda rekurencyjna najdłuższego wspólnego podciągu

Powyższy wykres przedstawia metodę rekurencyjną. Każda funkcja rekurencyjna ma przypadek bazowy, w którym należy przerwać rekurencję lub rozpocząć zwracanie ze stosu.

Do tej implementacji użyjemy przypadku bazowego. Zatem algorytm wygląda następująco:

• Jeżeli wszystkie elementy przed ostatnim elementem pasują, zwiększ długość o jeden i wróć.
• Przekaż dwa wzorce do funkcji i pobierz maksymalną wartość zwracaną.
• 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.

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

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

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

Wyjście:

Length of LCS is:  5

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

Programowanie dynamiczne oznacza optymalizację prostej metody rekurencyjnej. Na przykład, patrząc na graf rekurencyjny lub naiwny, widzimy kilka identycznych wywołań funkcji. Metoda programowania dynamicznego rejestruje wszystkie obliczenia w tablicy i wykorzystuje je ponownie w razie potrzeby.

Użyjemy tablicy 2D o wymiarach mxn, gdzie m i n to długości wzorca 1 i wzorca 2. Dla Tablica 2D, możemy używać struktur danych List w Python lub struktury danych wektorowych/tablicowych w C++.

Rzekomy Code dla LCS wykorzystującego 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 tablicy 2D w podejściu programowania dynamicznego.

Omówmy logikę, którą tu zastosowaliśmy. Oto kroki:

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 bierzemy pusty podciąg, długość podciągu wynosi 0.

Krok 2) Jeżeli dwa znaki są takie same, przypiszemy wartość do indeksu (i,j) poprzez zwiększenie wcześniej obliczonego LCS, który jest obecny w indeksie (i-1,j-1) (z poprzedniego wiersza).

Krok 3) Jeśli nie pasuje, bierzemy maksymalny LCS 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 wszystkie wartości w tablicy 2D zawierają 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 < 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;
}

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, w metodzie DP po prostu obliczamy każde zadanie raz. W metodzie rekurencyjnej moglibyśmy mieć nakładanieping 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 wzorzec1[i] jest równy wzorcowi2[j], wtedy zaktualizuj DP[i][j] = DP[i-1][j-1] + 1.
• Jeżeli wzorzec1[i] nie jest równy wzorcowi2[j], wówczas DP[i][j] będzie wartością maksymalną pomiędzy DP[i-1][j] i DP[i][j-1].
• Kontynuuj, aż i i j dotrą do m i n.
• Ostatni element DP[m-1][n-1] będzie zawierał długość.

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

FAQ