Pikim ühine jada: Python, C++ Näide

Mis on pikim ühine jada?

Longest Common Subsequence (LCS) tähendab, et teile antakse kaks objektide stringi/mustrit/jada. Nende kahe jada/stringi hulgast peate leidma pikima elementide alamjada samas järjekorras, mis on mõlemas stringis või mustris.

Näide

Näiteks on ette nähtud kaks stringi.

Oletame, et

Pattern_1 = "RGBGARGA"
Muster_2 = "BGRARG"

• Mustrist_1 saab luua selliseid jadasid nagu “RGB”, “RGGA”, “RGAR”. Jada loomiseks peate säilitama iga tähemärgi suhtelise asukoha stringis.
• Mustrist_2 saame toota selliseid jadasid nagu "BGR", "BRAG", "RARG". Jadasid saab luua seni, kuni need säilitavad algse stringi suhtelise asukoha.

Mõiste suhteline positsioon tähendab korda.

Näiteks „BRG” on kehtiv jada, sest algses stringimustris_2 ilmus kõigepealt „B”, seejärel „R” ja seejärel „G”. Kui jada on aga „RBRG”, siis see ei kehti. Kuna algses stringis (muster_2) on "B" esimene.

Antud kahest järjestusest või massiivist pikima ühise alamjada leidmiseks on kaks võimalust.

• Naiivne meetod
• Dünaamiline programmeerimislahendus: Pikimat ühist alljada tuntakse ka kui LCS-i.

Naiivne lahendus on ajaliselt keerulisem ja ei ole optimaalne lahendus. Dünaamilise programmeerimislahenduse (DP) abil saame keerukuse probleemist üle.

Naiivne meetod

Naiivne meetod on lihtne lähenemine probleemile, sõltumata ajalisest keerukusest ja muudest optimeerimisteguritest.

Naiivne meetod koosneb "toorest jõust", mitmest tsüklist ja enamikul juhtudel rekursiivsetest meetoditest.

Mõiste toores jõud tähendab antud probleemi kõigi võimalike mustrite läbimist.

Näide

Eeldame ülaltoodud mustri1 ja mustri2 näite põhjal, et mustri 1 pikkus on m ja mustri2 pikkus n. Kõigi võimalike juhtumite kontrollimiseks peame hindama mustri 1 kõiki võimalikke alamjadasid mustriga 2.

Siin on lihtne neljatäheline string "ABCD". Näiteks peame looma ABCD-st jada. Kas me võime võtta tegelase või mitte. See tähendab, et iga tegelase jaoks on meil kaks valikut.

Nemad on:

• Tegelane lisatakse alamjadasse.
• Tegelast alamjadasse ei lisata.

Siin on piltidel näha kõik järjestused, mida saame stringist "ABCD" teha.

1 tähemärgiga järjestus:

2 tähemärgiga jadad:

3 tähemärgiga jadad:

Ülaltoodud diagrammil on 14 järjestust. Kui me ei võta tähti, põhimõtteliselt tühja stringi, on jadasid kokku 15. Pealegi on string “ABCD” ise jada. Seega on järjestusi kokku 16.

Seega on võimalik luua 2⁴ või 16 alamjada "ABCD-st". Seejärel nöör pikkusega m kokku peab olema 2^m.

Iga alamjada puhul peame kontrollima seda kogu mustri jaoks2. See võtab 0 (n) aega. 0(n) tähendab keerukuse funktsiooni, mis arvutab täitmiseks kuluva aja.

Seega muutub kogu aja keerukus O(n*2^m). Näite puhul oleme eespool näinud väärtusi m=8 ja n=5.

Siin on naiivse meetodi sammud:

Step 1) Võtke jada mustrist1.
Step 2) Sobitage 1. etapi jada mustriga 2.
Step 3) Kui see sobib, salvestage alamjada.
Step 4) Kui mustris1 on jäänud rohkem jada, jätkake uuesti sammuga 1.
Step 5) Printige pikim alljada.

Optimaalne alusstruktuur

Mõiste optimaalne alamstruktuur tähendab, et alamülesannete lahendamisel on võimalik leida optimaalne (lihtne) lahendus. Näiteks ülaltoodud näites on meil muster1 ja muster2.

Step 1) Võtke igast mustrist kaks esimest tähemärki

Step 2) Võtke igast mustrist kolmas kuni viies märk.

Step 3) Jätkake samamoodi ülejäänud tähemärkidega.

Leiame LCS-i alamstringilt (string, mis on genereeritud algsest stringist). Seejärel peame arvestust alamstringide LCS-i pikkuse kohta.

Nüüd on siin veel üks huvitav vara, mis on kattuvad alamprobleemid. Probleemil on väidetavalt kattuvad alamprobleemid, kui probleemipüstitust saab jagada väikesteks alamprobleemideks ja kasutada programmis mitu korda.

Alloleval diagrammil on näha, et rekursiivne algoritm kutsus sama parameetriga funktsiooni mitu korda välja.

Näiteks vaatame rekursioonipuud.

Tumedas kastis on märgata kattuvaid alamprobleeme. (“RG”, “RA”), (“RG”,”R”) ja teisi kutsutakse mitu korda.

