Cea mai lungă secvență comună: Python, C++ Exemplu

Care este cea mai lungă subsecvență comună?

Cea mai lungă subsecvență comună (LCS) înseamnă că vi se vor da două șiruri/modele/secvențe de obiecte. Dintre aceste două secvențe/șiruri, trebuie să găsiți cea mai lungă subsecvență de elemente în aceeași ordine prezentă în ambele șiruri sau modele.

Exemplu

De exemplu, sunt furnizate două șiruri.

Să presupunem că,

Model_1 = „RGBGARGA”
Model_2 = „BGRARG”

• Din pattern_1, secvențele pot fi produse precum „RGB”, „RGGA”, „RGAR”. Pentru a crea o secvență, trebuie să mențineți poziția relativă a fiecărui caracter din șir.
• Din pattern_2, putem produce secvențe precum „BGR”, „BRAG”, „RARG”. Secvențele pot fi produse atâta timp cât mențin poziția relativă a șirului original.

Termenul poziție relativă înseamnă ordine.

De exemplu, „BRG” este o secvență validă, deoarece „B” a apărut mai întâi, apoi „R” și apoi „G” în modelul de șir original_2. Totuși, dacă o secvență este „RBRG”, nu este validă. Pentru că în șirul original (modelul_2), „B” este primul.

Avem două opțiuni pentru a găsi cea mai lungă subsecvență comună din cele două secvențe sau matrice date.

• Metoda naiva
• Soluție de programare dinamică: cea mai lungă subsecvență comună este cunoscută și sub numele de LCS.

O soluție naivă are o complexitate de timp mai mare și nu este soluția optimă. Folosind Dynamic Programming Solution (DP), depășim problema complexității.

Metoda naivă

Metoda naivă este o abordare simplă a problemei, indiferent de complexitatea timpului și de alți factori de optimizare.

Metoda Naive constă în „Brute Force”, mai multe bucle, metode recursive în majoritatea cazurilor.

Termenul de forță brută înseamnă parcurgerea tuturor tiparelor posibile pentru o anumită problemă.

Exemplu

Din exemplul de mai sus de model1 și model2, să presupunem că modelul1 are o lungime de m și modelul2 are o lungime de n. Pentru a verifica fiecare caz posibil, trebuie să evaluăm fiecare subsecvență posibilă a pattern1 cu pattern2.

Iată un șir simplu de 4 litere „ABCD”. De exemplu, trebuie să creăm o secvență din „ABCD”. Fie putem lua un personaj, fie nu. Asta înseamnă că, pentru fiecare personaj, avem două opțiuni.

Acestea sunt:

• Personajul va fi adăugat la următoarea.
• Personajul nu va fi adăugat la următoarea.

Aici, imaginile arată toate secvențele pe care le putem face din șirul „ABCD”.

Secvență cu 1 caracter:

Secvențe cu 2 caractere:

Secvențe cu 3 caractere:

Din diagrama de mai sus, există 14 secvențe. Dacă nu luăm litere, practic un șir gol, secvențele totale vor fi 15. Mai mult, șirul „ABCD” în sine este o secvență. Deci, secvențele totale sunt 16.

Deci, este posibil să generați 2⁴ sau 16 subsecvențe din „ABCD”. Apoi, un șir cu o lungime de m va trebui să totalizeze ulterior de 2^m.

Pentru fiecare subsecvență, trebuie să o verificăm pentru întregul model2. Va dura 0(n) timp. 0(n) înseamnă funcția de complexitate care calculează timpul necesar pentru execuție.

Deci, complexitatea totală a timpului devine O(n*2^m). Pentru exemplu, am văzut mai sus valoarea lui m=8 și n=5.

Iată pașii Metodei Naive:

Pas 1) Luați o secvență din modelul 1.
Pas 2) Potriviți secvența de la pasul 1 cu modelul 2.
Pas 3) Dacă se potrivește, atunci salvați următoarea.
Pas 4) Dacă în modelul 1 rămâne mai multă secvență, mergeți din nou la pasul 1.
Pas 5) Tipăriți cea mai lungă secvență.

Substructură optimă

Termenul de substructură optimă înseamnă că o soluție optimă (simplu) poate fi găsită prin rezolvarea subproblemelor. De exemplu, în exemplul de mai sus, avem model1 și model2.

Pas 1) Luați primele două caractere din fiecare model

Pas 2) Luați al treilea până la al cincilea caracter din fiecare model.

Pas 3) Continuați în mod similar cu caracterele rămase.

Găsim LCS-ul pe sub-șir (șir generat dintr-un șir original). Apoi păstrăm evidența lungimii LCS a subșirurilor.

Acum, iată o altă proprietate interesantă subprobleme suprapuse. Se spune că o problemă are subprobleme suprapuse dacă declarația problemei poate fi împărțită în subprobleme mici și utilizată de mai multe ori în program.

Diagrama de mai jos arată că algoritmul recursiv a numit funcția cu același parametru de mai multe ori.

De exemplu, să vedem arborele recursiv.

