Barisan Umum Terpanjang: Python, C++ Example

Apa Barisan Umum Terpanjang?

Urutan Umum Terpanjang (LCS) berarti Anda akan diberikan dua string/pola/urutan objek. Di antara dua barisan/string ini, Anda perlu menemukan barisan elemen terpanjang dalam urutan yang sama yang ada di kedua string atau pola.

Example

Misalnya, ada dua string yang disediakan.

Mari kita berasumsi bahwa,

Pola_1 = “RGBGARGA”
Pola_2 = “BGRARG”

• Dari pattern_1, sequence dapat dihasilkan seperti “RGB”, “RGGA”, “RGAR”. Untuk membuat urutan, Anda perlu mempertahankan posisi relatif setiap karakter dalam string.
• Dari pattern_2, kita dapat menghasilkan urutan seperti “BGR”, “BRAG”, “RARG”. Urutan dapat dihasilkan asalkan mempertahankan posisi relatif string asli.

Istilah posisi relatif berarti keteraturan.

Misalnya, “BRG” adalah urutan yang valid karena “B” muncul terlebih dahulu, lalu “R”, dan kemudian “G” pada string asli pattern_2. Namun, jika urutannya adalah “RBRG”, maka itu tidak valid. Karena pada string asli (pattern_2), “B” didahulukan.

Kita mempunyai dua pilihan untuk mencari Barisan Persekutuan Terpanjang dari dua barisan atau larik yang diberikan.

• Metode naif
• Solusi Pemrograman Dinamis: Urutan Umum Terpanjang juga dikenal sebagai LCS.

Solusi naif memiliki kompleksitas waktu yang lebih besar dan bukan solusi optimal. Dengan menggunakan Solusi Pemrograman Dinamis (DP), kami mengatasi masalah kompleksitas.

Metode Naif

Metode naif merupakan pendekatan sederhana terhadap permasalahan tanpa mempertimbangkan kompleksitas waktu dan faktor optimasi lainnya.

Metode Naif terdiri dari “Brute Force”, banyak loop, metode rekursif dalam banyak kasus.

Istilah brute force berarti menelusuri semua pola yang mungkin untuk suatu masalah tertentu.

Example

Dari contoh pattern1 dan pattern2 di atas, kita asumsikan pattern1 panjangnya m dan pattern2 panjangnya n. Untuk memeriksa setiap kemungkinan kasus, kita perlu mengevaluasi setiap kemungkinan rangkaian pola1 dengan pola2.

Berikut string 4 huruf sederhana “ABCD”. Misalnya, kita perlu membuat barisan dari “ABCD”. Entah kita bisa mengambil karakternya atau tidak. Artinya, untuk setiap karakter, kita punya dua pilihan.

Mereka adalah:

• Karakter tersebut akan ditambahkan ke selanjutnya.
• Karakter tidak akan ditambahkan ke selanjutnya.

Di sini, gambar menunjukkan semua barisan yang dapat kita buat dari string “ABCD”.

Urutan dengan 1 karakter:

Urutan dengan 2 karakter:

Urutan dengan 3 karakter:

Dari diagram di atas, ada 14 barisan. Jika kita tidak mengambil huruf, pada dasarnya string kosong, maka total barisannya adalah 15. Apalagi string “ABCD” itu sendiri adalah barisan. Jadi, jumlah barisannya adalah 16.

Jadi, dimungkinkan untuk menghasilkan 2⁴ atau 16 urutan dari “ABCD”. Kemudian, seutas tali dengan panjang m harus total urutan 2^m.

Untuk setiap subsekuen, kita perlu memeriksanya untuk keseluruhan pola2. Ini akan memakan waktu 0(n). 0(n) berarti fungsi kompleksitas yang menghitung waktu yang dibutuhkan untuk eksekusi.

Jadi, total kompleksitas waktu menjadi HAI(n*2^m). Sebagai contoh, kita telah melihat di atas nilai m=8 dan n=5.

Berikut langkah-langkah Metode Naif:

Langkah 1) Ambil urutan dari pola1.
Langkah 2) Cocokkan urutan dari langkah 1 dengan pola2.
Langkah 3) Jika cocok, simpan selanjutnya.
Langkah 4) Jika masih banyak urutan yang tersisa di pola1, lanjutkan ke langkah 1 lagi.
Langkah 5) Cetak urutan terpanjang.

Substruktur Optimal

Istilah substruktur optimal berarti solusi optimal (sederhana) dapat ditemukan dengan menyelesaikan submasalah. Misalnya, pada contoh di atas, kita memiliki pola1 dan pola2.

Langkah 1) Ambil dua karakter pertama dari setiap pola

Langkah 2) Ambil karakter ketiga hingga kelima dari setiap pola.

Langkah 3) Lanjutkan hal yang sama dengan karakter yang tersisa.

Kami menemukan LCS pada sub-string (string yang dihasilkan dari string asli). Kemudian kami mencatat panjang LCS substringnya.

Sekarang, inilah properti menarik lainnya sub-masalah yang tumpang tindih. Suatu permasalahan dikatakan memiliki submasalah yang tumpang tindih jika rumusan masalah tersebut dapat dipecah menjadi submasalah kecil dan digunakan beberapa kali dalam program.

Diagram di bawah menunjukkan bahwa algoritma rekursif memanggil fungsi dengan parameter yang sama beberapa kali.

Misalnya, mari kita lihat pohon rekursi.

