Najduži zajednički niz: Python, C++ Primjer

Što je najduži zajednički podslijed?

Najduži zajednički podniz (LCS) znači da ćete dobiti dva niza/uzorka/niza objekata. Između ova dva niza/niza, trebate pronaći najduži podniz elemenata u istom redoslijedu prisutnih u oba niza ili uzorka.

Primjer

Na primjer, postoje dva niza.

Pretpostavimo da,

Uzorak_1 = “RGBGARGA”
Uzorak_2 = “BGRARG”

• Iz uzorka_1 mogu se proizvesti nizovi kao što su "RGB", "RGGA", "RGAR". Za kreiranje niza morate održavati relativni položaj svakog znaka u nizu.
• Iz uzorka_2 možemo proizvesti sekvence poput "BGR", "BRAG", "RARG". Nizovi se mogu proizvesti sve dok zadržavaju relativni položaj izvornog niza.

Izraz relativni položaj označava red.

Na primjer, "BRG" je važeći niz jer se prvo pojavilo "B", zatim "R", a zatim "G" u izvornom uzorku niza_2. Međutim, ako je niz "RBRG", nije valjan. Jer u izvornom nizu (uzorak_2), "B" dolazi na prvo mjesto.

Imamo dvije opcije za pronalaženje najdulje zajedničke podsekvence iz zadane dvije sekvence ili polja.

• Naivna metoda
• Rješenje za dinamičko programiranje: Najduži zajednički podslijed poznat je i kao LCS.

Naivno rješenje ima veću vremensku složenost i nije optimalno rješenje. Koristeći Dynamic Programming Solution (DP), prevladavamo problem složenosti.

Naivna metoda

Naivna metoda je jednostavan pristup problemu bez obzira na vremensku složenost i druge faktore optimizacije.

Naivna metoda sastoji se od "Brute Force", višestrukih petlji, rekurzivnih metoda u većini slučajeva.

Izraz gruba sila znači prolazak kroz sve moguće obrasce za dati problem.

Primjer

Iz gornjeg primjera uzorka1 i uzorka2, pretpostavimo da uzorak1 ima duljinu m, a uzorak2 ima duljinu n. Kako bismo provjerili svaki mogući slučaj, trebamo procijeniti svaki mogući podslijed uzorka1 s uzorkom2.

Evo jednostavnog niza od 4 slova “ABCD”. Na primjer, moramo stvoriti niz od "ABCD." Ili možemo uzeti lik ili ne. To znači da za svaki lik imamo dva izbora.

Oni su:

• Znak će biti dodan podnizu.
• Znak neće biti dodan podnizu.

Ovdje slike prikazuju sve nizove koje možemo napraviti od niza “ABCD”.

Niz s 1 znakom:

Nizovi s 2 znaka:

Nizovi s 3 znaka:

Iz gornjeg dijagrama, postoji 14 nizova. Ako ne uzmemo slova, zapravo prazan niz, ukupni nizovi bit će 15. Štoviše, sam niz "ABCD" je niz. Dakle, ukupni nizovi su 16.

Dakle, moguće je generirati 2⁴ ili 16 podnizova iz “ABCD”. Zatim, niz duljine od m morat će imati ukupni podniz od 2^m.

Za svaki podslijed moramo ga provjeriti za cijeli uzorak2. Trebat će 0(n) vremena. 0(n) znači funkciju složenosti koja izračunava vrijeme potrebno za izvršenje.

Dakle, ukupna vremenska složenost postaje O(n*2^m). Za primjer, gore smo vidjeli vrijednost m=8 i n=5.

Evo koraka naivne metode:

Korak 1) Uzmite niz iz uzorka1.
Korak 2) Spojite niz iz koraka 1 s uzorkom 2.
Korak 3) Ako odgovara, spremite podniz.
Korak 4) Ako je ostalo još slijeda u uzorku1, ponovno idite na korak 1.
Korak 5) Ispiši najdulji podniz.

Optimalna podkonstrukcija

Izraz optimalna podstruktura znači da se optimalno rješenje (jednostavno) može pronaći rješavanjem podproblema. Na primjer, u gornjem primjeru imamo pattern1 i pattern2.

Korak 1) Uzmite prva dva znaka iz svakog uzorka

Korak 2) Uzmite treći do peti znak iz svakog uzorka.

Korak 3) Nastavite na sličan način s preostalim znakovima.

Nalazimo LCS na podnizu (niz generiran iz originalnog niza). Zatim vodimo zapis o duljini LCS podnizova.

Evo još jedne zanimljive nekretnine preklapajući podproblemi. Kaže se da problem ima podprobleme koji se preklapaju ako se iskaz problema može razdvojiti na male podprobleme i koristiti nekoliko puta u programu.

Donji dijagram pokazuje da je rekurzivni algoritam nekoliko puta pozvao funkciju s istim parametrom.

Na primjer, pogledajmo stablo rekurzije.

U okviru tamne boje možete primijetiti podprobleme koji se preklapaju. (“RG”, “RA”), (“RG”, “R”) i drugi pozivaju se nekoliko puta.

