Pisin yleinen seuraus

Tässä opetusohjelmassa opit, kuinka pisin yhteinen jälkijono löytyy. Löydät myös toimivia esimerkkejä pisimmistä tavallisista alijärjestelmistä C, C ++, Java ja Python.

Pisin yhteinen jakso (LCS) määritellään pisimmäksi jaksoksi, joka on yhteinen kaikille annetuille sekvensseille, edellyttäen, että alaryhmän elementtien ei tarvitse olla peräkkäisissä asemissa alkuperäisissä sekvensseissä.

Jos S1 ja S2 ovat kaksi annettua sekvenssiä, Z on S1: n ja S2: n yhteinen alijärjestys, jos Z on sekä S1: n että S2: n alijono. Lisäksi Z: n on oltava tiukasti kasvava sekvenssi sekä S1: n että S2: n indekseistä.

Tiukasti kasvavassa järjestyksessä alkuperäisistä sekvensseistä valittujen elementtien indeksien on oltava nousevassa järjestyksessä Z: ssä.

Jos

 S1 = (B, C, D, A, A, C, D)

Silloin se (A, D, B)ei voi olla S1: n jatko, koska elementtien järjestys ei ole sama (ts. Ei tarkasti kasvava sekvenssi).

Ymmärretään LCS esimerkillä.

Jos

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Sitten yhteiset alijonot ovat (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Näiden (C, D, A, C)osien joukossa on pisin yhteinen seuraus. Aiomme löytää tämän pisimmän yleisen jatkoosan dynaamisen ohjelmoinnin avulla.

Ennen kuin jatkat, jos et vielä tiedä dynaamista ohjelmointia, käy läpi dynaaminen ohjelmointi.

Dynaamisen ohjelmoinnin käyttäminen LCS: n löytämiseen

Otetaan kaksi jaksoa:

Ensimmäinen sekvenssi

Toinen Sequence

Seuraavia vaiheita noudatetaan pisin yhteisen seurannan löytämiseksi.

Luo ulottuvuustaulukko, n+1*m+1jossa n ja m ovat vastaavasti X: n ja Y: n pituudet. Ensimmäinen rivi ja ensimmäinen sarake on täytetty nollilla. Alusta taulukko
Täytä taulukon kukin solu seuraavan logiikan avulla.
Jos nykyiselle riville ja sarakkeelle vastaava merkki vastaa toisiaan, täytä nykyinen solu lisäämällä yksi diagonaalielementtiin. Osoita nuolta diagonaaliseen soluun.
Ota muu kuin edellisen sarakkeen ja edellisen rivielementin enimmäisarvo nykyisen solun täyttämiseksi. Osoita nuolta soluun, jonka arvo on suurin. Jos he ovat tasa-arvoisia, osoita mihinkään heistä. Täytä arvot
Vaihe 2 toistetaan, kunnes taulukko on täynnä. Täytä kaikki arvot
Viimeisen rivin ja viimeisen sarakkeen arvo on pisimmän yhteisen alijonon pituus. Oikea alakulma on LCS: n pituus
Löydätksesi pisimmän yhteisen loppusekvenssin, aloita viimeisestä elementistä ja seuraa nuolen suuntaa. Symbolia () vastaavat elementit muodostavat pisimmän yhteisen alijännitteen. Luo polku nuolien mukaan

Siten pisin yleinen osa on CD.

LCS

Kuinka dynaaminen ohjelmointialgoritmi on tehokkaampi kuin rekursiivinen algoritmi ratkaistaessa LCS-ongelmaa?

Dynaamisen ohjelmoinnin menetelmä vähentää toimintokutsujen määrää. Se tallentaa jokaisen toimintopuhelun tuloksen, jotta sitä voidaan käyttää tulevissa puheluissa ilman turhaa puhelua.

Edellä olevassa dynaamisessa algoritmissa X: n ja Y: n elementtien välisestä vertailusta saadut tulokset tallennetaan taulukkoon, jotta niitä voidaan käyttää tulevissa laskelmissa.

Joten dynaamisen lähestymistavan tarvitsema aika on taulukon täyttämiseen kuluva aika (ts. O (mn)). Rekursioalgoritmin monimutkaisuus on 2 ^{max (m, n)} .

Pisin yleisen seurannan algoritmi

 X ja Y ovat kaksi annettua jaksoa Alusta taulukon LCS, jonka mitat ovat X.pituus * Y.pituus X.etiketti = X Y.etiketti = Y LCS (0) () = 0 LCS () (0) = 0 Aloita LCS: stä ( 1) (1) Vertaa X (i) ja Y (j) Jos X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Osoita nuolta LCS: ään (i) (j) Muu LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Osoita nuoli maksimiin (LCS (i-1) ( j), LCS (i) (j-1))

Python-, Java- ja C / C ++ -esimerkkejä

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )