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ử, X và Ylà 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 X và Y, nếu Z là một con của cả hai X và Y.
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 m và Y 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.
Có 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 > và 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 X và Y.
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 đóm và n là độ dài của hai chuỗi.
Thí dụ
Trong ví dụ này, chúng tôi có hai chuỗi X = BACDB và Y = 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.