Selle optimeerimiseks kasutame lähenemist Dünaamiline programmeerimine (DP).

Pikima sidejada rekursiivne meetod

Ülaltoodud graafik on rekursiivne meetod. Igal rekursiivsel funktsioonil on põhijuht rekursiooni katkestamiseks või pinust naasmise alustamiseks.

Selle teostuse jaoks kasutame põhijuhtumit. Niisiis, algoritm on selline:

• Kui kõik elemendid enne viimast elementi kattuvad, suurendage pikkust ühe võrra ja tagastage
• Edastage funktsioonile kaks mustrit ja võtke tagastuse maksimaalne väärtus
• Kui ühe mustri pikkus on null, siis pole meil võrreldavat alamjada. Sel juhul tagasta 0. See on rekursiooni põhijuhtum.

Pseudokood:

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)

Rakendamine sisse 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;
}

Väljund:

Length of LCS is: 5

Rakendamine pythonis

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

Väljund:

Lenght of LCS is:  5

Pikima ühise alamjärjestuse dünaamilise programmeerimise meetod (LCS)

Dünaamiline programmeerimine tähendab lihtsa rekursiivse meetodi optimeerimist. Näiteks kui näeme rekursiivse või naiivse lähenemise graafikut, näeme, et seal on mitu sama funktsiooni väljakutset. Dünaamilise programmeerimise meetod salvestab kõik arvutused massiivi ja kasutab seda vajaduse korral.

Kasutame 2D massiivi mõõtmetega mxn, kus m ja n on mustri1 ja muster2 pikkused.

eest 2D massiiv, saame kasutada pythonis loendi andmestruktuure või vektor/massiivi andmestruktuure C++.

DP-d kasutava LCS-i pseudokood:

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]

Siin on tabel LCS, mida kasutatakse dünaamilise programmeerimise lähenemisviisi 2D-massiivi andmestruktuurina.

Arutleme siin kasutatud loogika üle. Sammud on:

Step 1) Kui i või j on null, võtame antud kahest stringist tühja stringi ja püüame leida ühiseid alamjadasid. Kuna aga võetav alamstring on tühi, on alamjada pikkus 0.

Step 2) Kui kaks tähemärki kattuvad, omistame väärtuse (i,j) indeksile, suurendades eelnevalt arvutatud LCS-i, mis sisaldub indeksis (i-1,j-1) (eelmisest reast).

Step 3) Kui see ei ühti, võtame kahe külgneva indeksi max LCS-i. Ja sel viisil peame täitma kõik 2D-massiivi väärtused.

Step 4) Lõpuks tagastame 2D-massiivi viimase lahtri väärtuse.

Põhimõtteliselt sisaldab kogu 2D-massiivi väärtus tavaliste alamjadade pikkust. Nende hulgas sisaldab viimane lahter pikima ühise alamjada pikkust.

Rakendamine sisse 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;
}

Väljund:

Length of LCS: 5

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

Väljund:

Length of LCS: 5

Seega on mõlemal stringil pikim ühine alamjada pikkusega 5.

Lühidalt, me lihtsalt arvutame iga ülesande üks kord DP-meetodis DP-meetodis. Rekursiivse meetodi korral võivad meil olla kattuvad alamprobleemid.

Selles dünaamilise programmeerimise algoritmis kasutame 2D-maatriksit. Antakse kaks stringi (oletame, et mõlema pikkus on n). Siis on massiivi vajaminev ruum nx n. Kui stringid on piisavalt suured, vajame DP-lahenduse mälu jaoks optimeeritud versiooni.

Koodis kasutatud lihtsustatud loogika on järgmine:

• Deklareerige 2D massiiv DP[m][n].
• Täitke DP-massiivi esimene rida ja esimene veerg 0-ga.
• Kasutage iteratsiooniks i ja j.
• Kui muster1[i] võrdub mustriga2[j], värskendage DP[i][j] = DP[i-1][j-1] + 1
• Kui muster1[i] ei võrdu mustriga2[j], on DP[i][j] maksimaalne väärtus DP[i-1][j] ja DP[i][j-1] vahel.
• Jätkake, kuni i ja j jõuavad punktideni m ja n.
• Viimane element ehk DP[m-1][n-1] sisaldab pikkust.

Siin on see adresseeritud kui DP[m-1][n-1], kuna massiivi indeks algab 0-st.

kokkuvõte

• DP-meetodil on väiksem ajaline keerukus; see on O(mn), kus m ja n on sisendstringi või massiivi pikkus.
• DP on ajalise keerukusega kiirem lähenemine kui rekursiivne O(n*2^m).
• Dünaamiline programmeerimine (DP) ei ole mälu optimeeritud. Kasutasime 2D massiivi, mille pikkus on m * n. Seega on ruumi keerukus (m*n).
• Rekursiivne meetod, halvima stsenaariumi korral on suurim mälu, mida see hõivab, m+n, mis on põhimõtteliselt sisestatud stringi kogupikkus.
• Tänapäeva kaasaegne arvuti on selle mälumahuga hakkama saamiseks piisav.