Khoa học máy tính - Thuật toán (algorithms)

THUẬT TOÁN (Algorithms)Nguyễn Thanh CẩmNội DungTHUẬT TOÁN VÀ ĐỘ PHỨC TẠP C1CHIA ĐỂ TRỊ C2QUY HOẠCH ĐỘNG C3THUẬT TOÁN THAM LAM C4THUẬT TOÁN QUAY LUIC5QUY HOẠCH ĐỘNGChia để trị là thiết kế thuật toán theo kiểu từ trên xuống (top-down) Quy hoạch động là quá trình tiếp cận thuật toán theo quá trình ngược lại, đó là thiết kế theo kiểu từ dưới lên (bottom-up).Điểm khác cơ bản của quy hoạch động với phương pháp chia để trị đó là:các bài toán con không độc lập với nhau, nghĩa là các bài toán con cùng có chung các bài toán con nhỏ hơn. Trong tình huống đó, phương pháp chia để trị sẽ tỏ ra không hiệu quả, khi nó phải lặp đi lặp lại việc giải các bài toán con chung đó. Quy hoạch động sẽ giải một bài toán con một lần và lời giải của các bài toán con sẽ được ghi nhận, nhằm thoát khỏi việc giải lại các bài toán con mỗi khi ta cần lời giải của nó.QUY HOẠCH ĐỘNGTrong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping subproblem) và cấu trúc con tối ưu (optimal substructure).Nhà toán học Richard Bellman đã phát minh phương pháp quy hoạch động vào năm 1953.2.12.22.2.12.2.2Thuật toán quy hoạch động tổng quátMột số thí dụ minh họa Bài toán thực hiện dãy phép nhân ma trậnBài toán tìm đường đi ngắn nhất - thuật toán Floy QUY HOẠCH ĐỘNGBài toán dãy con lớn nhất 2.2.3Bài toán dãy con chung dài nhất 2.2.43.1 Thuật toán quy hoạch động tổng quátĐể giải một bài toán bằng quy hoạch động, chúng ta cần tiến hành những công việc sau:Tìm nghiệm của các bài toán con (các trường hợp riêng) đơn giản nhất.Tìm ra các công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ hơn.Tạo ra một bảng để lưu giữ các nghiệm của các bài toán con. Sau đó tính nghiệm của các bài toán con theo các công thức đã tìm ra và lưu vào bảng.Từ bảng đã làm đầy, tìm cách xây dựng nghiệm của bài toán đã cho. 3.1 Thuật toán quy hoạch động tổng quátViệc phát triển giải thuật dựa trên quy hoạch động có thể chia làm 3 giai đoạn:Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bản thân bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất trong họ các bài toán con này.Ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng. Việc làm này là cần thiết vì lời giải của các bài toán con thường được sử dụng lại rất nhiều lần, và điều đó nâng cao hiệu quả của giải thuật do không phải giải lặp lại cùng một bài toán nhiều lần.Tổng hợp lời giải: Lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn tìm cách xây dựng lời giải của bài toán kích thước lớn hơn, cho đến khi thu được lời giải của bài toán xuất phát (là bài toán con có kích thước lớn nhất).3.1 Thuật toán quy hoạch động tổng quátCó hai tính chất quan trọng mà một bài toán tối ưu cần phải thoả mãn để có thể áp dụng quy hoạch động để giải nó là:Cấu trúc con tối ưu: Để giải được bài toán đặt ra một cách tối ưu, mỗi bài toán con cũng phải được giải một cách tối ưu. Số lượng các bài toán con phải không quá lớn. Rất nhiều các bài toán NP (xem [1] trang 234) – khó có thể giải được nhờ quy hoạch động, nhưng việc làm này là không hiệu quả do số lượng các bài toán con tăng theo hàm mũ. Một đòi hỏi quan trọng đối với quy hoạch động là tổng số các bài toán con cần giải là không quá lớn, cùng lắm phải bị chặn bởi một đa thức của kích thước dữ liệu vào.2.12.22.2.12.2.2Thuật toán quy hoạch động tổng quátMột số thí dụ minh họa Bài toán thực hiện dãy phép nhân ma trậnBài toán tìm đường đi ngắn nhất - thuật toán Floy QUY HOẠCH ĐỘNGBài toán dãy con lớn nhất 2.2.3Bài toán dãy con chung dài nhất 2.2.43.2.13.2.2Bài toán thực hiện dãy phép nhân ma trậnBài toán tìm đường đi ngắn nhất - thuật toán Floy 3.2 Một số thí dụ minh họa Bài toán dãy con lớn nhất 3.2.3Bài toán dãy con chung dài nhất 3.2.43.2.1 Bài toán thực hiện dãy phép nhân ma trậnTích của ma trận A = (aik) kích thước p x q với ma trận B = (bkj) kích thước q x r là ma trận C = (cij) kích thước p x r với các phần tử của C được tính theo công thức:  1 0, có n – d phần tử trên đường chéo cần tính, để tính mỗi phần tử đó ta cần so sánh d giá trị số tương ứng với các giá trị có thể của k. Từ đó suy ra số phép toán cần thực hiện theo thuật toán là cỡ3.2.1 Bài toán thực hiện dãy phép nhân ma trậnThuật toán trình bày có thể mô tả trong hai thủ tục sau:void Matrix-Chain(a,n)/* F[i,j] -  chi phí tối ưu thực hiện nhân dãy Mi . . . Mj;P[i,j] -  ghi nhận vị trí đặt dấu ngoặc đầu tiên trong cách thực hiện nhân dãy Mi . . . Mj */{for (i = 1;i1Từ công thức cuối cùng có thể chứng minh bằng quy nạp là T(n) = 2n.3.2.13.2.2Bài toán thực hiện dãy phép nhân ma trậnBài toán tìm đường đi ngắn nhất - thuật toán Floy 3.2 Một số thí dụ minh họa Bài toán dãy con lớn nhất 3.2.3Bài toán dãy con chung dài nhất 3.2.43.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy nhắc lại sơ lược về lý thuyết đồ thị. Hình 3.2 ở dưới là một đồ thị có hướng có trọng số. 1 3 9 5 1 2 3 3 2 4 Hình 3.2 Đồ thị có hướng có trọng sốV5V1V2V3V43.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy ví dụ trong hình 3.2 để đi từ v1 đến v3 ta có 3 đơn đường đi là: [v1, v2, v3], [v1, v4, v3], [v1, v2, v4, v3]. Vì thế độ dài của các đường đi này là:length [v1, v2, v3] = 1+3 = 4length[v1, v4, v3], = 1+2 = 3length[v1, v2, v4, v3] = 1+2+2 = 5Vậy [v1, v4, v3] là đường đi ngắn nhất từ v1 đến v3. Như đã đề cập ở trên, một ứng dụng phổ biến của đường đi ngắn nhất là xác định lộ trình ngắn nhất giữa các thành phố.3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Để tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v, ta liệt kê tất cả các đường đi từ u đến v (có thể có). Sau đó chọn đường đi ngắn. Tuy nhiên thuật toán này là không khả thi vì có độ phức tạp lớn hơn là thời gian hàm mũ. Nếu gọi T(n) là thời gian thực hiện thuật toán trên thì ta có T(n) = (n-2)! nên suy ra T(n) = O(n!), điều này là tồi hơn thời gian hàm mũ. Mục đích của chúng ta là tìm ra một thuật toán có hiệu quả hơn.3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Áp dụng phương pháp quy hoạch động cho bài toán tìm đường đi ngắn nhất, chúng ta có thể thực hiện như sau: Gọi W[i][j] là ma trận trọng số của đồ thị và được định nghĩa: 0 , nếu i = j W[i][j]= trọng số trên cạnh , nếu có cung từ vi đến vj ∞ , nếu không có cung từ vi đến vj. Bảng 3.3 dưới đây là ma trận trọng số của đồ thị ở hình 3.23.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Bảng 3.3 Ma trận trọng số của đồ thị ở hình 3.212345101∞1529032∞3∞∞04∞4∞∞20353∞∞∞03.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Bảng 3.4 Ma trận D chứa đường đi ngắn nhất giữa các cặp đỉnh trên đồ thị hình 12345101314280325310110474672035346403.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Tại sao chúng ta có thể tính D từ W. Minh họa điều này chúng ta sẽ tính một vài giá trị mẫu của D(k)[i][j] cho đồ thị ở hình 3.2D0[2][5] = length[v2, v5] = ∞D1[2][5] = min(length[v2, v5], length[v2, v1, v5]) = min(∞,14) = 14D2[2][5] = D1[2][5] = 14 (vì v2 là đỉnh khởi đầu nên không thể là đỉnh trung gian)D3[2][5] = D2[2][5] = 14 (vì không có đường đi từ v3 đến v5)D4[2][5] = min(D3[2][5], length[v2, v4 ,v5]) = min(14, 5) = 5Và cuối cùng giá trị tính toán D5[2][5] = 5 là chiều dài của đường đi ngắn nhất từ v2 đến v5 đã đi qua các đỉnh trung gian. Điều này có nghĩa nó là chiều dài của đường đi ngắn nhất.Như vậy D(n)[i][j] là chiều dài của đường đi ngắn nhất từ vi đến vj vượt qua các đỉnh trung gian, và D(0)[i][j] là chiều dài của đường đi ngắn nhất không vượt qua các đỉnh còn lại, nó là trọng số từ vi đến vj chúng ta đã thiết lập D(0) = W và D(n) = DVì thế để xác định D từ W chúng ta chỉ cần tìm cách để đạt được D(n) từ D(0).3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Sử dụng phương pháp quy hoạch động ta có thể thực hiện như sau:Cho k chạy từ 1 đến n, tính D(k) thông qua D(k-1). Như vậy ta đã tao ra một dãyD(0), D(1), D(2), , D(n)W DĐể tính D(k) thông qua D(k-1) ta có thể thực hiện theo hai trường hợp sau:Trường hợp 1: đường đi ngắn nhất từ vi đến vj dùng các đỉnh trung gian trong {v1, v2,,vk} trừ vk thì D(k)[i][j] = D(k-1)[i][j] (3.1)3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy một ví dụ của trường hợp này là ở bảng 3.3 D(5)[1][3] = D(4)[1][3] = 3 bởi vì khi chúng ta chọn đỉnh v5 làm đỉnh trung gian trên đường đi ngắn nhất từ v1 đến v3 thì ta không chọn được v5 nên đường đi chỉ còn [v1, v4, v3].Trường hợp 2: đường đi ngắn nhất từ vi đến vj sử dụng các đỉnh trung gian trong [v1, v2, .., vk] và sử dụng vk trong trường hợp này thì đường đi ngắn nhất là:D(k)[i][j] = D(k-1)[i][k] + D(k-1)[k][j] (3.2)Một ví dụ của trường hợp 2 trong bảng 3.3 là:D(2)[5][3] = 7 = 4 + 3 = D(1)[5][2] + D(1)[2][3] Bởi vì chúng ta phải có trường hợp 1 hoặc trường hợp hai giá trị của D(k)[i][j] là min của các giá trị bên phải của biểu thức 3.3 và 3.4 điều này có nghĩa là chúng ta xác định D(k) từ D(k-1) theo công thức sau:D(k)[i][j] = min(D(k-1)[i][j], D(k-1)[i][k] + D(k-1)[k][j])3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Ví dụ:Cho một đồ thị ở hình 3.2 đồ thị đã mô tả bởi ma trận kề W như ở bảng 3.3, một vài tính toán đơn giản như sau (với D(0) = W):D(1)[2][4] = min(D(0)[2][4], D(0)[2][1] + D(0)[1][4]) = min(2, 9+1) = 2D(1)[5][2] = min(D(0)[5][2], D(0)[5][1] + D(0)[1][2]) = min(∞, 3+1) = 4D(1)[5][4] = min(D(0)[5][4], D(0)[5][1]+D(0)[1][4]) = min(∞, 3+1) = 4Đầu tiên ta đã có mảng D(1) , mảng D(2) được tính toán như sau:D(2)[5][4] = min(D(1)[5][4], D(1)[5][2] + D(1)[2][4]) = min(4, 4+2) = 4Sau khi đã tính D(2) chúng ta tiếp tục tính tương tự cho đến D(5) mảng D cuối cùng là chiều dài của các đường đi ngắn nhất, nó thể hiện ở trong bảng 3.4.3.2.2 Bài toán tìm đường đi ngắn nhất - thuật toán Floy Thuật toán Floyd tìm đường đi ngắn nhấtBài toán: tính những đường đi ngắn nhất từ một đỉnh trong đồ thị có trọng số đến các đỉnh còn lại. (trọng số không âm)Input: (W[i][j])n*n là ma trận trọng số n đỉnh của đồ thị đã cho.Output: (D[i][j])n*n là ma trận trọng số của đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị n đỉnh.void floyd (int n, cónt number W[][], number D[][]){ index I, j,k: D=W for(k=1;k 1 và ta đã tính được si-1 . Ở bước thứ i để tính si là tổng của dãy con lớn nhất của dãy   a1, a2, , ai-1, ai.3.2.3 Bài toán dãy con lớn nhất Rõ ràng dãy con lớn nhất của dãy này hoặc là có chứa phần tử ai hoặc là không chứa phần tử ai, vì thế chỉ có thể là một trong hai dãy sau đây:·      Dãy con lớn nhất của dãy a1, a2, , ai-1.·      Dãy con lớn nhất của dãy a1, a2, , ai kết thúc tại ai.Từ đó suy ra   Si = max {si-1, ei },Trong đó ei là tổng của dãy con lớn nhất của dãy a1, a2, , ai kết thúc tại ai.3.2.3 Bài toán dãy con lớn nhất Lưu ý rằng để tính ei, i = 1, 2, , n, ta cũng có thể sử dụng công thức đệ quy sau:                e1 = a1;                ei = max {ai, ei-1 + ai }, i > 1.Ví dụ: cho dãy a = (3, 2, -7, 3, -5, 5, 3) thì dãy con lớn nhất là dãy b = (3,-5,5,3)Từ đó, ta có thuật toán sau để giải bài toán đặt ra:3.2.3 Bài toán dãy con lớn nhất void Maxsub(a);{    smax = a[1];                                  // smax - tổng của dãy con lớn nhất     maxendhere = a[1]; s=1; //vị trí đầu của dãy    imax = 1;                               // imax - vị trí kết thúc của dãy con lớn nhất     for( i = 2;i v) maxendhere = u else {maxendhere = v;s=i};                if (maxendhere > smax)                 {                            smax = maxendhere;                            imax = i;                } Else {smax=0;imax=i}    }}Dễ thấy thuật toán Maxsub có thời gian tính là O(n). 3.2.13.2.2Bài toán thực hiện dãy phép nhân ma trậnBài toán tìm đường đi ngắn nhất - thuật toán Floy 3.2 Một số thí dụ minh họa Bài toán dãy con lớn nhất 3.2.3Bài toán dãy con chung dài nhất 3.2.43.2.4 Bài toán dãy con chung dài nhất Bài toán: Cho hai dãy số nguyên a = (a1, a2, , am) và  b = (b1, b2, , bn). Cần tìm dãy số nguyên c = (c1, c2,, ck) sao cho c  a, c  b và c có độ dài lớn nhất.Ví dụ: nếu a = (3, 5, 1, 3, 5, 5, 3) và  b = (1, 5, 3, 5, 3, 1) thì dãy con chung dài nhất là  c = (5, 3, 5, 3) hoặc  c = (1, 3, 5, 3) hoặc  c = (1, 5, 5, 3).3.2.4 Bài toán dãy con chung dài nhất Thiết kế thuật toán: Thuật toán đơn giản: Duyệt tất cả các dãy con của dãy a và kiểm tra mỗi dãy như vậy có phải là dãy con của b, và giữ lại dãy con dài nhất. Mỗi dãy con của a tương ứng với dãy chỉ số là tập con k phần tử của tập chỉ số {1, 2, , m}, vì thế có tất cả 2m dãy con của a. 3.2.4 Bài toán dãy con chung dài nhất Áp dụng quy hoạch động: Nếu m = 0 hoặc n = 0, ta thấy dãy con dài nhất là dãy rổng.Nếu m >0 và n >0 ta gọi: (a1, a2,, ai) là dãy con của dãy a có độ dài i với 00 và j >0 và ai bj thì L(i, j) = max{L(i, j-1), L(i-1, j)}Nếu i >0 và j >0 và ai = bj thì L(i, j) = 1 + L(i-1, j-1)3.2.4 Bài toán dãy con chung dài nhất Lưu các giá trị L(i, j) vào mảng L[0..m, 0..n]. Nếu biết L[i, j-1], L[i-1, j] và L[i-1, j-1] ta sẽ tính được L[i, j], do đó ta có thể tính được các phần tử của mảng L[0..m, 0..n] 0 1 2 n 0 1 2 m3.2.4 Bài toán dãy con chung dài nhất Bây giờ từ mảng L đã được làm đầy, ta xây dựng dãy con chung dài nhất là k = L[m, n]. Ta xác định các thành phần của c = (c1, c2,, ck) lần lượt từ bên phải. Trong bảng L ta đi từ ô L[m, n]. 3.2.4 Bài toán dãy con chung dài nhất Giả sử ta đang ở ô L[i, j] và ta đang cần xác định cl (1 bj thì hoặc L[i, j] = L[i, j-1] hoặc L[i, j] = L[i-1, j]. Trong trường hợp L[i, j] = L[i, j-1] ta đi tới ô L[i, j-1].Còn nếu L[i, j] = L[i-1, j] thì ta đi lên ô L[i-1, j].Tiếp tục quá trình trên ta xác định được tất cả các thành phần của dãy con dài nhất c.3.2.4 Bài toán dãy con chung dài nhất void LCS(X[m],Y[n]);      {            for (i =1;i= L[i,j-1])                     {                          L[i,j] =L[i-1,j];                          b[i,j] =0;                      }                      else                        {                           L[i,j] =L[i,j-1];                           b[i,j] =-1;                        }        }3.2.4 Bài toán dãy con chung dài nhất Sử dụng bảng b[i, j] để ghi nhận tình huống tối ưu khi tính giá trị c[i, j] và đưa ra dãy con chung dài nhất của hai dãy X và Y nhờ hàm sau đây:void Print LCS (b,X,i,j);  {       if (i=0) or (j=0) return 0;       if (b[i,j]=1)          {              print LCS (b,X,i-1,j-1);              print xi;                        // Đưa ra phân tử xi          }         else            if (b[i,j]=­0)               PrintLCS (b,X,i-1,j)        else               Print LCS (b,X,i,j-1);   }Dễ dàng đánh giá được thời gian tính của thuật toán LCS là O(m.n).Tổng kết chươngabcdBài tậpBài 1-8/trang 68camcntt@yahoo.comThank You !