Pisin yhteinen jakso: Python, C++ esimerkki

Mikä on pisin yhteinen jakso?

Longest Common Subsequence (LCS) tarkoittaa, että sinulle annetaan kaksi merkkijonoa/mallia/jonoa objekteja. Näistä kahdesta sekvenssistä/merkkijonosta sinun on löydettävä pisin elementtien osasarja samassa järjestyksessä, joka on molemmissa merkkijonoissa tai kuvioissa.

esimerkki

Tarjolla on esimerkiksi kaksi merkkijonoa.

Oletetaan, että

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Mallista_1 voidaan tuottaa sekvenssejä, kuten "RGB", "RGGA", "RGAR". Sarjan luomiseksi sinun on säilytettävä kunkin merkin suhteellinen sijainti merkkijonossa.
• Mallista 2 voimme tuottaa sekvenssejä, kuten "BGR", "BRAG", "RARG". Sekvenssejä voidaan tuottaa niin kauan, kun ne säilyttävät alkuperäisen merkkijonon suhteellisen sijainnin.

Termi suhteellinen sijainti tarkoittaa järjestystä.

Esimerkiksi "BRG" on kelvollinen sarja, koska "B" ilmestyi ensin, sitten "R" ja sitten "G" alkuperäisessä merkkijonomallissa_2. Jos sekvenssi on kuitenkin "RBRG", se ei ole kelvollinen. Koska alkuperäisessä merkkijonossa (pattern_2) "B" on ensin.

Meillä on kaksi vaihtoehtoa löytää pisin yhteinen alasekvenssi annetuista kahdesta sekvenssistä tai taulukosta.

• Naiivi menetelmä
• Dynaaminen ohjelmointiratkaisu: Pisin yhteinen osajakso tunnetaan myös nimellä LCS.

Naiivilla ratkaisulla on suurempi aikamonimutkaisuus, eikä se ole optimaalinen ratkaisu. Dynamic Programming Solution (DP) -ratkaisun avulla voimme ratkaista monimutkaisuusongelman.

Naiivi menetelmä

Naiivi menetelmä on yksinkertainen lähestymistapa ongelmaan riippumatta ajan monimutkaisuudesta ja muista optimointitekijöistä.

Naiivi-menetelmä koostuu "raakavoimasta", useista silmukoista, rekursiivisista menetelmistä useimmissa tapauksissa.

Termi raaka voima tarkoittaa kaikkien mahdollisten mallien läpikäymistä tietylle ongelmalle.

esimerkki

Yllä olevasta esimerkistä kuvio1 ja kuvio2 oletetaan, että kuvion 1 pituus on m ja kuvion2 pituus on n. Tarkistaaksemme jokaisen mahdollisen tapauksen meidän on arvioitava kuvion 1 kaikki mahdolliset osasekvenssit kuvion 2 kanssa.

Tässä on yksinkertainen 4-kirjaiminen merkkijono "ABCD". Meidän on esimerkiksi luotava sekvenssi "ABCD:stä". Joko voimme ottaa hahmon tai emme. Tämä tarkoittaa, että meillä on jokaiselle hahmolle kaksi vaihtoehtoa.

Ne ovat:

• Hahmo lisätään osasarjaan.
• Merkkiä ei lisätä alajaksoon.

Tässä kuvat näyttävät kaikki sekvenssit, jotka voimme tehdä merkkijonosta "ABCD".

Sarja 1 merkillä:

2 merkin jaksot:

3 merkin jaksot:

Yllä olevasta kaaviosta on 14 sekvenssiä. Jos emme ota kirjaimia, periaatteessa tyhjää merkkijonoa, sekvenssien kokonaismäärä on 15. Lisäksi merkkijono ”ABCD” itsessään on sekvenssi. Joten sarjoja on yhteensä 16.

Joten on mahdollista luoda 2⁴ tai 16 alajaksoa "ABCD:stä". Sitten merkkijono, jonka pituus on m on yhteensä 2 alajaksoa^m.

