DAA - Urutan Umum Terpanjang

Masalah persekutuan terpanjang adalah menemukan urutan terpanjang yang ada di kedua string yang diberikan.

Urutan

Mari kita pertimbangkan urutan S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >.

Sebuah barisan Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > di atas S disebut deretan S, jika dan hanya jika ia dapat diturunkan dari penghapusan S beberapa elemen.

Urutan Umum

Seharusnya, X dan Yadalah dua urutan di atas satu set elemen yang terbatas. Kita bisa bilang begituZ adalah kelanjutan umum dari X dan Y, jika Z adalah kelanjutan dari keduanya X dan Y.

Urutan Umum Terpanjang

Jika serangkaian urutan diberikan, masalah urutan terpanjang adalah menemukan urutan yang sama dari semua urutan yang memiliki panjang maksimal.

Masalah urutan umum terpanjang adalah masalah ilmu komputer klasik, dasar dari program perbandingan data seperti utilitas-diff, dan memiliki aplikasi dalam bioinformatika. Ini juga banyak digunakan oleh sistem kontrol revisi, seperti SVN dan Git, untuk merekonsiliasi beberapa perubahan yang dibuat pada kumpulan file yang dikontrol revisi.

Metode Naif

Membiarkan X menjadi urutan panjang m dan Y urutan panjang n. Periksa setiap berikutnya dariX apakah itu kelanjutan dari Y, dan mengembalikan urutan umum terpanjang yang ditemukan.

Ada 2^m selanjutnya dari X. Menguji urutan apakah itu merupakan kelanjutan dariY mengambil O(n)waktu. Dengan demikian, algoritma naif akan mengambilO(n2^m) waktu.

Pemrograman Dinamis

Misalkan X = <x ₁ , x ₂ , x ₃ ,…, x _m > dan Y = <y ₁ , y ₂ , y ₃ ,…, y _n > menjadi barisan. Untuk menghitung panjang elemen digunakan algoritma berikut.

Dalam prosedur ini, tabel C[m, n] dihitung dalam urutan mayor baris dan tabel lain B[m,n] dihitung untuk membangun solusi optimal.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Algoritme ini akan mencetak urutan umum terpanjang X dan Y.

Analisis

Untuk mengisi tabel, bagian luar for loop berulang m waktu dan batin for loop berulang nwaktu. Oleh karena itu, kompleksitas algoritme adalah O (m, n) , dimanam dan n adalah panjang dua senar.

Contoh

Dalam contoh ini, kami memiliki dua string X = BACDB dan Y = BDCB untuk menemukan urutan persekutuan terpanjang.

Mengikuti algoritma LCS-Length-Table-Formulation (seperti yang dinyatakan di atas), kami telah menghitung tabel C (ditampilkan di sisi kiri) dan tabel B (ditampilkan di sisi kanan).

Dalam tabel B, alih-alih 'D', 'L' dan 'U', kami masing-masing menggunakan panah diagonal, panah kiri, dan panah atas. Setelah menghasilkan tabel B, LCS ditentukan oleh fungsi LCS-Print. Hasilnya adalah BCB.