Za optimizaciju ovoga, imamo pristup Dinamičko programiranje (DP).

Rekurzivna metoda najdulje komunikacijske sekvence

Grafikon prikazan gore je rekurzivna metoda. Svaka rekurzivna funkcija ima osnovni slučaj za prekidanje rekurzije ili početak vraćanja sa svog stoga.

Za ovu implementaciju koristit ćemo osnovni slučaj. Dakle, algoritam je ovako:

• Ako svi elementi prije posljednjeg elementa imaju podudaranje, tada povećajte duljinu za jedan i vratite se
• Proslijedite dva uzorka u funkciju i uzmite najveću vrijednost povrata
• Ako jedan uzorak ima nultu duljinu, tada nemamo podniza za usporedbu. Vrati 0 u ovom slučaju. Ovo je osnovni slučaj rekurzije.

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)

Implementacija u 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;
}

Izlaz:

Length of LCS is: 5

Implementacija u pythonu

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

Izlaz:

Lenght of LCS is:  5

Metoda dinamičkog programiranja najdulje zajedničke podsekvence (LCS)

Dinamičko programiranje znači optimiziranje obične rekurzivne metode. Na primjer, ako vidimo graf rekurzivnog ili jednostavnog pristupa, možemo vidjeti da postoji nekoliko istih poziva funkcija. Metoda dinamičkog programiranja bilježi sve izračune u nizu i koristi ga po potrebi.

Koristit ćemo 2D niz dimenzija mxn, gdje su m i n duljine uzoraka1 i uzorka2.

Za 2D niz, možemo koristiti strukture podataka List u pythonu ili strukture podataka vektora/niza u C++.

Pseudo kod za LCS koji koristi 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]

Ovdje je tablica LCS koja se koristi kao struktura podataka 2D polja za pristup dinamičkom programiranju.

Raspravimo o logici koju smo ovdje koristili. Koraci su:

Korak 1) Ako je i ili j nula, uzimamo prazan niz iz zadana dva niza i pokušavamo pronaći zajedničke podnizove. Međutim, kako je podniz koji uzimamo prazan, duljina podniza je 0.

Korak 2) Ako se dva znaka podudaraju, dodijelit ćemo vrijednost (i,j) indeksu povećanjem prethodno izračunatog LCS-a, koji je prisutan u (i-1,j-1) indeksu (iz prethodnog reda).

Korak 3) Ako se ne podudara, tada ćemo uzeti max LCS susjedna dva indeksa. I na ovaj način, moramo ispuniti sve vrijednosti u 2D nizu.

Korak 4) Na kraju, vratit ćemo vrijednost zadnje ćelije 2D polja.

U osnovi, sve vrijednosti u 2D nizu sadrže duljinu uobičajenih podnizova. Među njima, posljednja ćelija sadrži duljinu najdužeg zajedničkog podniza.

Implementacija u 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;
}

Izlaz:

Length of LCS: 5

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

Izlaz:

Length of LCS: 5

Dakle, oba niza imaju najdulji zajednički podniz duljine 5.

Ukratko, mi jednostavno izračunavamo svaki zadatak jednom u DP metodi u DP metodi. U rekurzivnoj metodi mogli bismo imati podprobleme koji se preklapaju.

U ovom algoritmu dinamičkog programiranja koristimo 2D matricu. Bit će dana dva niza (pretpostavimo da oba imaju duljinu n). Tada je potreban prostor u nizu nx n. Ako su nizovi dovoljno veliki, trebat će nam verzija DP rješenja optimizirana za memoriju.

Pojednostavljena logika koja je uzeta u kod je:

• Deklarirajte 2D niz DP[m][n].
• Ispunite prvi redak i prvi stupac DP polja s 0.
• Uzmite i i j za ponavljanje.
• Ako je uzorak1[i] jednak uzorku2[j], ažurirajte DP[i][j] = DP[i-1][j-1] + 1
• Ako uzorak1[i] nije jednak uzorku2[j], tada će DP[i][j] biti najveća vrijednost između DP[i-1][j] i DP[i][j-1].
• Nastavite dok i i j ne dođu do m i n.
• Posljednji element ili DP[m-1][n-1], sadržavat će duljinu.

Ovdje se adresira kao DP[m-1][n-1], jer indeks niza počinje od 0.

rezime

• DP metoda ima nižu vremensku složenost; to je O(mn), gdje su m i n duljina ulaznog niza ili niza.
• DP je brži pristup od rekurzivnog, s vremenskom složenošću od O(n*2^m).
• Dinamičko programiranje (DP) nije optimizirano za memoriju. Koristili smo 2D niz koji ima duljinu m*n. Dakle, složenost prostora je (m*n).
• Rekurzivna metoda, u najgorem slučaju, najveća memorija koju će zauzeti bit će m+n, u osnovi ukupna duljina unesenog niza.
• Današnje moderno računalo dovoljno je za rukovanje ovom količinom memorije.