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

Što je najduži zajednički podslijed?

Najduži zajednički podniz (LCS) znači da će vam biti zadana dva niza, uzorka ili niza objekata. Među ta dva niza ili niza morate pronaći najduži podniz elemenata u istom redoslijedu prisutan u oba niza ili uzorka.

Primjer

Na primjer, zadana su dva niza znakova. Pretpostavimo da:

Uzorak_1 = “RGBGARGA”
Uzorak_2 = “BGRARG”

• Iz pattern_1 mogu se proizvesti nizovi poput „RGB“, „RGGA“, „RGAR“. Za stvaranje niza potrebno je održavati relativni položaj svakog znaka u nizu.
• Iz pattern_2 možemo generirati nizove poput „BGR“, „BRAG“, „RARG“. Nizovi se mogu generirati sve dok održavaju relativni položaj izvornog niza.

Izraz relativni položaj označava red.

Na primjer, „BRG“ je valjan niz jer se u izvornom nizu pattern_2 prvo pojavio „B“, zatim „R“, a zatim „G“. Međutim, ako je niz „RBRG“, nije valjan jer se u izvornom nizu (pattern_2) prvo pojavljuje „B“.

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. Korištenjem rješenja dinamičkog programiranja (DP) prevladavamo problem složenosti.

Naivna metoda

Naivna metoda je jednostavan pristup problemu, bez obzira na vremensku složenost i druge faktore optimizacije. U većini slučajeva sastoji se od "grube sile", višestrukih petlji i rekurzivnih poziva. Pojam grube sile znači prolazak kroz sve moguće obrasce za zadani 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, trebamo stvoriti niz od „ABCD“. Možemo uzeti znak ili ne. To znači da za svaki znak imamo dva izbora:

• 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 vidljivo je 14 nizova. Ako ne uzmemo nijedno slovo, u osnovi prazan niz, ukupan broj nizova bit će 15. Štoviše, sam niz "ABCD" je niz. Dakle, ukupan broj nizova je 16.

Dakle, moguće je generirati 2^4 ili 16 podnizova iz „ABCD“. Zatim, niz duljine m imat će ukupni podniz od 2^m.

Za svaki podniz moramo ga provjeriti za cijeli uzorak2. Trebat će vremena O(n). O(n) označava funkciju složenosti koja izračunava vrijeme potrebno za izvršenje.

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

Evo koraka naivne metode:

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

Optimalna podkonstrukcija

Pojam optimalne podstrukture znači da se optimalno rješenje može pronaći rješavanjem podproblema. Na primjer, u gornjem primjeru imamo uzorak1 i uzorak2.

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.

Rekurzivna struktura LCS problema

Pronalazimo LCS na podnizu (niz generiran iz izvornog niza). Zatim čuvamo zapis o duljini LCS-a podnizova.

Evo još jedne zanimljive nekretnine preklapanjeping podproblemiKaže se da problem ima preklapanjeping podproblemi ako se izjava problema može razbiti 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, pogledajte stablo rekurzije. U tamnom okviru možete primijetiti preklapanjeping podproblemi. („RG“, „RA“), („RG“, „R“) i drugi se pozivaju nekoliko puta.

Kako bismo to optimizirali, imamo pristup Dinamičko programiranje (DP).

Rekurzivna metoda najduljeg zajedničkog podniza

Graf prikazan gore predstavlja rekurzivnu metodu. Svaka rekurzivna funkcija ima osnovni slučaj za prekid rekurzije ili početak vraćanja sa svog stoga.

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

• Ako se svi elementi prije zadnjeg elementa podudaraju, tada se duljina povećava za jedan i vraća se.
• Proslijedite dva uzorka funkciji i uzmite maksimalnu 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.

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

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

Izlaz:

Length of LCS is:  5

Metoda dinamičkog programiranja najduljeg zajedničkog podniza (LCS)

Dinamičko programiranje znači optimiziranje obične rekurzivne metode. Na primjer, ako pogledamo graf rekurzivnog ili naivnog pristupa, možemo vidjeti da postoji nekoliko identičnih poziva funkcija. Metoda dinamičkog programiranja bilježi sve izračune u niz i ponovno ih koristi kada je potrebno.

Koristit ćemo 2D niz dimenzija mxn, gdje su m i n duljine uzorka1 i uzorka2. Za 2D niz, možemo koristiti strukture podataka List u Python ili vektorske/matrične podatkovne strukture u C++.

Nadimak Code za LCS korištenjem DP-a:

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-a koja se koristi kao 2D struktura podataka polja za pristup dinamičkog programiranja.

Razmotrimo logiku koju smo ovdje koristili. Koraci su:

Korak 1) Ako je i ili j nula, uzimamo prazan niz iz zadanih dvaju nizova i pokušavamo pronaći zajedničke podnizove. Međutim, budući da je podniz koji uzimamo prazan, duljina podniza je 0.

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

Korak 3) Ako se ne podudara, uzet ćemo maksimalni LCS dva susjedna indeksa. Na taj način moramo popuniti sve vrijednosti u 2D polju.

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

U osnovi, sve vrijednosti u 2D nizu sadrže duljinu zajedničkih podnizova. Među njima, posljednja ćelija sadrži duljinu najduljeg 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 < 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;
}

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, u DP metodi jednostavno izračunavamo svaki zadatak jednom. U rekurzivnoj metodi možemo imati preklapanjeping podproblemi.

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 pattern1[i] jednak pattern2[j], tada se ažurira DP[i][j] = DP[i-1][j-1] + 1.
• Ako pattern1[i] nije jednak pattern2[j], tada će DP[i][j] biti maksimalna 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, DP[m-1][n-1], sadržavat će duljinu.

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

Pitanja i odgovori