Tìm Xâu Con Chung Dài Nhất Của Hai Xâu - Tài Liệu Text - 123doc

Tải bản đầy đủ (.docx) (15 trang)

1. Trang chủ
>>
2. Công nghệ thông tin
>>
3. Lập trình

Tìm xâu con chung dài nhất của hai xâu

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (243.63 KB, 15 trang )

HỌC VIỆN KỸ THUẬT QUÂN SỰKHOA CÔNG NGHỆ THÔNG TINBÁO CÁO MÔN HỌCPHÂN TÍCH VÀ THIẾT KẾ GIẢI THUẬTĐề 21:Bài toán xâu con chung dài nhất và thuật toán LCS(Longest Common SubsequenceGiáo viên hướng dẫn: Hà Đại DươngSinh viên thực hiện: Nguyễn Thị Ngọc HàLớp: HTTT14Hà Nội, 1/2018MỤC LỤCI. GIỚI THIỆU CHUNG VỀ PHƯƠNG PHÁP QUY HOẠCH ĐỘNG..........31.Ý tưởng....................................................................................................32.Mô hình...................................................................................................3II. THUẬT TOÁN LCS ( Longest Common Subsequence).................................41.Bài toán...................................................................................................42.Mô tả chi tiết thuật toán........................................................................43.Đánh giá độ phức tạp thuật toán..........................................................64. Tự xác định 2 bộ dữ liệu (với số phần tử N>=5), với mỗi bộ dữ liệuthực hiện từng thuật toán đã mô tả ở mục 2 và ghi ra kết quả mỗi bước. 75.Viết chương trình sử dụng C, C++.......................................................9I.GIỚI THIỆU CHUNG VỀ PHƯƠNG PHÁP QUY HOẠCH ĐỘNG1. Ý tưởngQui hoạch động (DP – Dynamic Programming), một thuật ngữ được nhàtoán học Rechard Bellman đưa ra vào năm 1957, là một phương phápgiải bài toán bằng cách kết hợp các lời giải cho các bài toán con của nógiống như phương pháp chia để trị (devide-and-conquer).Các bài thuật toán chia để trị để phân hoạch bài toán cần giải quyết thànhcác bài toán con độc lập với nhau, sau đó giải quyết bằng phương phápđệ qui (recursive) và kết hợp các lời giải lại để được lời giải của bài toánban đầu.Ngược lại qui hoạch động là phương pháp được áp dụng khi mà các bàitoán con của bài toán ban đầu (bài toán gốc) là không độc lập với nhau,chúng có chung các bài toán nhỏ hơn. Trong các trường hợp như vậy mộtthuật toán chia để trị sẽ thực hiện nhiều việc hơn những gì thực sự cầnthiết, nó sẽ lặp lại việc giải quyết các bài toán con nhỏ hơn đó. Một thuậttoán qui hoạch động sẽ chỉ giải quyết các bài toán con nhỏ một lần duynhất sau đó lưu kết quả vào một bảng và điều này giúp nó tránh khôngphải tính toán lại các kết quả mỗi khi gặp một bài toán nhỏ nào đó.Các bài toán qui hoạch động thường được áp dụng trong các bài toán tốiưu. Trong các bài toán tối ưu đó thường có nhiều nghiệm (lời giải). Mỗilời giải của một giá trị được lượng giá bằng cách sử dụng một hàm đánhgiá tùy thuộc vào các bài toán cụ thể và yêu cầu của bài toán là tìm ramột nghiệm có giá trị của hàm đánh giá tối ưu (lớn nhất hoặc nhỏ nhất).Qui hoạch động là một phương pháp chung rất hiệu quả để giải quyết cácvấn đề tối ưu chẳng hạn như trên các đối tượng sắp thứ tự từ trái quaphải, vấn đề tìm đường đi ngắn nhất, vấn đề điều khiển tối ưu… Khi đãhiểu rõ về qui hoạch động thì việc ứng dụng vào giải các bài toán tối ưukhông phải là quá khó khăn nhưng rất nhiều lập trình viên ban đầu phảimất rất nhiều thời gian mới có thể hiểu được.2. Mô hìnhQuá trình phát triển của một thuật toán qui hoạch động có thể chia làm 4bước như sau:- Bước 1: Xác định đặc điểm cấu trúc của giải pháp tối ưu của bài toán- Bước 2: Tìm công thức truy hồi (đệ qui) xác định giá trị của một giảipháp tối ưu.- Bước 3: Tính giá trị tối ưu của bài toán dựa vào các giá trị tối ưu củacác bài toán con của nó (bottom-up).- Bước 4: Xây dựng nghiệm đạt giá trị tối ưu từ các thông tin đã tính.Các bước 1-3 là các bước cơ bản trong việc giải quyết bất cứ bài toán tốiưu nào bằng phương pháp qui hoạch động. Bước 4 có thể bỏ qua nếu nhưbài toán chỉ yêu cầu tìm ra giá trị tối ưu chứ không cần chỉ ra nghiệm cụthể. Thông thường 2 bước đầu là quan trọng và cũng là khó khăn hơn cả,việc xác định cấu trúc nghiệm cũng như công thức truy hồi cần dựa vàokinh nghiệm và sự quan sát các trường hợp cụ thể của bài toán. Do vậytrong quá trình xây dựng thuật toán qui hoạch động cho các bài toán tốiưu chúng ta cần khảo sát các bộ giá trị thực tế của bài toán, giá trị tối ưuvà nghiệm của bài toán ứng với các bộ giá trị đó.II.THUẬT TOÁN LCS ( Longest Common Subsequence)1. Bài toánCho hai xâu A và xâu B. Tìm xâu con chung dài nhất của hai xâu A vàxâu B.Ứng dụng: Nó giải quyết rất nhiều bài toán trong thực tế nhằm đưa ramức độ tương đương giữa hai xâu.2. Mô tả chi tiết thuật toánCho hai xâu ký tự: A = (a1, a2… am),B = (b1, b2, …, bn) vàP = (p1, p2… pn) là xâu co chung dài nhất của A và B.Áp dụng nguyên lý quy hoạch động ta có thể giải quyết bài toán LCS.GọiT [i, j] là độ dài xâu con chung dài nhất của hai xâu A [1… i]i m vàB[1,…,j] j n , điều này có nghĩa là T[i,j] là độ dài xâu con chung dài nhấtcủa i ký tự đầu của xâu A và j ký tự đầu của xâu B. Do đó T [m, n] chínhlà độ dài xâu con chung dài nhất của A và B.a). Định lý:Cho hai xâu ký tự: A = (a1, a2…, am),B = ( b1, b2, …, bn) vàP = (p1, p2… pn) là xâu con chung dài nhất của A và B.- Nếu am = bn thì pk = am = bn và Pk-1 là LCS của Am-1 và Bn-1.- Nếu am bn và pk am thì P là LCS của Am-1 và B.- Nếu am bn và pk bn thì P là LCS của A và Bn-1.Chứng minh:- Nếu pk am thì chúng ta có thể thêm am = bn vào P chứa xâu con chungcủa A và B sẽ có độ dài là k+1, mâu thuẫn với giả thiết rằng P là LCScủa A và B, như vậy chúng ta phải có p k = am = bn. Bây giờ tiền tố P k-1có độ dài k-1 là xâu chung của A m-1 và Bn-1. Chúng ta chứng minh nólà một LCS, giả sử có một xâu chung W kết quả là W có độ dài lớnhơn k, đó là mâu thuẫn.- Nếu pk am, thì P là xâu chung của Am-1 và B. Nếu tồn tại một xâuchung W của Am-1 và B với chiều dài lớn hơn k, khi đó W có thể làxâu chung của Am-1 và B, trái với giả thiết rằng P là LCS của A và B.- Chứng minh tương tự như trên với pk bnb). Công thức truy hồi cho LCS:Qua định lý trên ta có thể rút ra một số vấn đề:- Trường hợp i=0 hoặc j = 0 thì độ dài xâu con chung dài nhất của A vàB là 0, nghĩa là T [0, j] = T [i, 0] = 0.- Trường hợp xét ai = bj thì ta thêm pk = am = bn vào P và độ dài xâu conchung dài nhất T[i, j] sẽ bằng độ dài xâu con chung dài nhất của A i-1và Bj-1 là T[i-1, j-1] cộng thêm 1.- Ngược lại nếu ai bj ta phải tìm LCS của Ai-1 và B, tìm LCS của A vàBj-1 là T [i-1, j] và T [i, j-1]. Xâu nào lớn hơn sẽ là LCS của A và B.Ta có : T[i, j] =Giải thuật 1 :1) Input (A[1,…, m], B[1,…, n])2) For i = 0 to m T [i, 0] =0;For j = 0 to n T [0, j] = 0;3) For i = 1 to mFor j = 1 to nIf A[i] = B[j] then T [i, j] = T [i-1, j-1] +1Else T [i, j] = max {T [i-1, j], T [i, j-1] }4) Output ( T[m,n])c). Truy vết tìm xâu con chung dài nhấtTa dựa vào bảng phương án để truy vết tìm xâuchung. Xuất phát từ ô T[m,n], giả sử đang đứng tại ô C[i,j]ta sẽ xét 2 ô trước đó là ô C[i-1,j], C[i,j-1], nếu một tronghai ô có giá trị bằng ô T[i,j] thì ta sẽ lùi về ô đó cho tới khihai ô trước có giá trị nhỏ hơn ô đang đứng C[i’,j’], Khi đóX[i’] = Y[j’]. Kết nạp A[i’] vào chuỗi P. Lùi về ô T[i’-1,j’-1] vàtiếp tục lặp lại cho tới T[0,0].Giải thuật 21). P := ‘’;m := length(A); n := length(B);A;B; T[m,n]2). While (n>0) and (m>0) dobegina). if (A[m-1]=B[n-1])beginP := A[m] +P;m := m -1 ;n := n-1 ;b). else if (T[m-1,n] >= T[m,n-1]) then m:=m-1;else then n:=n-1;end ;3). Output(P);3. Đánh giá độ phức tạp thuật toána) Quy hoạch động cho 2 xâu : Khảo sát độ phức tạp trên số phép gánInput (A [1… m], B [1… n])For i = 0 to m T [i, 0] =0;For j = 0 to n T [0, j] = 0;For i = 1 to mFor j = 1 to nPhép gán (m)Phép gán (n)Phép gán (m)Phép gán (m.n)If A[i] = B[j] then T [i, j] = T [i-1, j-1] +1Else T [i, j] = max {T [i-1, j], T [i, j-1] }Số phép gán(m.n)Output (T [m, n]) Tổng số phép gán = m+ n+ m+ m.n+ m.n = 2m.n + 2m + n =O(mn)b) Truy vết tìm xâu con chung dài nhất:1). P := ‘’;m := length(A); n := length(B);A;B; T[m,n]2). While (n>0) and (m>0) dobegina). if (A[m-1]=B[n-1])beginP := A[m] +P;m := m -1 ;n := n-1 ;b). else if (T[m-1,n] >= T[m,n-1]) then m:=m-1;else then n:=n-1;end ;3). Output(P);Số phép so sánh của vòng lặp while là min(m,n)Số phép gán trong vòng lặp m+nThuật toán có độ phức tạp làO((m+n)*min(m,n))=O(m+n).4. Tự xác định 2 bộ dữ liệu (với số phần tử N>=5), với mỗi bộ dữ liệuthực hiện từng thuật toán đã mô tả ở mục 2 và ghi ra kết quả mỗibướca). Bộ dữ liệu 1Hai chuỗi: A= “AABEF”B = “ EABCEGF”Công thức truy hồi cho LCS:B[j]EABCEGF00 +1000000A00+1111111A001+111111B0+10122+1222E0112233+13F01122334A[i]Bảng phương án tìm độ dài xâu con chung dài nhấtTruy vết tìm xâu con chung dài nhấtB[j]EABCEGF00000000A00111111A00111111B00122222E01122333F01122334A[i]Bảng truy vết tìm xâu chung dài nhất Xâu con chung dài nhất cần tìm là “ ABEF”b). Bộdữ liệu 2:Hai chuỗi :A= ”123457”B =”13545”Công thức truy hồi cho LCS:B[j]135450+1000001011111201+1111130122+1224012+123+1350123347012334A[i]Bảng phương án tìm độ dài xâu con chung dài nhấtTruy vết xâu con chung dài nhất13545000000011111011111012222012233012334012334Bảng truy vết tìm xâu chung dài nhất Xâu con chung lớn nhất là :”1345”5. Viết chương trình sử dụng C, C++#include<iostream>#include<cstdlib>#include<algorithm>#include<string.h>#include<cstring>#include<stdio.h>#define MAX 101using namespace std;void ini(string X ,string Y , int L[MAX][MAX], int n , int m){int i,j;for (i=0;i= L[n][m-1]){n--;}else{m--;}}}return word;}int main(){string X,Y;int L[MAX][MAX];cin >> X>>Y;int n = X.length() + 1;int m = Y.length() + 1;L[n][m];ini(X,Y,L,n,m);int sol = LCS(X,Y,L,n,m);for (int i=0; i