Dalam kotak berwarna gelap, Anda dapat melihat sub-masalah yang tumpang tindih. (“RG”, “RA”), (“RG”, “R”) dan lainnya disebut beberapa kali.

Untuk mengoptimalkan ini, kami memiliki pendekatan Pemrograman Dinamis (DP).

Metode Rekursif Urutan Komunikasi Terpanjang

Grafik yang ditunjukkan di atas adalah metode rekursif. Setiap fungsi rekursif memiliki kasus dasar untuk menghentikan rekursi atau mulai kembali dari tumpukannya.

Untuk implementasi ini, kami akan menggunakan kasus dasar. Sehingga algoritma seperti berikut ini:

• Jika semua elemen sebelum elemen terakhir cocok, tambah panjangnya satu dan kembalikan
• Berikan dua pola ke fungsi, dan ambil nilai pengembalian maksimum
• Jika suatu pola mempunyai panjang nol, maka kita tidak mempunyai urutan berikutnya untuk dibandingkan. Kembalikan 0 dalam kasus ini. Ini adalah kasus dasar dari rekursi.

Kode Semu:

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)

Implementasi di 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;
}

Keluaran:

Length of LCS is: 5

Implementasi dengan 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("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Keluaran:

Lenght of LCS is:  5

Metode Pemrograman Dinamis Longest Common Subsequence (LCS)

Pemrograman dinamis berarti mengoptimalkan metode rekursif biasa. Misalnya, jika kita melihat grafik pendekatan rekursif atau naif, kita dapat melihat bahwa ada beberapa pemanggilan fungsi yang sama. Metode Pemrograman Dinamis mencatat semua perhitungan dalam array dan menggunakannya bila diperlukan.

Kita akan menggunakan array 2D dengan dimensi mxn, dimana m dan n adalah panjang pattern1 dan pattern2.

Untuk Array 2D, kita dapat menggunakan struktur data List di python atau struktur data vektor/array di C++.

Kode Pseudo untuk LCS menggunakan DP:

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]

Berikut tabel LCS yang digunakan sebagai struktur data array 2D untuk pendekatan pemrograman dinamis.

Mari kita bahas logika yang kita gunakan di sini. Langkah-langkahnya adalah:

Langkah 1) Jika i atau j adalah nol, kita mengambil string kosong dari dua string yang diberikan dan mencoba mencari barisan yang sama. Namun, karena substring yang kita ambil kosong, panjang selanjutnya adalah 0.

Langkah 2) Jika dua karakter cocok, kita akan menetapkan nilai ke indeks (i,j) dengan menaikkan LCS yang dihitung sebelumnya, yang ada di indeks (i-1,j-1) (dari baris sebelumnya).

Langkah 3) Jika tidak cocok, maka kita akan mengambil LCS maksimal dari dua indeks yang berdekatan. Dan dengan cara ini, kita perlu mengisi semua nilai dalam array 2D.

Langkah 4) Terakhir, kami akan mengembalikan nilai sel terakhir dari array 2D.

Pada dasarnya, semua nilai dalam array 2D berisi panjang rangkaian berikutnya. Di antaranya, sel terakhir berisi panjang barisan persekutuan terpanjang.

Implementasi di 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;
}

Keluaran:

Length of LCS: 5

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

Keluaran:

Length of LCS: 5

Jadi, kedua dawai tersebut mempunyai barisan persekutuan terpanjang dengan panjang 5.

Singkatnya, kami hanya menghitung setiap tugas satu kali dalam metode DP dalam metode DP. Dalam metode rekursif, kita mungkin mempunyai submasalah yang tumpang tindih.

Dalam Algoritma Pemrograman Dinamis ini, kami menggunakan matriks 2D. Akan ada dua string yang diberikan (anggap keduanya memiliki panjang n). Maka ruang yang dibutuhkan dalam array tersebut adalah nx n. Jika stringnya cukup besar, kita memerlukan versi solusi DP yang memorinya dioptimalkan.

Logika sederhana yang diambil dalam kode adalah:

• Deklarasikan DP Array 2D[m][n].
• Isi baris pertama dan kolom pertama array DP dengan 0.
• Ambil i dan j untuk iterasi.
• Jika pola1[i] sama dengan pola2[j], maka perbarui DP[i][j] = DP[i-1][j-1] + 1
• Jika pola1[i] tidak sama dengan pola2[j], maka DP[i][j] akan menjadi nilai maksimum antara DP[i-1][j] dan DP[i][j-1].
• Lanjutkan hingga i dan j mencapai m dan n.
• Elemen terakhir atau DP[m-1][n-1], akan berisi panjangnya.

Di sini, dialamatkan sebagai DP[m-1][n-1], karena indeks array dimulai dari 0.

Ringkasan

• Metode DP memiliki kompleksitas waktu yang lebih rendah; yaitu O(mn), di mana m dan n adalah panjang string atau array input.
• DP adalah pendekatan yang lebih cepat dibandingkan pendekatan rekursif, dengan kompleksitas waktu HAI(n*2^m).
• Pemrograman dinamis (DP) tidak dioptimalkan untuk memori. Kami menggunakan array 2D yang memiliki panjang m*n. Jadi, kompleksitas ruangnya adalah (m*n).
• Metode rekursif, dalam skenario terburuk, memori tertinggi yang akan ditempati adalah m+n, pada dasarnya adalah total panjang string yang dimasukkan.
• Komputer modern saat ini cukup untuk menangani jumlah memori ini.