Jokaisen alasekvenssin kohdalla meidän on tarkistettava se koko kuvion2 osalta. Se kestää 0 (n) aikaa. 0(n) tarkoittaa monimutkaisuusfunktiota, joka laskee suoritusajan.

Joten kokonaisaika monimutkaisuus muuttuu O(n*2^m). Esimerkkiä varten olemme nähneet edellä arvon m=8 ja n=5.

Tässä ovat naiivin menetelmän vaiheet:

Vaihe 1) Ota sarja kuviosta1.
Vaihe 2) Yhdistä vaiheen 1 sekvenssi kuvion 2 kanssa.
Vaihe 3) Jos se vastaa, tallenna alajakso.
Vaihe 4) Jos kuviossa1 on jäljellä enemmän jaksoa, siirry uudelleen vaiheeseen 1.
Vaihe 5) Tulosta pisin osajakso.

Optimaalinen alarakenne

Termi optimaalinen alirakenne tarkoittaa, että optimaalinen ratkaisu (yksinkertainen) voidaan löytää ratkaisemalla osaongelmat. Esimerkiksi yllä olevassa esimerkissä meillä on malli1 ja kuvio2.

Vaihe 1) Ota kustakin kuviosta kaksi ensimmäistä merkkiä

Vaihe 2) Ota jokaisesta kuviosta kolmas tai viides merkki.

Vaihe 3) Jatka samalla tavalla muiden merkkien kanssa.

LCS löytyy alimerkkijonosta (alkuperäisestä merkkijonosta luotu merkkijono). Sitten pidämme kirjaa alimerkkijonojen LCS:n pituudesta.

Tässä on toinen mielenkiintoinen ominaisuus päällekkäisiä osa-ongelmia. Ongelmalla sanotaan olevan päällekkäisiä aliongelmia, jos ongelmalause voidaan jakaa pieniin osaongelmiin ja käyttää useita kertoja ohjelmassa.

Alla oleva kaavio osoittaa, että rekursiivinen algoritmi kutsui funktiota samalla parametrilla useita kertoja.

Katsotaanpa esimerkiksi rekursiopuuta.

Tummassa laatikossa voit huomata päällekkäisiä aliongelmia. ("RG", "RA"), ("RG", "R") ja muita kutsutaan useita kertoja.

Tämän optimoimiseksi meillä on lähestymistapa Dynaaminen ohjelmointi (DP).

Rekursiivinen menetelmä pisimmän viestintäsekvenssin

Yllä oleva kaavio on rekursiivinen menetelmä. Jokaisella rekursiivisella funktiolla on perustapaus, joka katkaisee rekursion tai alkaa palata pinosta.

Käytämme tässä toteutuksessa perustapausta. Joten algoritmi on seuraavanlainen:

• Jos kaikki elementit ennen viimeistä elementtiä täsmäävät, lisää pituutta yhdellä ja palaa
• Välitä kaksi kuviota funktiolle ja ota palautuksen maksimiarvo
• Jos yhden kuvion pituus on nolla, meillä ei ole vertailtavaa alajaksoa. Palauta 0 tässä tapauksessa. Tämä on rekursion perustapaus.

Pseudokoodi:

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)

Toteutus sisää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;
}

lähtö:

Length of LCS is: 5

Toteutus pythonissa

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

lähtö:

Lenght of LCS is:  5

Pitkän yhteisen osasekvenssin dynaaminen ohjelmointimenetelmä (LCS)

Dynaaminen ohjelmointi tarkoittaa tavallisen rekursiivisen menetelmän optimointia. Jos esimerkiksi näemme rekursiivisen tai naiivin lähestymistavan graafin, voimme nähdä, että on useita samoja funktiokutsuja. Dynaaminen ohjelmointimenetelmä tallentaa kaikki laskelmat taulukkoon ja käyttää sitä tarvittaessa.

Käytämme 2D-taulukkoa, jonka mitat ovat mxn, missä m ja n ovat kuvion1 ja kuvion2 pituuksia.

