Pisin yhteinen jakso: Python, C++ esimerkki

Mikä on pisin yhteinen jakso?

Pisin yhteinen osasekvenssi (LCS) tarkoittaa, että sinulle annetaan kaksi merkkijonoa, kuviota tai objektien sekvenssiä. Näistä kahdesta sekvenssistä tai merkkijonosta sinun on löydettävä pisin samassa järjestyksessä olevien elementtien osasekvenssi molemmissa merkkijonoissa tai kuvioissa.

esimerkki

Esimerkiksi annetaan kaksi merkkijonoa. Oletetaan, että:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Pattern_1:stä voidaan tuottaa sekvenssejä, kuten “RGB”, “RGGA” ja “RGAR”. Sekvenssin luomiseksi sinun on säilytettävä kunkin merkin suhteellinen sijainti merkkijonossa.
• Pattern_2:sta voimme tuottaa sekvenssejä, kuten “BGR”, “BRAG”, “RARG”. Sekvenssejä voidaan tuottaa, kunhan ne säilyttävät alkuperäisen merkkijonon suhteellisen sijainnin.

Termi suhteellinen sijainti tarkoittaa järjestystä.

Esimerkiksi ”BRG” on kelvollinen merkkijono, koska alkuperäisessä merkkijonossa pattern_2 oli ensin ”B”, sitten ”R” ja lopuksi ”G”. Jos merkkijono 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 aikakompleksisuus, eikä se ole optimaalinen ratkaisu. Dynaamisen ohjelmoinnin ratkaisun (DP) avulla ratkaisemme kompleksisuusongelman.

Naiivi menetelmä

Naiivimenetelmä on yksinkertainen lähestymistapa ongelmaan riippumatta aikakompleksisuudesta ja muista optimointitekijöistä. Se koostuu useimmissa tapauksissa "raa'asta voimasta", useista silmukoista ja rekursiivisista kutsuista. Termi raaka voima tarkoittaa kaikkien mahdollisten kuvioiden läpikäymistä tietyssä ongelmassa.

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 nelikirjaiminen merkkijono ”ABCD”. Esimerkiksi meidän on luotava merkkijono ”ABCD:stä”. Voimme joko ottaa merkin tai olla ottamatta. Tämä tarkoittaa, että jokaiselle merkille meillä on kaksi vaihtoehtoa:

• 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 näkyy 14 merkkijonoa. Jos emme ota yhtään kirjainta, eli pohjimmiltaan tyhjän merkkijonon, merkkijonojen kokonaismäärä on 15. Lisäksi merkkijono "ABCD" itsessään on merkkijono. Joten merkkijonojen kokonaismäärä on 16.

Joten on mahdollista luoda 2^4 tai 16 alisekvenssiä merkistä ”ABCD”. Sitten merkkijono, jonka pituus on m on yhteensä 2^m:n alisekvenssi.

Jokaista alisekvenssiä kohden meidän on tarkistettava koko kuvion2 osalta. Se vie O(n) aikaa. O(n) tarkoittaa monimutkaisuusfunktiota, joka laskee suoritukseen kuluvan ajan.

Joten kokonaisaika monimutkaisuus muuttuu O(n*2^m). Yllä olevassa esimerkissä m:n arvo on 8 ja n:n arvo 5.

Tässä ovat naiivin menetelmän vaiheet:

Vaihe 1) Ota jokin sarja kuviosta 1.
Vaihe 2) Yhdistä vaiheen 1 sarja kuvioon 2.
Vaihe 3) Jos se vastaa, tallenna alajakso.
Vaihe 4) Jos kuviossa 1 on jäljellä lisää sarjoja, siirry uudelleen vaiheeseen 1.
Vaihe 5) Tulosta pisin osajakso.

Optimaalinen alarakenne

Termi optimaalinen alirakenne tarkoittaa, että optimaalinen ratkaisu voidaan löytää ratkaisemalla alitehtävät. Esimerkiksi yllä olevassa esimerkissä meillä on kuvio1 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-ongelman rekursiivinen rakenne