În caseta de culoare închisă, puteți observa sub-probleme care se suprapun. (“RG”, “RA”), (“RG”,”R”) și altele sunt numite de mai multe ori.

Pentru optimizarea acestui lucru, avem abordarea de Programare dinamică (DP).

Metoda recursiva a celei mai lungi secvente de comunicatii

Graficul prezentat mai sus este metoda recursivă. Fiecare funcție recursivă are un caz de bază pentru a sparge recursiunea sau pentru a începe să revină din stiva sa.

Pentru această implementare, vom folosi un caz de bază. Asa ca Algoritmul este ca urmatorul:

• Dacă toate elementele dinaintea ultimului element au o potrivire, atunci măriți lungimea cu unul și reveniți
• Treceți două modele funcției și luați valoarea maximă a returnării
• Dacă un model are lungime zero, atunci nu avem nicio subsecvență de comparat. Returnați 0 în acest caz. Acesta este cazul de bază al recursiunii.

Pseudo cod:

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)

Implementarea în 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;
}

ieșire:

Length of LCS is: 5

Implementare în 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)))

ieșire:

Lenght of LCS is:  5

Metoda de programare dinamică a celei mai lungi subsecvențe comune (LCS)

Programarea dinamică înseamnă optimizarea metodei recursive simple. De exemplu, dacă vedem graficul de abordare recursiv sau naiv, putem vedea că există mai multe apeluri de aceleași funcții. Metoda de programare dinamică înregistrează toate calculele într-o matrice și o folosește atunci când este necesar.

Vom folosi o matrice 2D cu dimensiuni de mxn, unde m și n sunt lungimile model1 și model2.

Pentru Matrice 2D, putem folosi structuri de date Listă în python sau structuri de date vector/array în C++.

Pseudocod pentru LCS folosind 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]

Iată tabelul LCS care este utilizat ca structură de date matrice 2D pentru abordarea de programare dinamică.

Să discutăm despre logica pe care am folosit-o aici. Pașii sunt:

Pas 1) Dacă i sau j este zero, luăm un șir gol din cele două șiruri date și încercăm să găsim subsecvențele comune. Cu toate acestea, deoarece subșirul pe care îl luăm este gol, lungimea subsecvenței este 0.

Pas 2) Dacă două caractere se potrivesc, vom atribui valoarea indexului (i,j) prin incrementul LCS calculat anterior, care este prezent în indexul (i-1,j-1) (de pe rândul anterior).

Pas 3) Dacă nu se potrivește, atunci vom lua LCS maxim al celor doi indici adiacenți. Și în acest fel, trebuie să umplem toate valorile din matricea 2D.

Pas 4) În cele din urmă, vom returna valoarea ultimei celule a matricei 2D.

Practic, toată valoarea din matricea 2D conține lungimea subsecvențelor comune. Dintre acestea, ultima celulă conține lungimea celei mai lungi subsecvențe comune.

Implementarea în 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;
}

ieșire:

Length of LCS: 5

Implementarea în 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))

ieșire:

Length of LCS: 5

Deci, ambele șiruri au cea mai lungă subsecvență comună de lungime 5.

Pe scurt, pur și simplu calculăm fiecare sarcină o dată în metoda DP în metoda DP. În metoda recursivă, am putea avea subprobleme suprapuse.

În acest algoritm de programare dinamică, folosim o matrice 2D. Vor fi date două șiruri (să presupunem că ambele au lungimea n). Atunci spațiul necesar în matrice este nx n. Dacă șirurile sunt suficient de mari, vom avea nevoie de o versiune optimizată pentru memorie a soluției DP.

Logica simplificată care a fost luată în cod este:

• Declarați o matrice 2D DP[m][n].
• Completați primul rând și prima coloană a matricei DP cu 0.
• Luați i și j pentru iterație.
• Dacă modelul1[i] este egal cu modelul2[j], atunci actualizați DP[i][j] = DP[i-1][j-1] + 1
• Dacă modelul1[i] nu este egal cu modelul2[j], atunci DP[i][j] va fi valoarea maximă între DP[i-1][j] și DP[i][j-1].
• Continuați până când i și j ajung la m și n.
• Ultimul element sau DP[m-1][n-1], va conține lungimea.

Aici, este adresat ca DP[m-1][n-1], deoarece indicele matricei începe de la 0.

Rezumat

• Metoda DP are o complexitate de timp mai mică; este O(mn), unde m și n sunt lungimea șirului sau matricei de intrare.
• DP este o abordare mai rapidă decât cea recursivă, cu complexitatea timpului de O(n*2^m).
• Programarea dinamică (DP) nu este optimizată pentru memorie. Am folosit o matrice 2D care are lungimea m*n. Deci, complexitatea spațiului este (m*n).
• Metoda recursiva, in cel mai rau scenariu, cea mai mare memorie pe care o va ocupa va fi m+n, practic lungimea totala a sirului introdus.
• Calculatorul modern de astăzi este suficient pentru a gestiona această cantitate de memorie.