DAA - Trình tự con chung dài nhất

Vấn đề dãy con phổ biến dài nhất là tìm dãy dài nhất tồn tại trong cả hai chuỗi đã cho.

Trình tự con

Chúng ta hãy xem xét một dãy S = <s 1 , s 2 , s 3 , s 4 ,…, s n >.

Dãy Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > trên S được gọi là dãy con của S, nếu và chỉ khi nó có thể được suy ra từ việc xóa S của một số phần tử.

Trình tự con chung

Giả sử, XYlà hai chuỗi trên một tập hợp hữu hạn các phần tử. Chúng ta có thể nói về điều đóZ là một dãy con chung của XY, nếu Z là một con của cả hai XY.

Trình tự con chung dài nhất

Nếu một tập hợp các trình tự được đưa ra, bài toán con chung dài nhất là tìm một dãy con chung của tất cả các chuỗi có độ dài tối đa.

Bài toán con phổ biến dài nhất là một bài toán khoa học máy tính cổ điển, là cơ sở của các chương trình so sánh dữ liệu như tiện ích khác biệt, và có các ứng dụng trong tin sinh học. Nó cũng được sử dụng rộng rãi bởi các hệ thống kiểm soát sửa đổi, chẳng hạn như SVN và Git, để đối chiếu nhiều thay đổi được thực hiện đối với bộ sưu tập tệp được kiểm soát bởi phiên bản.

Phương pháp ngây thơ

Để cho X là một chuỗi độ dài mY một chuỗi chiều dài n. Kiểm tra mọi phần sau củaX cho dù nó là một dãy con của Yvà trả về dãy con chung dài nhất được tìm thấy.

2m chuỗi con của X. Kiểm tra các trình tự xem nó có phải là một chuỗi con củaY nhận O(n)thời gian. Do đó, thuật toán ngây thơ sẽ lấyO(n2m) thời gian.

Lập trình năng động

Gọi X = <x 1 , x 2 , x 3 ,…, x m >Y = <y 1 , y 2 , y 3 ,…, y n > là các dãy. Để tính độ dài của một phần tử, thuật toán sau được sử dụng.

Trong quy trình này, bảng C[m, n] được tính theo thứ tự chính của hàng và một bảng khác B[m,n] được tính toán để tạo ra giải pháp tối ưu.

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)

Thuật toán này sẽ in ra dãy con chung dài nhất của XY.

Phân tích

Để điền bảng, bên ngoài for lặp lại vòng lặp m thời gian và bên trong for lặp lại vòng lặp nlần. Do đó, độ phức tạp của thuật toán là O (m, n) , trong đómn là độ dài của hai chuỗi.

Thí dụ

Trong ví dụ này, chúng tôi có hai chuỗi X = BACDBY = BDCB để tìm dãy con chung dài nhất.

Theo thuật toán LCS-Độ dài-Bảng-Công thức (như đã nêu ở trên), chúng ta đã tính được bảng C (được hiển thị ở bên trái) và bảng B (được hiển thị ở bên phải).

Trong bảng B, thay vì 'D', 'L' và 'U', chúng tôi sử dụng mũi tên chéo, mũi tên trái và mũi tên lên tương ứng. Sau khi tạo bảng B, LCS được xác định bởi chức năng LCS-Print. Kết quả là BCB.