varten 2D-taulukko, voimme käyttää List-tietorakenteita pythonissa tai vektori-/taulukkotietorakenteita C++.

Pseudokoodi DP:tä käyttävälle LCS:lle:

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]

Tässä on taulukko LCS, jota käytetään 2D-taulukon tietorakenteena dynaamisen ohjelmoinnin lähestymistapaa varten.

Keskustellaan tässä käyttämästämme logiikasta. Vaiheet ovat:

Vaihe 1) Jos i tai j on nolla, otamme tyhjän merkkijonon annetuista kahdesta merkkijonosta ja yritämme löytää yhteiset osasekvenssit. Koska ottava osamerkkijono on kuitenkin tyhjä, osajonon pituus on 0.

Vaihe 2) Jos kaksi merkkiä täsmäävät, annamme arvon (i,j)-indeksille lisäämällä aiemmin laskettua LCS-arvoa, joka on (i-1,j-1) -indeksissä (edelliseltä riviltä).

Vaihe 3) Jos se ei täsmää, otamme kahden vierekkäisen indeksin maksimi-LCS:n. Ja tällä tavalla meidän on täytettävä kaikki 2D-taulukon arvot.

Vaihe 4) Lopuksi palautamme 2D-taulukon viimeisen solun arvon.

Periaatteessa kaikki 2D-taulukon arvot sisältävät yhteisten osasekvenssien pituuden. Näistä viimeinen solu sisältää pisimmän yhteisen osasekvenssin pituuden.

Toteutus sisää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;
}

lähtö:

Length of LCS: 5

Toteutus sisää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))

lähtö:

Length of LCS: 5

Joten molemmilla merkkijonoilla on pisin yhteinen osajono, jonka pituus on 5.

Lyhyesti sanottuna laskemme jokaisen tehtävän kerran DP-menetelmässä DP-menetelmässä. Rekursiivisessa menetelmässä meillä voi olla päällekkäisiä aliongelmia.

Tässä dynaamisessa ohjelmointialgoritmissa käytämme 2D-matriisia. Siinä annetaan kaksi merkkijonoa (oletetaan, että molemmilla on pituus n). Tällöin taulukossa tarvittava tila on nx n. Jos merkkijonot ovat riittävän suuria, tarvitsemme DP-ratkaisusta muistioptimoidun version.

Koodiin otettu yksinkertaistettu logiikka on:

• Ilmoita 2D-taulukko DP[m][n].
• Täytä DP-taulukon ensimmäinen rivi ja ensimmäinen sarake 0:lla.
• Ota i ja j iteraatioon.
• Jos kuvio1[i] on yhtä kuin kuvio2[j], päivitä DP[i][j] = DP[i-1][j-1] + 1
• Jos kuvio1[i] ei ole yhtä suuri kuin kuvio2[j], niin DP[i][j] on maksimiarvo DP[i-1][j]:n ja DP[i][j-1]:n välillä.
• Jatka kunnes i ja j saavuttavat kohdat m ja n.
• Viimeinen elementti tai DP[m-1][n-1] sisältää pituuden.

Tässä sitä osoitetaan nimellä DP[m-1][n-1], koska taulukon indeksi alkaa nollasta.

Yhteenveto

• DP-menetelmällä on pienempi aikamonimutkaisuus; se on O(mn), missä m ja n ovat syötetyn merkkijonon tai taulukon pituus.
• DP on nopeampi lähestymistapa kuin rekursiivinen, ja sen aika monimutkaisuus on O(n*2^m).
• Dynaaminen ohjelmointi (DP) ei ole muistioptimoitu. Käytimme 2D-taulukkoa, jonka pituus on m*n. Joten avaruuden kompleksisuus on (m*n).
• Rekursiivinen menetelmä, pahimmassa tapauksessa suurin muisti, jonka se vie, on m+n, periaatteessa syötetyn merkkijonon kokonaispituus.
• Nykyaikainen tietokone riittää käsittelemään tämän määrän muistia.