Tập bài giảng Thiết kế và đánh giá thuật toán (Phần 2)

1i và p2 được gán V[j] tức là C j 1i , V[j] lưu trữ giá trị C j i sẽ được gán bới p1+p2, sau đó p1 được gán bởi p2, nghĩa là khi j tăng lên 1 đơn vị thành j+1 thì p1 là C j 1i và nó được dùng để tính C 1j i  . - Cuối cùng với j = i thực hiện gán V[i] giá trị 1 tức là C i i = 1. Giải thuật: Comb(n, k ) { V[0] = 1; V[1] = 1; for(i=2;i<=n;i++) { p1 := V[0]; for(j=1;i<=i-1;j++) { p2 := V[j]; V[j]:= p1+p2; p1:= p2; } V[i] := 1; } return(V[k]); } Dễ thấy rằng độ phức tạp của giải thuật vẫn là O(n2). 6.2.2. Bµi to¸n nh©n nhiÒu ma trËn 144 1) Bµi to¸n Tính tích các ma trận : A = A1×...× An sao cho số phép tính cần thực hiện là ít nhất (Với giả thiết các phép nhân là thực hiện được). 2) Phân tích bài toán Ta nhận thấy rằng: Do tính kết hợp của phép nhân ma trận, các ma trận Ai có thể nhóm lại theo nhiều cách khác nhau, mà ma trận kết quả A không đổi. Tuy nhiên có sự khác biệt về chi phí khi thay đổi các tổ hợp các ma trận Ai. Dưới đây là thuật toán nhân hai ma trận A và B, các thuộc tính rows và columns là số hàng và số cột của ma trận. MATRIX-MULTIPLY(A, B) { if (columns[A]  rows[B]) return; else for(i=1;i<=rows[A];i++) for(j=1;j<=columns[B];j++) { C[i, j] = 0 for(k=1;k<=columns[A];k++) C[i, j] = C[i, j] + A[i, k] * B[k, j]; } return C; } Ta chỉ có thể nhân hai ma trận A và B khi và chỉ khi nó là phù hợp: số cột của ma trận A phải bằng số hàng của ma trận B. Nếu A là ma trận cỡ m  n và B là ma trận n  p thì ma trận kết quả C có cỡ là m  p. Thời gian để tính C được quyết định bởi số phép tính C[i, j] = C[i, j] + A[i, k] * B[k, j], đó là m  n  p. Để minh hoạ cho sự khác nhau về thời gian tính C do cách đặt các cặp dấu ngoặc đơn khác nhau trong phép nhân các ma trận ta xét các ma trận A, B, C, D với các kích thước như sau: 145 A30x1 B1x40 C40x10 D10x25 Hãy tính ma trận tích A×B×C×D Ta sẽ thấy chi phí cho phép nhân các ma trận phụ thuộc vào cách tổ hợp các ma trận qua việc thực hiện nhân các ma trận này theo các thứ tự khác nhau và tính chi phí theo từng cách như sau: Thứ tự Chi phí ((AB)C)D 30×1×40 + 30×40×10 + 30×10×25 = 20700 (A(B(CD)) 40×10×25 + 1×40×25 + 30×1×25 = 11750 (AB)(CD) 30×1×40 + 40×10×25 + 30×40×25 = 41200 A((BC)D) 1×40×10 + 1×10×25 + 30×1×25 = 1400 Hình 6.2. Chi phí theo các cách tổ hợp ma trận 3) Ý tƣởng Ta giải bài toán bằng cách tiếp cận từ dưới lên. Ta sẽ tính toán và luu trữ lời giải tối ưu cho từng phần nhỏ để tránh tính toán lại cho bài toán lớn hơn. Trước hết là cho các bộ 2 ma trận, các bộ 3 ma trận . . . Chẳng hạn, để tính A×B×C ta có thể tính theo các cách : (A×B)×C hoặc A×(B×C). Nên chi phí để tính A×B×C là chi phí tính được từ 2 phần : Phần một là chi phí kq1×C, với kq1 = A×B ( chi phí này đã tính và được lưu trữ) Phần hai là chi phí A × kq2, với kq2 = B×C ( chi phí này đã được lưu trữ) So sánh 2 phần trên và lưu trử chi phí nhỏ hơn. . . 4) Thiết kế thuật toán Mấu chốt là tính chi phí nhân bộ các ma trận : Ai×...×Aj , với 1≤ i < j ≤ n, trong đó các bộ nhỏ hơn đã được tính và lưu trử kết quả. Với một cách tổ hợp các ma trận : Ai×...×Aj = (Ai×...×Ak) × (Ak+1×...×Aj) Chi phí để nhân các ma trận Ai,...,Aj sẽ bằng tổng : Chi phí để nhân Ai×...×Ak ( kq1), chi phí để nhân Ak+1×...×Aj ( kq2), và chi phí kq1×kq2. 146 Nếu gọi Mij là chi phí nhỏ nhất để nhân bộ các ma trận Ai×...×Aj ,1≤ i < j ≤ n thì: * Mik là chi phí nhỏ nhất để nhân bộ các ma trận Ai×...×Ak * Mk+1,j là chi phí nhỏ nhất để nhân bộ các ma trận Ak+1×...×Aj Với ma trận kq1 cỡ di-1×dk và kq2 có cỡ dk×dj , nên chi phí để nhân kq1×kq2 là di-1dkdj. Do đó: M ij = Min {M ik + M k +1, j + d i −1 d k d j };1 ≤ i < j ≤ n M ii = 0 Ta có thể xem M là ma trận tam giác trên : (Mij)1≤i<j≤n . Ta cần tính và làm đầy các phần tử của ma trận này cho đến khi xác định được M1n . Tất cả các phần tử nằm trên đường chéo chính bằng 0. Tính Mij , ta cần biết Mik , Mk+1,j. Ta tính bảng dọc theo các đường chéo bắt đầu từ đường chéo kế trên đường chéo chính và thay đổi về hướng góc phải trên. Ta muốn biết thứ tự tốt nhất để nhân dãy các ma trận (theo nghĩa chi phí nhỏ nhất). Mỗi lần ta xác định được tổ hợp tốt nhất, ta dùng biến k để lưu trữ thứ tự này. Đó là Oij = k, với M ik + M k +1, j + d i −1 d k d j đạt min. Các Mij ta lưu trữ trong mảng 2 chiều M. Các chỉ số k để xác định được Mij ta lưu trữ trong mảng 2 chiều O. Kích thước của các ma trận ta lưu trữ trong mảng 1 chiều d : Ai là ma trận có di-1 hàng , di cột. Thuật toán: Input d = (d0,d1,...,dn); Output M = (Mij) , O = (Oij); MO(d,n,O,M) { for (i = 1; i <= n; i++) M[i][i] = 0; for (diag = 1; diag <= n-1; diag++) for (i = 1; i <= n - diag; i++) i ≤ k ≤ j −1 147 { j = i + diag; csm = i; min = M[i][i]+M[i+1][j]+d[i-1]*d[i]*d[j]; for (k= i; k <= j - 1; k++) if (min > (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j] )) { min= M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]; csm = k; } M[i][j] = min; O[i][j] = csm; } return M[1][n]; } Khi đó dùng hàm sau để xuất thứ tự các tổ hợp nhân ma trận: MOS(i, j, O) { if (i == j) printf(Ai); else { k = O[i][j]; printf("("); MOS(i,k,O); printf("*:); MOS (k+1,j,O); printf(")"); } } Ví dụ 6.1. Thuật toán được minh họa qua phép nhân các ma trận: A1×A2×A3×A4×A5×A6 148 Với kích cỡ của các ma trận là: Ma trận Cỡ A1 30  35 A2 35  15 A3 15  5 A4 5  10 A5 10  20 A6 20  25 Hình 6.3. Kích cỡ các ma trận Để tiện theo dõi ta quay các mảng M và mảng O sao cho đường chéo chính nằm ngang. Hình 6.4. Mảng M Hình 6.5. Mảng O 4 5 2 3 1 6 9.375 11.875 15.750 7.875 0 15.125 1 4.375 7.125 0 2.625 10.500 2 750 8.456 0 5.375 3 0 16.000 3.500 4 0 5.000 5 0 6 A1 A2 A3 A4 A5 A6 i j 4 5 2 3 6 3 3 1 1 3 1 3 3 2 3 2 3 3 3 3 4 5 4 5 5 i j 149 Chỉ có đường chéo chính và tam giác phía trên được dùng trong mảng M và chỉ tam giác phía trên được dùng trong mảng O. Phần tử ở hàng i cột j của mảng M lưu trữ số ít nhất các phép tính để nhân Ai×...×Aj. Chẳng hạn M[2][5]=7125 là số phép tính ít nhất để nhân A2×A3×A4×A5. Như vậy M[1][6] = 15125 là số phép tính ít nhất để nhân A1×A2×A3×A4×A5×A6 Phần tử ở hàng i cột j của mảng 0 lưu trữ chỉ số k ứng với trường hợp phải dùng ít nhất các phép tính để nhân Ai×...×Aj bằng cách kết hợp (Ai×...×Ak)×(Ak+1×...×Aj) Ta có O[1][6] = 3 nên A1×A2×A3×A4×A5×A6 được kết hợp là: (A1×A2×A3)×(A4×A5×A6) Ta có O[1][3] = 1 nên (A1×A2×A3) được kết hợp là: A1×(A2×A3) Ta có O[4][6] = 5 nên (A4×A5×A6) được kết hợp là: (A4×A5)×A6 Và như vậy số phếp tính phải thực hiện ít nhất khi nhân A1×A2×A3×A4×A5×A6 là nhân theo thứ tự: (A1×(A2×A3))×((A4×A5)×A6) 5) Độ phức tạp tính toán của thuật toán Trong thuật toán ta coi phép toán tích cực là phép toán so sánh: min > (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j] Phép toán này nằm trong 3 vòng for lồng nhau, mỗi vòng for có số lần thực hiện tối đa là n-1. Do vậy số lần thực hiện tối đa phép toán tích cực đó là (n-1)(n- 1)(n-1). Từ đó dễ thấy độ phức tạp tính toán của thuật toán là O(n3) 6.2.3. Bµi to¸n chiÕc ba l« 1) Bài toán Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi và một giá trị vi. Tất cả các loại đồ vật đều có số lượng không hạn chế. Tìm một cách lựa chọn các đồ vật đựng vào ba lô, chọn các loại đồ vật nào, mỗi loại lấy bao nhiêu sao cho tổng trọng lượng không vượt quá W và tổng giá trị là lớn nhất. (Với giả thiết W, gi, vi là các số nguyên) 2) Thiết kế thuật toán 150 Giả sử X[k,V] là số lượng đồ vật k được chọn, F[k,V] là tổng giá trị của k đồ vật đã được chọn và V là trọng lượng còn lại của ba lô, k = 1..n, V = 1..W. Trong trường hợp đơn giản nhất, khi chỉ có một đồ vật, ta tính được X[1,V] và F[1,V] với mọi V từ 1 đến W như sau: X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1. Giả sử ta đã tính được F[k-1,V], khi có thêm đồ vật thứ k, ta sẽ tính được F[k,V], với mọi V từ 1 đến W. Cách tính như sau: Nếu ta chọn xk đồ vật loại k, thì trọng lượng còn lại của ba lô dành cho k-1 đồ vật từ 1 đến k-1 là U = V-xk*gk và tổng giá trị của k loại đồ vật đã được chọn F[k,V] = F[k-1,U] + xk*vk, với xk thay đổi từ 0 đến yk= V DIV gk và ta sẽ chọn xk sao cho F[k,V] lớn nhất. Ta có công thức truy hồi như sau: X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1. F[k,V] = Max(F[k-1,V-xk*gk] + xk*vk) với xk chạy từ 0 đến V DIV gk. Sau khi xác định được F[k,V] thì X[k,V] là xk ứng với giá trị F[k,V] được chọn trong công thức trên. Để lưu các giá trị trung gian trong quá trình tính F[k,V] theo công thức truy hồi trên, ta sử dụng một bảng gồm n dòng từ 1 đến n, dòng thứ k ứng với đồ vật loại k và W+1 cột từ 0 đến W, cột thứ V ứng với trọng lượng V. Mỗi cột V bao gồm hai cột nhỏ, cột bên trái lưu F[k,V], cột bên phải lưu X[k,V]. Ta sẽ tổ chức hai bảng tách rời là F và X. Ví dụ 6.2. Bài toán cái ba lô với trọng lượng W=9, và 5 loại đồ vật được cho trong bảng sau: Đồ vật Trọng lượng Giá trị 1 3 4 2 4 5 3 5 6 4 2 3 5 1 1 Hình 6.6. Trọng lương và giá trị 5 loại đồ vật Ta có bảng F[k,V] và X[k,V] như sau, trong đó mỗi cột V có hai cột con, cột 151 bên trái ghi F[k,V] và cột bên phải ghi X[k,V]. 0 1 2 3 4 5 6 7 8 9 1 0 0 0 0 0 0 4 1 4 1 4 1 8 2 8 2 8 2 12 3 2 0 0 0 0 0 0 4 0 5 1 5 1 8 0 9 1 10 2 12 0 3 0 0 0 0 0 0 4 0 5 0 6 1 8 0 9 0 10 0 12 0 4 0 0 0 0 3 1 4 0 6 2 7 1 9 3 10 2 12 4 13 3 5 0 0 1 1 3 0 4 0 6 0 7 0 9 0 10 0 12 0 13 0 Hình 6.6. Bảng F[k,V] và X[k,V] Trong bảng trên, việc điền giá trị cho dòng 1 rất đơn giản bằng cách sử dụng công thức: X[1,V] = V DIV g1 và F[1,V] = X[1,V] * v1. Từ dòng 2 đến dòng 5, phải sử dụng công thức truy hồi: F[k,V] = Max(F[k-1,V-xk*gk + xk*vk) với xk chạy từ 0 đến V DIV gk Chẳng hạn, để tính F[2,7], ta có xk chạy từ 0 đến V DIV gk, trong trường hợp này là xk chạy từ 0 đến 7 DIV 4, tức xk có hai giá trị 0 và 1. Khi đó F[2,7] = Max(F[2-1, 7-0*4] + 0*5, F[2-1,7-1*4] + 1*5) = Max(F[1,7], F[1,3] + 5) = Max(8, 4+5) = 9. F[2,7] = 9 ứng với xk = 1 do đó X[2,7] = 1. Vấn đề bây giờ là cần phải tra trong bảng trên để xác định phương án. Khởi đầu, trọng lượng còn lại của ba lô V = W. Nếu X[k,V] > 0 thì chọn X[k,V] đồ vật loại k. Tính lại V = V - X[k,V] * gk. Chẳng hạn, trong bảng trên, ta sẽ xét các đồ vật từ 5 đến 1. Khởi đầu V = W = 9. Với k = 5, vì X[5,9] = 0 nên ta không chọn đồ vật loại 5. Với k = 4, vì X[4,9] = 3 nên ta chọn 3 đồ vật loại 4. Tính lại V = 9 – 3 * 2 = 3. Với k = 3, vì X[3,3] = 0 nên ta không chọn đồ vật loại 3. 152 Với k = 2, vì X[2,3] = 0 nên ta không chọn đồ vật loại 2. Với k = 1, vì X[1,3] = 1 nên ta chọn 1 đồ vật loại 1. Tính lại V = 3 – 1 * 3 = 0. Vậy tổng trọng lượng các vật được chọn là 3 * 2 + 1 * 3 = 9. Tổng giá trị các vật được chọn là 3 * 3 + 1 * 4 = 13. Giải thuật thiết kế theo kĩ thuật quy hoạch động như sau: Tổ chức dữ liệu: - Mỗi đồ vật được tổ chức là một cấu trúc gồm các trường: + Ten: tên đồ vật + Trong_luong: Trọng lượng đồ vật + Gia_tri: Giá trị đồ vật + Phuong_an: lưu trữ số lượng đồ vật theo phương án - Các đồ vật được lưu trữ trong một mảng - Bảng được biểu diễn bằng một mảng hai chiều các số nguyên để lưu trữ các giá trị F[k,v] và X[k,v] Hàm Tao_bang nhận vào ds_vat là danh sách các vật, n là số lượng các loại vật, W là trọng lượng của ba lô. F và X là hai tham số thuộc kiểu Bang và được truyền bằng tham chiếu để nhận lại hai bảng F và X do hàm tạo ra. Tao_Bang (ds_vat, n,W, F, X) { for(v=0;v<=W;v++) { X[1, v] = v/ds_vat[1].trong_luong; F[1, v] = X[1, v] * ds_vat[1].gia_tri; } for(k=2;k<=n;k++) { X[k, 0] = 0; F[1, 0] = 0; for(v=1;v<=W;v++) 153 { FMax = F[k-1, v] ; XMax = 0; yk = v/ds_vat[k].trong_luong; for(xk=1;xk<=yk;xk++) if(F[k-1,v-xk*ds_vat[k].trong_luong]+xk*ds_vat[k].gia_tri>FMax) { FMax=F[k-1,v-k*ds_vat[k].trong_luong]+xk*ds_vat[k].gia_tri; XMax= xk; } F[k, v] = FMax; X[k, v] = XMax; } } } Hàm Tra_bang nhận vào hai bảng F và X; n là số lượng các loại đồ vật, W là trọng lượng của ba lô và trả ra ds_vat là một danh sách đồ vật đã được xác định phương án. Tra_Bang(n,W, F,X) { v = W; for(k=n;k>=1;k--) if( X[k,v] > 0) { ds_vat[k].Phuong_an = X[k,v]; v = v - X[k, v] * ds_vat[k].trong_luong; } } 3) Độ phức tạp tính toán của thuật toán Trong thuật toán ta coi phép toán tích cực là phép toán so sánh: 154 F[k-1,v-xk*ds_vat[k].trong_luong]+xk*ds_vat[k].gia_tri>FMax Phép toán này nằm trong 3 vòng for lồng nhau. Vòng for thứ nhất có số lần thực hiện tối đa là n-1. Vòng for thứ hai số lần thực hiện tối đa là W. Vòng for thứ ba ta gọi trọng lượng nhỏ nhất trong n vật là g thì số lần thực hiện tối đa của vòng for này là [W/g]=m . Từ đó nhận thấy độ phức tạp tính toán của thuật toán là O(n.W.m) 6.2.4. Xâu con chung dài nhất 1) Bài toán Cho hai xâu ký tự X = và Y = chỉ chứa các chữ cái la tinh. Ta gọi Z = là xâu con chung của X và Y nếu Z chứa các ký tự có mặt trong cả 2 xâu X và Y; trong đó thứ tự trước sau của các ký tự trong xâu Z cũng là thứ tự trước sau của các ký tự trong hai xâu X và Y ban đầu. Bài toán đặt ra với hai xâu X và Y ban đầu hãy xác định xâu con chung Z có độ dài lớn nhất. Rõ ràng xâu con Z chính là xâu X và xâu Y sau khi xoá đi một số ký tự nào đó trong X và trong Y. Bài toán này có thể giải quyết một cách hiệu quả thông qua phương pháp quy hoạch động như sau: 2) Phân tích bài toán Một cách tiếp cận vấn đề đơn giản nhất để giải quyết bài toán xâu con chung dài nhất đó là liệt kê tất cả các xâu con của X và kiểm tra mỗi xâu con này có phải là xâu con của Y hay không; đồng thời theo dõi xâu con dài nhất tìm thấy. Mỗi xâu con của X tương ứng với một tập hợp con gồm các chỉ số {1,2, ..., m} của X – với m là độ dài của xâu X. Như vậy ta sẽ có 2m xâu con của X (kể cả xâu rỗng), do đó việc giải bài toán này sẽ có độ phức tạp với thời gian mũ. Điều này khiến nó trở lên không hiệu quả trong thực tiễn với các xâu dài (m lớn). Tuy nhiên, bài toán xâu con chung dài nhất có một tính chất cấu trúc con tối ưu. Để dễ hiểu ta đưa ra định nghĩa về tiền tố như sau: Tiền tố thứ i của X, với i = 0, 1, ..., m là Xi = ; thì lớp tự nhiên của bài toán con tương ứng với các cặp tiền tố của hai xâu con đầu vào. Chẳng hạn: X = thì X5 = , còn X0 là rỗng. 155 Tính chất cấu trúc con tối ưu của một xâu con chung dài nhất được thể hiện rất rõ thông qua khẳng định sau: Cho X = và Y = là các xâu ký tự, và cho Z = <z1, z2, ..., zk> là một xâu con chung dài nhất bất kỳ của X và Y. Khi đó ta có: - Nếu xm = yn thì zk = xm = yn và Zk-1 là một xâu con chung dài nhất của Xm-1 và Yn-1 (1) - Nếu xm  yn thì zk  xm hàm ý Z là xâu con chung dài nhất của Xm-1 và Y, (2) - Nếu xm  yn thì zk  yn hàm ý Z là xâu con chung dài nhất của X và Yn-1. (3) Thật vậy: (1) Với xm = yn và Z là xâu con chung dài nhất của X, Y; giả sử zk  xm thì ta có thể nối xm = yn vào Z để có được một xâu con chung của X và Y có chiều dài k+1, điều này mâu thuẫn với giả thiết cho rằng Z là xâu con chung dài nhất của X và Y. Như vậy, ta phải có zk = xm = yn. Mặt khác ta nhận thấy, tiền tố Zk-1 là một xâu con chung có chiều dài k-1 của Xm-1 và Yn-1; và ta phải chứng minh Zk-1 là một xâu con chung dài nhất của Xm-1 và Yn-1. Thật vậy, giả sử có một xâu con chung T của Xm-1 và Yn-1 có chiều dài lớn hơn k-1, khi đó việc thêm vào giá trị xm = yn sẽ khiến cho T trở thành xâu con chung của X và Y có chiều dài lớn hơn k, điều này mâu thuẫn với giả thiết Z chỉ có độ dài k là xâu con chung dài nhất. Do đó ta suy ra điều phải chứng minh. (2). Với giả thiết là xm  yn và zk  xm, khi đó ta phải chứng minh Z là một xâu con chung dài nhất của Xm-1 và Y. Thật vậy, trước hết ta nhận thấy Z sẽ là xâu con chung của Xm-1 và Y; điều này có được là từ giả thiết ta suy ra việc xoá đi phần tử xm không làm ảnh hưởng tính chất xâu con chung của Z. Mặt khác, giả sử có một xâu con chung T của Xm-1 và Y có chiều dài lớn hơn k, khi đó T cũng sẽ là một xâu con chung của X và Y, và điều này mâu thuẫn với giả thiết Z là xâu con chung dài nhất của X và Y (độ dài của Z chỉ là k). Đây là điều phải chứng minh. (3) được chứng minh tương tự như 2. Khẳng định trên cho thấy một xâu con chung dài nhất của hai dãy chứa trong nó một xâu con chung dài nhất của thành phần là hai tiền tố của hai dãy ban đầu. Như vậy bài toán xâu con chung dài nhất có một tính chất cấu trúc con tối ưu. Một 156 giải pháp đệ quy cũng có tính chất các bài toán con phủ chồng như sẽ xem xét dưới đây. 3) Thiết kế thuật toán Khẳng định trên cho ta một ý tưởng chia bài toán xâu con chung dài nhất của hai xâu X = và Y = thành hai bài toán con. Nếu xm = yn thì ta giải bài toán con tìm một xâu con chung của Xm-1 và Yn-1. Việc nối thêm xm = yn vào xâu con chung dài nhất này sẽ cho ra xâu con chung dài nhất của X và Y. Ngược lại nếu xm  yn thì ta giải quyết hai bài toán con: Bài toán 1: Tìm xâu con chung dài nhất của Xm-1 và Y. Bài toán 2: Tìm xâu con chung dài nhất của Yn-1 và X. Sau đó so sánh 2 xâu con chung dài nhất của 2 bài toán này, xâu nào có độ dài lớn hơn thì nó là xâu con chung dài nhất của X và Y. Ta dễ dàng nhận thấy tính chất các bài toán con phủ chồng trong bài toán tìm xâu con chung dài nhất. Để tìm một xâu con chung dài nhất của X và Y, ta có thể cần phải tìm các xâu con chung dài nhất của X và Yn-1 và của Xm-1 và Y. Nhưng mỗi bài toán con này lại chứa các bài toán con tìm xâu con chung dài nhất của Xm-1 và Yn-1. Như vậy giải pháp đệ quy của ta đối với bài toán xâu con chung dài nhất có liên quan đến việc thiết lập một phương trình đệ quy cho mức hao phí của một giải pháp tối ưu. Ta định nghĩa c[i,j] là chiều dài của một xâu con chung dài nhất của dãy Xi và Yj. Nếu i = 0 hoặc j = 0 (tồn tại một trong các xâu có chiều dài bằng 0) thì xâu con chung dài nhất có chiều dài bằng 0. Cấu trúc con tối ưu của bài toán xâu con chung dài nhất cho phương trình đệ quy sau: 0 nếu i = 0 hoặc j = 0, c[i,j] = c[i-1,j-1] + 1 nếu i, j > 0 và xi = yj, (*) max (c[i,j-1], c[i-1,j]) nếu i,j>0 và xi  yj. Dựa trên phương trình (*) ta có thể dễ dàng viết một thuật toán đệ quy thời gian mũ để tính toán chiều dài của một xâu con chung dài nhất. Tuy nhiên ta sẽ dùng kỹ thuật quy hoạch động để tính toán các giải pháp từ dưới lên. Hàm DDXCCDN (độ dài xâu con chung dài nhất) nhận hai dãy X = <x1, x2, ..., xm>; và Y = làm dữ liệu đầu vào. 157 Mỗi giá trị c[i,j] trong bảng c[0..m, 0..n] được tính toán theo thứ tự chính là hàng; nghĩa là hàng đầu tiên của c được điền từ trái qua phải, sau đó là hàng thứ 2 .v.v. Song song với bảng c, ta tính toán một bảng b[0..m, 0..n] có giá trị bảng tương ứng với giải pháp của bài toán con tối ưu c[i,j]. Hàm trả về các bảng b và c; trong đó c[m,n] chứa chiều dài của một xâu con chung dài nhất của X, Y. - Xây dựng bảng c[m,n]; m = length(X), n = length(Y) trong đó: + c[i,j] chứa độ dài xâu con chung dài nhất của Xi và Yj; 0  i  m, 0  j  n; với c[i,j] được tính theo công thức (*); + c[m,n] chính là chiều dài của xâu con chung dài nhất. Ta hình dung bảng c[m,n] được lấy gốc toạ độ c[0,0] là góc trên cùng, bên trái; còn trục tung và trục hoành tương ứng với X và Y. - Xây dựng bảng b[i,j] tương ứng để truy vết của xâu con chung dài nhất bắt đầu từ b[m,n]; trong đó b[i,j] được tính như sau: + Nếu xi = yj đặt b[i,j] = 0; điều này có nghĩa đây chính là một thành phần của xâu con chung dài nhất khi ta lần ngược từ dưới lên; {b[i,j] = 0 biểu thị hướng truy vết đi chéo lên của bảng c tại vị trí (i,j)}; + Nếu xi  yj và c[i-1,j]  c[i,j-1] đặt b[i,j] = 1; điều này khẳng định xâu con chung dài nhất của Xi, Yj chính là xâu con chung dài nhất của Xi-1, Yj; hay nói cách khác nếu xi-1 = yj thì đây chính là một thành phần của xâu con chung dài nhất; {b[i,j] = 1 biểu thị hướng truy vết đi lên thẳng đứng của bảng c tại vị trí (i,j)}; + Nếu xi  yj và c[i-1,j]  c[i,j-1] thì b[i,j] = -1; điều này khẳng định xâu con chung dài nhất của Xi, Yj chính là xâu con chung dài nhất của Xi, Yj-1; hay nói cách khác nếu xi = yj-1 thì đây chính là một thành phần của xâu con chung dài nhất; {b[i,j] = -1biểu thị hướng truy vết đi ngang sang trái của bảng c tại vị trí (i,j)} - Từ b[m,n] lần ngược lên trên đến b[0,0] tìm được xâu con chung dài nhất theo thứ tự đảo ngược lại của các vị trí; - Đảo ngược lại xâu con tìm được ta sẽ được xâu con chung dài nhất cần tìm. Thuật toán Xaucon(X,Y) /* Hàm này tính toán 2 bảng c và b từ dữ liệu đầu vào là hai xâu X và Y */ { m=length(X); n=length(Y); 158 for( i= 0; i<=m;i++) c[i,0]=0; for( i= 0; i<=n;i++) c[0,i]=0; for( i= 1; i<=m;i++) for( j= 1; j<=n;j++) if (X[i] == Y[j]) { c[i,j]= c[i-1,j-1]+1; b[i,j]= 0 ; } else if (c[i-1,j]  c[i,j-1]) { c[i,j]:= c[i-1,j]; b[i,j]:= 1; } else { c[i,j]:= c[i,j-1]; b[i,j]:= -1; } } In ra xâu con chung dài nhất Sau khi đã xây dựng được các bảng b và c, ta sẽ sử dụng các bảng này để in ra xâu con chung dài nhất. Bắt đầu từ b[m,n] trong bảng b ta tiến hành dò ngược lên trên. Với một b[i,j] bất kỳ (0  i  m, 0  j  n) ta chia làm 3 trường hợp: - Nếu b[i,j] = -1 và (i > 0 và j > 0) thì ta truy vết ngang sang trái của bảng c, tức là xét bài toán con ứng với Xi-1 và Yj. - Nếu b[i,j] = 0 và (i > 0 và j > 0) thì xi = yj = zc[i,j] chính là một thành phần của xâu con chung dài nhất; xét bài toán con ứng với Xi-1, Yj-1 và in ra giá trị đó. 159 - Nếu b[i,j] = 1 và (i > 0 và j > 0) thì ta truy vết lên thẳng đứng của bảng c, tức là xét bài toán con ứng với Xi và Yj-1. Như vậy sau khi dò ngược lên trên ta in ra được xâu con chung dài nhất của X và Y. Thuật toán In_XCCDN in ra xâu con chung dài nhất In_XCCDN(b,c,i,j) { if ((i == 0)||(j == 0) return; if (b[i,j] == 0) { In_XCCDN(b,c,i-1,j-1) printf(X[i]) } else { if (b[i,j] == 1) In_XCCDN(b,c,i-1,j) else In_XCCDN(b,c,i,j-1); } Ví dụ 6.3. Cho xâu X=ABCDAD; xâu Y=BDCABAD; Tìm xâu con chung dài nhất Z; ta có thể mô tả các bước của thuật toán trong các bảng sau j 0 1 2 3 4 5 6 7 i yj B D C A B A D 0 xi 0 0 0 0 0 0 0 0 1 A 0 0 0 0 1 1 1 1 2 B 0 1 1 1 1 2 2 2 3 C 0 1 1 2 2 2 2 2 4 D 0 1 2 2 2 2 2 3 5 A 0 1 2 2 3 3 3 3 6 D 0 1 2 2 3 3 3 4 Hình 6.8. Bảng c 160 1 2 3 4 5 6 7 1 1 1 1 0 -1 -1 -1 2 0 -1 -1 1 0 -1 -1 3 1 1 0 -1 1 1 1 4 1 0 1 1 1 1 0 5 1 1 1 0 -1 0 1 6 1 1 1 1 1 1 0 Hình 6.9. Bảng b Trong bảng c các phần tử của dòng ứng với i=0 và cột ứng với j=0 đều có giá trị 0 do các lệnh: for( i= 0; i<=m;i++) c[i,0]=0; for( i= 0; i<=n;i++) c[0,i]=0; Từ hàng 1 đến hàng 6 các phần tử của các bảng b và c được xác định do các lệnh: for( i= 1; i<=m;i++) for( j= 1; j<=n;j++) if (X[i] == Y[j]) { c[i,j]= c[i-1,j-1]+1; b[i,j]= 0 ; } else if (c[i-1,j]  c[i,j-1]) { c[i,j]:= c[i-1,j]; b[i,j]:= 1; 161 } else { c[i,j]:= c[i,j-1]; b[i,j]:= -1; } Việc in ra xâu con chung dài nhất được thực hiện qua hàm In_XCCDN(b,c,6,7). Quá trình tìm (và in ra) xâu con chung dài nhất được minh họa trong các bảng qua các ô bôi đen, theo đó xâu con chung dài nhất được in ra sẽ là: ABAD 3) Đánh giá độ phức tạp của thuật toán Đối với thuật toán Xaucon(X,Y) phép toán tích cực có thể coi là phép so sánh X[i] == Y[j], phép này nằm trong hai vòng for lồng nhau là for( i= 1; i<=m;i++) for( j= 1; j<=n;j++) Do đó độ phức tạp của thuật toán là O(mn). Đối với In_XCCDN(b,c,i,j) gọi đệ quy lẫn nhau với đầu vào ban đầu là bộ (b,c,i=m, j=n). Nhưng dù thế nào thì ở bước 2 hoặc bước 3 ít nhất giá trị của i hoặc của j (hoặc của cả 2) bị giảm đi 1. Thuật toán dừng khi i=0 hoặc j=0; do đó trong trường hợp xấu nhất thuật toán cũng chỉ mất m+n bước, hay nói cách khác độ phức tạp của thuật toán là O(m+n). Sau khi gọi Xaucon(X,Y) sẽ gọi In_XCCDN(b,c,i,j). Do vậy độ phức tạp tính toán của thuật toán tìm xâu con chung dài nhất của hai xâu sẽ là O(mn). * Nhận xét Đối với hai thuật toán Xaucon và In_XCCDN ở trên ta phải sử dụng thêm một bảng phụ b[0..m,0..n] để truy vết khi xác định một xâu con chung dài nhất. Tuy nhiên việc xác định một xâu con chung dài nhất này chỉ cần dựa vào thông tin của bảng c; hay nói cách khác từ c[m,n] truy ngược lên đến c[0,0], tại mỗi vị trí c[i,j] ta có thể xác định được bước truy vết tiếp theo chỉ cần dựa vào bộ ba giá trị {c[i,j], c[i- 1,j], và c[i,j-1]} mà không cần xem xét bảng phụ b. Chính vì vậy ta có thể cải thiện không gian bộ nhớ khi bỏ qua bảng b. Khi đó các hàm Xaucon và In_XCCDN sẽ có sự thay đổi như sau: Xaucon(X,Y) 162 /* Hàm này tính toán bảng c từ dữ liệu đầu vào là hai xâu X và Y */ { m=length(X); n=length(Y); for( i= 0; i<=m;i++) c[i,0]=0; for( i= 0; i<=n;i++) c[0,i]=0; for( i= 1; i<=m;i++) for( j= 1; j<=n;j++) if (X[i] == Y[j]) c[i,j]= c[i-1,j-1]+1; else if (c[i-1,j]  c[i,j-1]) c[i,j]:= c[i-1,j]; else c[i,j]:= c[i,j-1]; } In_XCCDN(c,i,j) /* Đưa ra xâu con chung dài nhất*/ { z= ’’; i= m; j= n; While ((i>0) && (j>0)) if (X[i] == Y[j]) { z= z + X[i]; i= i-1; 163 j= j-1; } else if (c[i-1,j]  c[i,j-1]) i= i-1; else j:= j-1; return(Z); } 164 BÀI TẬP CHƢƠNG 6 1. Cho hai dãy số nguyên X = 12, 5, 50, 35, 11, 45, 60 Y = 6, 5, 40, 35, 21, 55, 45, 60, 9 Hãy mô phỏng quá trình áp dụng thuật toán tìm xâu con chung dài nhất để tìm dãy con chung dài nhất của X và Y. 2. Bài toán chia quà Minh và Nhật là hai anh em sinh đôi, trong ngày sinh nhật, hai anh em nhận được n món quà. Trên món quà i có ghi giá tiền x[i]. Hai anh em quyết định phân chia n món quà thành hai phần, mỗi người được sở hữu một phần. Hãy sử dụng kỹ thuật quy hoạch động phân chia sao cho chênh lệch giá trị của hai phần quà là ít nhất. Hướng dẫn: - Gọi t là tổng giá trị của n món quà : t =  x[i] - Gọi m là nửa tổng giá trị của n món quà: m = t/2 - Phải tìm tập y {1,2, ... ,n} sao cho  x[i] với iy gần m nhất - Để diễn đạt phần tử thứ i của tập {1,2,... ,n} thuộc tập y, ta sẽ ký hiệu y[i]=1, ngược lại ta ký hiệu y[i]=0 - Gọi f[i,j] là tổng giá trị lớn nhất trong trường hợp có i món quà và giá trị tối đa là j (nghĩa là tổng giá trị của các món quà được chọn không quá j)  f[n,m] là giá trị cần tìm. - Xây dựng được công thức như sau: f[i,0]=0, i =1..n và f[0,j]=0, j =1..m f[i-1,j-x[i]]+x[i] (món quà thứ i được chọn) f[i,j] = max f[i-1,j] (món quà thứ i không được chọn) i =1..n và j =1..m Thuật toán: For i:=1 to n do For j:=1 to m do Nếu x[i]j thì 165 f[i,j]:= max(f[i-1,j - x[i]] + x[i] , f[i-1,j]) Nếu không thì f[i,j]:= f[i-1,j] Đánh giá độ phức tạp của thuật toán: 0(n.m) 3. Bài toán đường đi của người giao hàng Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác là xác định được. Giả thiết rằng mỗi thành phố đều có đường đi đến các thành phố còn lại. Khoảng cách giữa hai thành phố có thể là khoảng cách địa lý, có thể là cước phí di chuyển hoặc thời gian di chuyển. Ta gọi chung là độ dài. Dùng kỹ thuật quy hoạch động tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất. Hướng dẫn: n thành phố được đánh số từ 1 đến n. Đường đi từ thành phố i đến thành phố j xem như là cung đi từ đỉnh i đến đỉnh j của đơn đồ thị có hướng. Ðộ dài từ i đến j là trọng số m(i,j) của cung (i,j). Vậy bài toán trên có thể xem là tìm một chu trình xuất phát từ đỉnh i nào đó của đơn đồ thị có hướng có trọng số G=(V,E), đi qua mỗi đỉnh đúng 1 lần sao cho có trọng số nhỏ nhất. Giả sử có một chu trình thỏa yêu cầu bài toán và bắt đầu từ đỉnh 1 về đỉnh 1. Khi đó chu trình này bao gồm cung (1,k), với k  V\{1}, và đường đi từ k đến 1, đi qua mỗi đỉnh còn lại thuộc V\{1,k}, mỗi đỉnh đúng 1 lần. Nếu chu trình này có trọng số nhỏ nhất (tối ưu ), thì khi đó đường đi từ k đến 1 cũng có trọng số nhỏ nhất (tối ưu ). Biểu diễn G bằng ma trận kề : C = cij (1 i,jn) như sau: cij = m(i,j) nếu (i,j)E cij = 0 nếu i=j cij =  nếu (i,j)E Xét tập S  V\{1} và i(V\{1})\S. Ta gọi : d(i,S) = Trọng số của đường đi ngắn nhất đi từ đỉnh i đến đỉnh 1 đi qua mỗi đỉnh trong S đúng 1 lần. Vậy với 2 ≤ i ≤ n thì: 166 - Nếu S = , ta có : d(i, ) = Ci1 ; - Nếu S   thì : d(i, S ) = Min{Cik + d(k, S \{k})} Khi đó, trọng số của chu trình ngắn nhất đi từ 1 đến 1 sẽ là : d (1, V \ {1}) = Min{C1k + d (k ,V \{1, k})} Để tính d(1,V \ {1}) ta cần có d(k ,V \ {1, k}) , với 2 k n. Tổng quát, ta cần tính các d(i, S ) , S V\{1} và i (V\{1})\S . Đầu tiên ta tính và lưu trữ d(i, ) ; d(i, S) với S chỉ có 1 phần tử ; d(i, S) với S có 2 phần tử , . . .cho đến khi tính được các d(k, V\{1, k}) với 2 ≤ k ≤ n. Input : C Output : d (1,V \ {1}) Mô tả: Bước 0 : Khởi tạo : d(i, ) = Ci1 ; 2 ≤ i ≤ n Bước 1 : Với S ? V\{1} và |S| = 1; ∀ i  1 và iS : d(i, S ) = Min{Cik + d(k, S\{k})} với kS ..... Bước n-2: Với S ? V\{1} và |S| = n-2; ∀ i1 và i S : d (i, S ) = Min{C ik + d (k , S \ {k})} với kS Bước n-1 : d(1, V\{1}) = Min{C1k + d(k ,V\{1, k})} với 2 ≤ k ≤ n Ðánh giá độ phức tạp tính toán: Ta xét thời gian thực hiện T(n) của d(i,S): i có n-1 lựa chọn. Với mọi i =2,..,n : Số các tập S có k phần tử khác 1,i là C k 2n Do dĩ 2n 2n 0k k 2n 2)1n()1n()n(T C      Mặt khác khi tính d(i,S) với S gồm k phần tử, ta cần thực hiện k-1 phép so sánh để xác định min. Nên thời gian thực hiện của thuật toán là O(n22n) 167 4. Dãy con tăng dài nhất Cho dãy số nguyên A = a1, a2, .., an. Áp dụng kỹ thuật quy hoạch động chọn ra một dãy con tăng B của A (bao gồm một số các phần tử trong A nhưng vẫn giữ nguyên thứ tự) có độ dài lớn nhất. Ví dụ : A = ( 1, 2, 3, 4, 5, 9, 10, 5, 6, 7, 8) => B = (1, 2, 3, 4, 5, 6, 7, 8) Hướng dẫn: Ta thêm vào dãy ban đầu 2 phần tử : A[0] = - và A[n+1] =  làm hai đầu mút. Vậy dãy con tăng dài nhất sẽ bắt đầu là A[0] và kết thúc là A[n+1]. Với i : 0<=i<n+1 thì ta gọi Fa[i] là độ dài của dãy con bắt đầu bởi A[i]. Điều đó có nghĩa là Fa[n+1] là độ dài của dãy con bắt đầu từ n+1. Dãy này chỉ có 1 phần tử nên có độ dài là 1 Fa[n+1] = 1. Ta sẽ bắt đầu xét các phần tử A[i] với i từ n đến 0 ta tính Fa[i] dựa trên các Fa[i+1],Fa[i+2],,Fa[n+1] đã tính được trước đó. Dãy con đơn điệu tăng dài nhất bắt đầu từ A[i] có thể được cập nhật thêm A[i] theo cách như sau : Xét tất cả các chỉ số j trong khoảng i+1 đến n+1 mà A[j] >A[i], ta chọn ra chỉ số jmax có Fa[jmax] lớn nhất. Và lúc này thì : Fa[i] = Fa[jmax] +1. Để có thể lần lại được kết quả thì khi gán Fa[i]= Fa[jmax]+ 1, ta cũng gán T[i] = jmax để biết rằng dãy con bắt đầu từ A[i] thì sẽ có phần tử thứ 2 kế tiếp là A[jmax] Thuật toán daytang(A) { A[0] = -; A[n+1]= ; Fa[n+1]=1; for(i=n;i>=0;i--) { Jmax = n+1; for(j=i+1;j<=n+1;j++) if ((A[j] > A[i]) && (Fa[j]>Fa[jmax])) jmax=j; Fa[i]:=Fa[jmax]+1; 168 T[i]:= jmax; } } Việc in ra dãy con tăng dài nhất được thực hiện bởi hàm: hienthi(A,T) { I=T[0]; While (i n+1) { printf(A[i]); I=T[i]; } } 5. Giả sử có hai đội A và B tham gia một trận thi đấu thể thao, đội nào thắng trước n hiệp thì sẽ thắng cuộc. Chẳng hạn một trận thi đấu bóng chuyền 5 hiệp, đội nào thắng trước 3 hiệp thì sẽ thắng cuộc. Giả sử hai đội ngang tài ngang sức. Đội A cần thắng thêm i hiệp để thắng cuộc còn đội B thì cần thắng thêm j hiệp nữa. Gọi P(i,j) là xác suất để đội A cần i hiệp nữa để chiến thắng, B cần j hiệp. Dĩ nhiên i,j đều là các số nguyên không âm. Ðể tính P(i,j) ta thấy rằng nếu i=0, tức là đội A đã thắng nên P(0,j) = 1. Tương tự nếu j=0, tức là đội B đã thắng nên P(i,0) = 0. Nếu i và j đều lớn hơn không thì ít nhất còn một hiệp nữa phải đấu và hai đội có khả năng 5 ăn, 5 thua trong hiệp này. Như vậy P(i,j) là trung bình cộng của P(i-1,j) và P(i,j-1). Trong đó P(i-1,j) là xác suất để đội A thắng cuộc nếu thắng hiệp đó và P(i,j-1) là xác suất để A thắng cuộc nếu nó thua hiệp đó. Tóm lại ta có công thức tính P(i,j) như sau: P(i,j) =1Nếu i = 0 P(i,j) =0Nếu j = 0 P(i,j) =(P(i-1,j) + P(i,j-1))/2Nếu i > 0 và j > 0 a. Viết một hàm đệ quy để tính P(i,j). b. Dùng kĩ thuật quy hoạch động để viết hàm tính P(i,j). 169 6. Mét con tµu cã träng l-îng W. Cã n mÆt hµng ®-îc ®¸nh sè tõ 1, 2, , n. Mçi mÆt hµng lo¹i i cã sè l-îng lµ qi, khèi l-îng lµ ai vµ gi¸ trÞ lµ ci. Dïng kü thuËt quy ho¹ch ®éng t×m c¸ch xÕp hµng ho¸ lªn tµu sao cho tæng gi¸ trÞ ®¹t ®-îc lµ lín nhÊt. H-íng dÉn: Gọi xi là số lượng hàng hoá loại i (i = 1 .. n ) Bước 1: Tìm cơ sở của phương án hay chính là tìm điều kiện dừng của bài toán. Xét trường hợp có 1 mặt hàng (n=1, có số lượng là q1, có khối lượng là a1, có giá trị là c1. - Cần xếp hàng lên tàu cho đến khi không xếp được nữa thì thôi (tổng khối lượng của hàng lớn hơn trọng tải của tàu), Vậy số mặt hàng xếp lên tàu có tổng khối lượng bao giờ cũng nhỏ hơn hoặc bằng trọng tải của tàu do vậy số lượng hàng hoá xếp được lên tàu sẽ là x1=W div a1 - Số lượng mặt hàng q1 vẫn còn đủ (x1<= q1 ) thì giá trị đạt được là x1*c1 . - Số lượng mặt hàng q1 hết ( x1> q1 ) thì giá trị đạt được là q1*c1. Bước 2: Tìm công thức truy hồi: Xét trường hợp có n mặt hàng (n >= 1, có số lượng là qi, có khối lượng là ai, có giá trị là ci. *) Gọi f(k,v) là giá trị lớn nhất của tàu với k loại mặt hàng 1<= k <= n và v khối lượng (1 <= v <= W) *) Theo bước 1 ta có: + x1 = W div a1. + Nếu x1 > q1 thì f(1,v) = q1*c1. + Nếu x1<= q1 thì f(1,v) = x1*c1. *) Giả sử đã tính được f(l,m) với 1<= l<= k và 1<= m <= v + cần tính f(k,v) với 1<= k <= n và 1 <= v <= W + Gọi yk = v div ak ta có f(k,v) = max {f(k-1,m) + xk*ck} (Giá trị hàng hoá trên tàu tăng lên một lượng xk*ck) + Trong đó max được lấy: Nếu yk <= qk với xk = 1, 2, , yk Nếu yk > qk với xk = 1, 2, , qk + Giá trị lớn nhất của tàu sẽ là f(n,W). 170 + u = v - xk*ak (Trọng tải của tàu phải giảm xuống một lượng xk*ak) Bước 3: Lập bảng phương án - Dùng mảng hai chiều KQ[1..n, 1..W] để lưu bảng phương án trung gian - Một trường chứa giá trị tàu f(k, v) đạt được tại thời điểm k mà trong công thức truy hồi f(k,v) = max {f(k-1,m) + xk*ck} đạt tới max. - Một trường chứa số lượng mặt hàng xk. Bước 4: Tính nghiệm của bài toán con thông qua nghiệm của bài toán nhỏ hơn Sử dụng công thức truy hồi ở bước 3 để tính. Bước 5: Xây dựng nghiệm của bài toán dựa trên bảng phương án (ma trận KQ) - Từ công thức truy hồi f(k,v) = max {f(k-1,m) + xk*ck} giá trị của bảng KQ có thể tính lần lượt theo dòng 1, 2, , n. - Từ mảng KQ đã làm đầy ta xác định giá trị x và f(n,W) + Ta thấy ô KQ[n,W] chứa f(n,W) và xn. Như vậy xác định được giá trị của f(n,W) và xn. + Tính v = W – xn*an + Tìm đến ô KQ[n-1,v] biết được f(n,W) và xn-1 + Tiếp tục quá trình trên ta tìm được xn-2, xn-3, , x1. + Không tìm xi khi giá trị v = 0. + Các xi tìm thấy lưu vào mảng X. Đánh giá thuật độ phức tạp tính toán: O(n2) 171 PHỤ LỤC 1. Cài đặt thuật toán quy hoạch động giải bài toán chiếc ba lô /* Doc du lieu tu file Balo.txt: Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m), n dong tiep theo ghi trong luong va gia tri cua vat*/ #define max 100 int v[max], w[max]; int n, W; int L[max][max]; int vmax; int pa[max]; void DocDL() { FILE *f; f = fopen("BaLo.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } fscanf(f, "%d", &n); fscanf(f, "%d", &W); for(int i=1; i<=n; i++) { fscanf(f, "%d", &w[i]); fscanf(f, "%d", &v[i]); } fclose(f); } int Max(int a, int b) { 172 if(a>b) return a; return b; } void QHD() { int i, j; for(i = 1; i<=n; i++) for(j=0; j<=W; j++) if(j>=w[i]) L[i][j] = Max(v[i]+L[i-1][j-w[i]], L[i-1][j]); } void TruyVet() { int i, j; i = n; j = W; int k; k = 1; vmax = 0; while(i && j) { if(L[i][j] == L[i-1][j]) i--; if(L[i][j] == (v[i] + L[i-1][j-w[i]]) && (j>w[i])) { pa[k] = i; vmax += v[i]; j -= w[i]; k++; i--; } 173 } } void InPA() { int i; i = 1; while(pa[i]) { printf("%3d", pa[i]); i++; } printf("-%3d", vmax); } main() { DocDL(); QHD(); TruyVet(); InPA(); getch(); } 2. Cài đặt thuật toán quay lui giải bài toán chiếc ba lô /*Doc du lieu tu file Balo.txt Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m) n dong tiep theo ghi trong luong va gia tri cua vat */ #include #include #include #define max 100 int n, W; 174 int w[max], v[max], vmax; int daxet[max]; int x[max]; int pa[max]; int vi, wi; void DocDL() { FILE *f; f = fopen("BaLo.txt", "r"); if(!f) { puts("Loi mo tep"); } fscanf(f, "%d", &n); fscanf(f, "%d", &W); for(int j=0; j<n; j++) { fscanf(f, "%d", &w[j]); fscanf(f, "%d", &v[j]); } } void LuuPa(int i) { //intf("%d\n", i); for(int j=0; j<=i; j++) pa[j] = x[j]; } void InPa() { int i = 0; while(pa[i]) 175 { printf("%3d", pa[i]); i++; } } void Try(int i) { for(int j=0; j<n; j++) if(!daxet[j] && (wi+w[j])<=W) { x[i] = j+1; daxet[j] = 1; vi += v[j]; wi += w[j]; if(vi>vmax) { vmax = vi; LuuPa(i); } Try(i+1); //x[i] = 0; daxet[j] = 0; wi -= w[j]; vi -= v[j]; } } int main() { DocDL(); wi = 0; vmax = 0; 176 vi = 0; Try(0); InPa(); getch(); } 3. Cài đặt thuật toán nhánh cận giải bài toán chiếc ba lô /*Doc du lieu tu file Balo.txt Dong thu nhat ghi so do vat (n) va trong luong toi da cua ba lo (m) n dong tiep theo ghi trong luong va gia tri cua vat */ #include #include #include #define max 100 int v[max], w[max]; int daxet[max]; int vi, wi, vmax; int n, W; int x[max]; int pa[max]; void DocDL() { FILE *f; f = fopen("BaLo.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } fscanf(f, "%d", &n); 177 fscanf(f, "%d", &W); for(int i=1; i<=n; i++) { fscanf(f, "%d", &w[i]); fscanf(f, "%d", &v[i]); } fclose(f); } int sumv(int i) { int s = 0; for(int j=i; j<=n; j++) s += v[j]; return s; } void LuuPa(int i) { for(int j=1; j<=i; j++) pa[j] = x[j]; } void InPa() { int i = 1; while(pa[i]) { printf("%3d", pa[i]); i++; } } void Try(int i) { 178 for(int j=1; j<=n; j++) { int v1, w1; v1 = vi + v[j]; w1 = wi + w[j]; if(!daxet[j] && w1<=W) if((sumv(j+1)+v1)>vmax) { x[i] = j; daxet[j] = 1; vi = v1; wi = w1; if(vi>vmax) { vmax = vi; LuuPa(i); } Try(i+1); daxet[j] = 0; vi -= v[j]; wi -= w[j]; } } } int main() { DocDL(); vi = 0; wi = 0; vmax = 0; Try(1); 179 InPa(); getch(); } 4. Cài đặt thuật toán quy hoạch động giải bài toán dãy con chung dài nhất Input: Hai dãy d1, d2 Output: Dãy con chung có độ dài lớn nhất /* Đọc dữ liệu từ file DayConChung.txt: mỗi dòng ghi 1 dãy*/ #include #include #include #include #define max 100 char a[max], b[max]; int n, m; int L[max][max]; char c[max]; void DocDL() { FILE *f; f = fopen("DayConChung.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } char s[max]; int i; fgets(s, 100, f); n = strlen(s); 180 s[n-1]='\0'; a[0] = ' '; strcat(a, s); fgets(s, 100, f); m = strlen(s); s[m-1]='\0'; b[0] = ' '; strcat(b, s); } int Max(int a, int b, int c) { if(a>=b && a>=c) return a; if(b>=a && b>=c) return b; return c; } void QHD() { int i, j; for(i=1; i<=n; i++) for(j=1; j<=m; j++) if(a[i] == b[j]) L[i][j] = Max(L[i-1][j], L[i][j-1], L[i-1][j-1] + 1); else L[i][j] = Max(L[i-1][j], L[i][j-1], L[i-1][j-1]); } void TruyVet() { int i, j; i=n-1; j=m-1; 181 int k=0; while(i && j) { if(L[i][j] == L[i-1][j]) i--; if(L[i][j] == L[i][j-1]) j--; if(a[i] == b[j]) { c[k] = a[i]; i--; j--; k++; } } c[k] = '\0'; } void InPA() { int l; l= strlen(c); for(int i=l-1; i>=0; i--) printf("%c", c[i]); } int main() { DocDL(); puts(a); puts(b); QHD(); TruyVet(); 182 InPA(); getch(); } 5. Cài đặt thuật toán quay lui giải bài toán Mã đi tuần #include #include #include int p; void InBanCo(int n, int *bc) { puts(""); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) printf("%5d",*(bc+ i*n+j)); printf("\n"); } } void try(int i, int n, int *bc,int *x,int *y, int *dx, int *dy) { for(int j=0; j<8; j++) { int u; int v; u = *x + dx[j]; v = *y + dy[j]; if(u >=0 && u =0 && v <8 && *(bc+u*n+v)==0) { *(bc + u*n +v) = i; if(i == n*n) InBanCo(n,bc); 183 else { *x = u; *y = v; try(i+1,n,bc,x,y,dx,dy); if(p==0) { *x = u - dx[j]; *y = v - dy[j]; *(bc + u*n + v) = 0; } } if(p==1) { *x = u - dx[j]; *y = v - dy[j]; *(bc + u*n + v) =0; } } } } main() { int n, x, y, *bc; int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dy[] = {1, 2, 2, 1, -1, -2, -2, -1}; printf("BAI TOAN MA DI TUAN\n\n"); printf("Nhap n = "); scanf("%d",&n); bc = (int *)calloc(n*n, sizeof(int)); printf("\nIn tat ca cac truong hop (1/0): "); 184 scanf("%d", &p); *bc = 1; x = 0; y = 0; try(2,n,bc,&x,&y,dx,dy); getch(); } 5. Cài đặt thuật toán thiết kế theo kỹ thuật tham lam giải bài toán người bán hàng. /* Dữ liệu lưu trong tệp NguoiBanHang.txt: ghi số thành phố và ma trận chi phí*/ #include #include #include #define max 100 int n; int matran[max][max]; int daxet[max]; int pa[max]; int chiphi; void DocDL() { FILE *f; f = fopen("NguoiBanHang.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } fscanf(f, "%d", &n); int i, j; for(i=1; i<=n; i++) 185 for(j=1; j<=n; j++) fscanf(f, "%d", &matran[i][j]); fclose(f); } void InPa() { int i; puts(""); for(i=1; i<=n; i++) printf("%d -> ", pa[i]); printf("%d -%3d", pa[n+1], chiphi); } int ChiPhiMin(int i) { int chiso = -1; int j; for(j=1; j<=n; j++) if(matran[i][j] && !daxet[j]) break; if(j>n) return -1; else { chiso = j; for(j=1; j<=n; j++) if(matran[i][chiso] > matran[i][j] && matran[i][j] && !daxet[j]) chiso = j; return chiso; } } void Greed_TSP() 186 { int i; for(i = 2; i<=n; i++) { int chiso; chiso = ChiPhiMin(pa[i-1]); if(chiso==-1) break; else { pa[i] = chiso; daxet[chiso] = 1; chiphi += matran[pa[i-1]][chiso]; } } if(i!=n+1) printf("\nKhong co phuong an - Khong di qua het cac dinh"); else { if(matran[pa[n]][1]) { chiphi += matran[pa[n]][1]; InPa(); } else printf("\nKhong co phuong an - Khong quay tro lai dinh 1 duoc"); } } int main() { DocDL(); 187 pa[1] = 1; daxet[1] = 1; chiphi = 0; Greed_TSP(); getch(); } 6. Cài đặt thuật toán thiết kế theo kỹ thuật quay lui giải bài toán người bán hàng. /* Dữ liệu lưu trong tệp NguoiBanHang.txt: ghi số thành phố và ma trận chi phí*/ #include #include #include #define max 100 int n; int matran[max][max]; int daxet[max]; int pa[max]; int chiphi; int c; void DocDL() { FILE *f; f = fopen("NguoiBanHang.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } fscanf(f, "%d", &n); int i, j; for(i=1; i<=n; i++) 188 for(j=1; j<=n; j++) fscanf(f, "%d", &matran[i][j]); fclose(f); } void InPa() { int i; puts(""); for(i=1; i<=n; i++) printf("%d -> ", pa[i]); printf("%d - %d", pa[n+1], chiphi); puts(""); } void Try(int i) { for(int j=2; j<=n; j++) if(!daxet[j] && matran[pa[i-1]][j]) { pa[i] = j; daxet[j] = 1; c += matran[pa[i-1]][j]; if(i==n) { if(matran[pa[n]][1]) { chiphi = c; chiphi += matran[pa[n]][1]; pa[n+1] = 1; InPa(); } } 189 else Try(i+1); daxet[j] = 0; c -= matran[pa[i-1]][j]; } } void inmt() { for(int i=1; i<=n; i++) { puts(""); for(int j=0; j<=n; j++) printf("%3d", matran[i][j]); } } int main() { DocDL(); daxet[1] = 1; pa[1] = 1; c = 0; Try(2); getch(); } 7. Cài đặt thuật toán thiết kế theo kỹ thuật nhánh cận giải bài toán người bán hàng. /* Dữ liệu lưu trong tệp NguoiBanHang.txt: ghi số thành phố và ma trận chi phí*/ #include #include #include #define max 100 int n; 190 int matran[max][max]; int daxet[max]; int pa[max]; int chiphi; void DocDL() { FILE *f; f = fopen("NguoiBanHang.txt", "r"); if(!f) { puts("Loi mo tep"); getch(); exit(0); } fscanf(f, "%d", &n); int i, j; for(i=1; i<=n; i++) for(j=1; j<=n; j++) fscanf(f, "%d", &matran[i][j]); fclose(f); } void InPa() { int j; for(j=1; j<=n; j++) printf("%d -> ", pa[j]); printf("%d - %d", pa[n+1], chiphi); } void Try(int i, int c) { int j; 191 int c1; for(j=2; j<=n; j++) { if(!daxet[j] && matran[pa[i-1]][j]) { c1 = c + matran[pa[i-1]][j]; if(c1<chiphi) { pa[i] = j; daxet[j] = 1; c = c1; if(i==n) { if(matran[pa[n]][1] && (c+ matran[pa[n]][1]) < chiphi) { pa[n+1] = 1; chiphi = c+ matran[pa[n]][1]; } } else Try(i+1, c); daxet[j] = 0; } } } } int main() { DocDL(); pa[1] = 1; daxet[1] = 1; 192 chiphi = 1000; Try(2, 0); InPa(); getch(); } 8.Cài đặt thuật toán thiết kế theo kỹ thuật quy hoạch động giải bài toán máy trả tiền ATM. /* Dữ liệu lưu trong tệp DoiTien.txt: ghi mệnh giá n loại tiền, số tiền cần rút*/ #include #include #include #define max 100 int n, soTien; int T[max]; int pa[max]; int B[max][max]; void DocDL() { FILE *f; f = fopen("DoiTien.txt", "r"); if(!f) { puts("Loi doc tep"); getch(); exit(0); } fscanf(f, "%d", &n); fscanf(f, "%d", &soTien); int i; for(i=1; i<=n; i++) fscanf(f, "%d", &T[i]); 193 fclose(f); } int Min(int a, int b) { if(a<b) return a; else return b; } void QHD() { int i, j; for(j=1; j<=soTien; j++) B[0][j] = 32767; for(i=1; i<=n; i++) for(j=1; j<=soTien; j++) { if(j<T[i]) B[i][j] = B[i-1][j]; else B[i][j] = Min(B[i-1][j], 1+ B[i][j-T[i]]); } } void TruyVet() { int i, j; i = n; j = soTien; int k; k = 1; while(i && (j>0)) { 194 if(B[i][j] == B[i-1][j]) i--; if(B[i][j] == (1 + B[i][j-T[i]])) { j -= T[i]; pa[k] = i; k++; } } } void InPA() { int i; i = 1; while(pa[i]) { printf("%3d", T[pa[i]]); i++; } } main() { DocDL(); QHD(); TruyVet(); InPA(); getch(); } 195 TÀI LIỆU THAM KHẢO [1]. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học quốc gia Hà Nội, 2004 [2]. Nguyễn Đức Nghĩa - Nguyễn Tô Thành, Toán rời rạc, Nhà xuất bản Đại học quốc gia Hà Nội, 2003 [3]. Robert Sedgewick, Cẩm nang thuật toán, NXB Khoa học kỹ thuật, 2004. [4]. Chủ biên Ngọc Anh Thư, Nhóm dịch Nguyễn Tiến, Nguyễn Văn Hoài, Nguyễn Hữu Bình, Đặng Xuân Hường, Ngô Quốc Việt, Trương Ngọc Vân: Giáo trình Thuật toán, NXB Thống kê, 2002 [5]. Nhóm dịch Trần Đan Thư, Vũ Mạnh Tường, Dương Vũ Diệu Trà, Nguyễn Tiến Huy: Cẩm nang Thuật toán, NXB Khoa học và Kỹ thuật, 1998 [6]. Hà Huy Khoái, Nhập môn số học thuật toán, NXB Khoa học kỹ thuật, 1997. [7].Giải thuật và Lập trình, Lê Minh Hoàng, Đại học Sư phạm Hà Nội, 2002. [8]. Trần Tuấn Minh, Thiết kế và đánh giá thuật toán, Đại học Đà lạt, 2002 [9]. Đinh Mạnh Tường, Cấu trúc dữ liệu & Thuật toán, Nhà xuất bản khoa học và kĩ thuật, 2001 [10]. Nguyễn Xuân Huy, Thuật toán, Nhà xuất bản thống kê, 1988 [11]. Thomas H. Cormen:Introduction to Algorithms, Second Edition, 2001 [12]. Robert Sedgewick, Algorightms 2 nd Edition, ISBN: 0201066734, Addison Wesley, 1988. [13]. Niklaus Wirth, Algorithms and Data Structures, Prentice-Hall, 1986 [14]. Donald E. Knuth, Selected papers on analysis of algorithms, LeLand Stanford Junior University, 2000 [15]. Gregory L.Heileman, Data structures, algorithms, and object – oreinted programing, McGraw – Hill, 1996