Barisan Umum Terpanjang: Python, C++ Example

Apa Barisan Umum Terpanjang?

Longest Common Subsequence (LCS) berarti Anda akan diberikan dua string, pola, atau urutan objek. Di antara kedua urutan atau string ini, Anda perlu menemukan suburutan terpanjang dari elemen-elemen yang berada dalam urutan yang sama yang terdapat di kedua string atau pola tersebut.

Example

Sebagai contoh, terdapat dua string yang diberikan. Mari kita asumsikan bahwa:

Pola_1 = “RGBGARGA”
Pola_2 = “BGRARG”

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

Istilah posisi relatif berarti keteraturan.

Sebagai contoh, “BRG” adalah urutan yang valid karena “B” muncul pertama, kemudian “R,” dan kemudian “G” dalam string asli pattern_2. Namun, jika urutannya adalah “RBRG”, maka itu tidak valid, karena dalam string asli (pattern_2), “B” muncul pertama.

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 sederhana memiliki kompleksitas waktu yang lebih besar dan bukan solusi optimal. Dengan menggunakan Solusi Pemrograman Dinamis (DP), kita dapat mengatasi masalah kompleksitas tersebut.

Metode Naif

Metode Naif adalah pendekatan sederhana untuk masalah ini, terlepas dari kompleksitas waktu dan faktor optimasi lainnya. Metode ini terdiri dari "brute force", banyak perulangan, dan panggilan rekursif dalam sebagian besar kasus. Istilah brute force berarti menelusuri semua pola yang mungkin untuk 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 adalah contoh string sederhana 4 huruf “ABCD”. Misalnya, kita perlu membuat urutan dari “ABCD”. Kita bisa mengambil karakter atau tidak. Itu berarti, untuk setiap karakter, kita memiliki dua pilihan:

• 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, terdapat 14 urutan. Jika kita tidak mengambil huruf apa pun, pada dasarnya string kosong, maka total urutannya adalah 15. Selain itu, string “ABCD” itu sendiri merupakan sebuah urutan. Jadi, total urutannya adalah 16.

Jadi, dimungkinkan untuk menghasilkan 2^4 atau 16 suburutan dari “ABCD”. Kemudian, sebuah string dengan panjang m akan memiliki suburutan total sebanyak 2^m.

Untuk setiap suburutan, kita perlu memeriksanya untuk seluruh pola2. Ini akan membutuhkan waktu O(n). O(n) berarti fungsi kompleksitas yang menghitung waktu yang dibutuhkan untuk eksekusi.

Jadi, total kompleksitas waktu menjadi O(n*2^m). Untuk contoh yang telah kita lihat di atas, nilai m=8 dan n=5.

Berikut langkah-langkah Metode Naif:

Langkah 1) Ambil urutan dari pola 1.
Langkah 2) Cocokkan urutan dari langkah 1 dengan pola 2.
Langkah 3) Jika cocok, simpan selanjutnya.
Langkah 4) Jika masih ada urutan yang tersisa di pola1, maka ulangi langkah 1.
Langkah 5) Cetak urutan terpanjang.

Substruktur Optimal

Istilah substruktur optimal berarti solusi optimal 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.

Struktur Rekursif dari masalah LCS

Kita mencari LCS (Least Common Substance) pada substring (string yang dihasilkan dari string asli). Kemudian kita menyimpan catatan panjang LCS dari substring tersebut.

Sekarang, inilah properti menarik lainnya tumpang tindihping sub-masalahSuatu masalah dikatakan memiliki tumpang tindih.ping sub-masalah jika pernyataan masalah dapat dipecah menjadi sub-masalah kecil dan digunakan beberapa kali dalam program.

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

Sebagai contoh, perhatikan pohon rekursi. Di dalam kotak berwarna gelap, Anda dapat melihat adanya tumpang tindih.ping sub-masalah. (“RG”, “RA”), (“RG”, “R”), dan lainnya dipanggil beberapa kali.

Untuk mengoptimalkan hal ini, kami memiliki pendekatan sebagai berikut: Pemrograman Dinamis (DP).

Metode Rekursif Urutan Bagian Terpanjang yang Sama

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

Untuk implementasi ini, kita akan menggunakan kasus dasar. Jadi, algoritma seperti berikut ini:

• Jika semua elemen sebelum elemen terakhir memiliki kecocokan, maka tambahkan satu panjang dan kembali.
• Berikan dua pola ke fungsi tersebut, dan ambil nilai maksimum dari nilai yang dikembalikan.
• 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.

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

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

Keluaran:

Length of LCS is:  5

Metode Pemrograman Dinamis Urutan Bagian Umum Terpanjang (LCS)

Pemrograman dinamis berarti mengoptimalkan metode rekursif biasa. Misalnya, jika kita melihat grafik pendekatan rekursif atau naif, kita dapat melihat bahwa ada beberapa panggilan fungsi yang identik. Metode Pemrograman Dinamis mencatat semua perhitungan dalam sebuah array dan menggunakannya kembali saat dibutuhkan.

Kita akan menggunakan array 2D dengan dimensi mxn, di mana m dan n adalah panjang pola1 dan pola2. Untuk sebuah Array 2D, kita dapat menggunakan struktur data List di Python atau struktur data vektor/array di C++.

Pseudo Code 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 adalah 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 menemukan suburutan yang sama. Namun, karena substring yang kita ambil kosong, panjang suburutannya adalah 0.

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

Langkah 3) Jika tidak cocok, maka kita akan mengambil LCS maksimum dari dua indeks yang berdekatan. 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 larik 2D berisi panjang suburutan umum. Di antara nilai-nilai tersebut, sel terakhir berisi panjang suburutan umum 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 < 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;
}

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, kita hanya menghitung setiap tugas sekali dalam metode DP. Dalam metode rekursif, mungkin ada tumpang tindih.ping submasalah.

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 pattern1[i] sama dengan pattern2[j], maka perbarui DP[i][j] = DP[i-1][j-1] + 1.
• Jika pattern1[i] tidak sama dengan pattern2[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, DP[m-1][n-1], akan berisi panjangnya.

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

Pertanyaan Umum Demo Slot