Etsimme LCS:n alimerkkijonosta (alkuperäisestä merkkijonosta luodusta merkkijonosta). Sitten pidämme kirjaa alimerkkijonojen LCS:n pituudesta.

Tässä on toinen mielenkiintoinen ominaisuus päällekkäisyysping osaongelmatOngelman sanotaan olevan päällekkäinenping osaongelmia, jos ongelmanlause voidaan jakaa pienempiin osaongelmiin ja käyttää ohjelmassa useita kertoja.

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

Katso esimerkiksi rekursiopuuta. Tummanvärisessä laatikossa voit huomata päällekkäisyyksiä.ping osaongelmia. (”RG”, ”RA”), (”RG”, ”R”) ja muita kutsutaan useita kertoja.

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

Pisin yhteisen osajonon rekursiivinen menetelmä

Yllä oleva kaavio on rekursiivinen metodi. Jokaisella rekursiivisella funktiolla on perustapaus rekursion katkaisemiseksi tai pinosta palaamisen aloittamiseksi.

Tässä toteutuksessa käytämme perustapausta. Joten, algoritmi on seuraavanlainen:

• Jos kaikilla viimeistä elementtiä edeltävillä elementeillä on osuma, lisää pituutta yhdellä ja palauta arvo.
• Välitä funktiolle kaksi kuviota ja ota paluun maksimiarvo.
• Jos yhden kuvion pituus on nolla, meillä ei ole vertailtavaa alajaksoa. Palauta 0 tässä tapauksessa. Tämä on rekursion perustapaus.

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

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 sisää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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

lähtö:

Length of LCS is:  5

Pisin yhteisen osajonon dynaaminen ohjelmointimenetelmä (LCS)

Dynaaminen ohjelmointi tarkoittaa tavallisen rekursiivisen menetelmän optimointia. Jos esimerkiksi tarkastelemme rekursiivista tai naiivia lähestymistapaa, voimme nähdä, että funktiokutsuja on useita identtisiä. Dynaaminen ohjelmointi tallentaa kaikki laskelmat taulukkoon ja käyttää niitä uudelleen tarvittaessa.

Käytämme 2D-taulukkoa, jonka mitat ovat mxn, missä m ja n ovat kuvioiden 1 ja 2 pituudet. 2D-taulukko, voimme käyttää List-tietorakenteita Python tai vektori-/matriisitietorakenteissa C++.

Pseudo Code LCS:lle DP:n avulla:

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 LCS-taulukko, jota käytetään 2D-taulukkotietorakenteena dynaamisessa ohjelmoinnissa.

Käyttämämme logiikka on seuraava:

Vaihe 1) Jos i tai j on nolla, otamme annetuista kahdesta merkkijonosta tyhjän merkkijonon ja yritämme löytää niiden yhteiset alijonot. Koska ottamamme alijono on kuitenkin tyhjä, alijonon pituus on 0.

Vaihe 2) Jos kaksi merkkiä täsmää, annamme arvon (i,j)-indeksille kasvattamalla aiemmin laskettua LCS:ää, joka on (i-1,j-1)-indeksissä (edelliseltä riviltä).

Vaihe 3) Jos se ei täsmää, otamme kahden vierekkäisen indeksin suurimman LCS:n. Tällä tavoin meidän on täytettävä kaikki arvot 2D-taulukossa.

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

Pohjimmiltaan kaikki 2D-taulukon arvot sisältävät yhteisten alisekvenssien pituudet. Näistä viimeinen solu sisältää pisimmän yhteisen alisekvenssin 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 < 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;
}

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 DP-menetelmässä laskemme jokaisen tehtävän kerran. Rekursiivisessa menetelmässä päällekkäisyyksiä voi ollaping osaongelmia.

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 pattern1[i] on yhtä suuri kuin pattern2[j], päivitä DP[i][j] = DP[i-1][j-1] + 1.
• Jos pattern1[i] ei ole yhtä suuri kuin pattern2[j], niin DP[i][j] on suurin arvo 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, DP[m-1][n-1], sisältää pituuden.

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

UKK