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

ử lý một cách tự động việc chép luân phiên vào b và c. Ta thực hiện bằng cách : Dùng một khoá k, với k  {1,2} và quy định : 48 Nếu k = 1 thì chép vào b; Nếu k = 2 thì chép vào c; Giả sử đầu tiên cho k = 1 để quyết định chép p phần tử của a vào b trước. Sau mỗi lần chép xong p phần tử, ta chỉ cần khởi động lại giá trị k = 3-k . Thao tác 2: Đọc p phần tử của a chép vào b như thế nào ? Ta đọc từng phần tử của a và chép phần tử đó vào b; Việc đọc chép từng phần tử này còn được thực hiện trong khi chưa đủ p phần tử và chưa hết dãy a. Vậy thao tác phân bố có thể mô tả chi tiết như sau : do { i = 1; while ( (i <= p) && (chưa hết dãy a) ) { Đọc phần tử thứ i trong a; if ( k == 1) chép vào b; else chép vào c; i++; } k = 3-k; } while(chưa hết dãy F); Thao tác phân bố cài đặt thành một hàm như sau : //F, F1, F2, n, h1,h2 là các biến toàn cục. distribute(p) { int i, k=1, l = 1; h1 = 0; h2 = 0; do { 49 i = 1; while( i<=p && l <= n) { if(k==1) { h1++; F1[h1] = F[l]; } else { h2++; F2[h2] = F[l]; } i++; l++; } k = 3-k; } while(l <= n); } Với công việc thứ hai: Trộn từng bộ p phần tử trong c, và p phần tử trong c, kết quả lưu tr? vào a, trong khi chưa hết b và c. Input b, c; Output a; Mô tả : Trong khi ( chưa hết dãy b và chưa hết dãy c ) { Trộn từng cặp p phần tử của b và của c vào a; } Trong khi (chưa hết dãy c) 50 chép các phần tử còn lại của c vào a; Trong khi (chưa hết dãy b) chép các phần tử còn lại của b vào a; Ta cần chỉ rõ công việc trộn từng cặp p phần tử của b và của c vào a hoạt động như thế nào ? Đó là : - (*) : Đọc từng phần tử trong b, trong c, so sánh giá trị của chúng, giá trị nào nhỏ hơn thì chép phần tử tương ứng vào a. Nếu là phần tử của b thì đọc tiếp 1 phần tử của b; ngược lại thì đọc tiếp 1 phần tử của c - ( ** ) :Thao tác trên còn được thực hiện trong khi : chưa đọc đủ p phần tử trong b và chưa đọc đủ p phần tử trong c và chưa hết dãy c và chưa hết dãy b; Vòng lặp (**) dừng khi đã đọc đủ p phần tử trong c, hoặc đã đọc đủ p phần tử trong b, hoặc hết dãy b hoặc hết dãy c; Và khi đó ta cần xử lý các trường hợp sau : Trong trường hợp chưa hết dãy b và chưa hết dãy c : Nếu chưa đủ p phần tử trong b, thì đọc và chép các phần tử của b vào a cho đủ p. Tương tự như vậy cho c. * Đánh giá độ phức tạp tính toán của thuật toán Ta nhận xét rằng, trong phương pháp sắp xếp bằng trộn hai đường trực tiếp, số lượng các bước sao chép các phần tử từ dãy này sang dãy kia còn lớn hơn số lượng các bước so sánh giữa các phần tử : Vì ứng vớùi một lần so sánh thì có một thao tác sao chép, nhưng nếu một dãy nào đó xử lý cạn (hết dãy) thì phần đuôi của dãy còn lại được sao chép mà không ứng với một phép so sánh nào. Vì thế, đối với phương pháp này, ta chọn phép sao chép làm căn cứ đánh giá thời gian thực hiện của thuật toán. Trong mỗi lần phân bố và trộn thì toàn bộ n phần tử được duyệt qua, so sánh và chép vào dãy đích (output). Như vậy thời gian chi phí cho mỗi bước có cấp là O(n). Vì trong mỗi bước (bước thứ k) ta giải quyết được 2k = p giá trị và tiến trình dừng khi p ≥ n nên ta có lg2n bước, do đó cấp thời gian chi phí cho phương pháp này là O(nlg2n). Một nhượïc điểm của phương pháp sắp xếp bằng kiểu trộn hai đường trực tiếp là chi phí cho không gian quá lớn: nó đòi hỏi cung cấp vùng nhớ 2n phần tử, gấp đôi so với phương pháp thông thường. Do đó phương pháp này chỉ thích hợp khi ta thao tác trên các tệp. 51 Mặt khác, phương pháp sắp xếp kiểu trộn hai đường trực tiếp có một nhược diểm quan trọng nữa là nó tự giới hạn số lượng các giá trị cố định là 1, 2, 4,.., 2k, trong đó 2k < n. Như vậy ta luôn luôn phải duyệt qua k bước chia và trộn. Nếu cho phép số lượng các phần tử trong một lần trộn có kích thước khác thì số các bước có thể giảm đi và trong trường hợp này việc sắp xếp có khả năng kết thúc sớm. 2.2.3. T×m kiÕm nhÞ ph©n 1) Bài toán Cho dãy a gồm n phần tử đã được sắp tăng dần và một phần tử x. Tìm x có trong a hay không? Nếu có x trong a thì cho kết quả là chỉ số của phần tử đó, ngược lại cho kết quả 0. 2) Ý tƣởng Chia đôi dãy, mỗi lần chia đôi so sánh phần tử giữa x với nếu x bằng phần tử giữa thì dừng, ngược lại nếu x nhỏ hơn phần tử giữa thì lấy nửa trái, ngược lại thì lấy nửa phải 3) Thiết kế thuật toán + l là chỉ số dưới của dãy a + r là chỉ số dưới của dãy a + m là chỉ số giữa. Mô tả thuật toán: - Nếu l > r kết thúc và trả lại giá trị 0 (không tìm thấy) - Nếu l<=r thì: + tính m=[(l+r)/2]; + So sánh x và a[m]: Nếu x= a[m]: kết thúc và trả lại m ngược lại nếu x<a[m]: tìm kiếm (đệ quy) ở nửa trái- từ a[l] đến a[m-1] ngược lại tìm kiếm (đệ quy) ở nửa phải- từ a[m+1] đến a[r] Thuật toán: KNP(l,r,a,x) { if(l>r) loc=0; 52 else { m=[(l+r)/2]; if(x<a[m]) loc=TKNP(l,m-1,a,x); else if(x>a[m]) loc=TKNP(m+1,r,a,x) else loc=m; return(loc); } 4) Đánh giá độ phức tạp tính toán của thuật toán - Xây dựng phương trình truy hồi: c1 nếu n=1 T( 2 n )+c2 nếu n>1 Với n>1 ta có: T(n) = T( 2 n )+ c2 = T( 4 n )+ 2c2 = T( 8 n )+ 3c2 .... = T( i2 n )+ ic2 Dừng khi i2 n =1  n=2i  i=log2n Do đó T(n) = T(1) + c2log2n = c1 + c2log2n T(n)= 53 = O(log2n) 2.2.4. Nh©n c¸c sè nguyªn lín. 1) Bài toán Cho hai số nguyên X và Y, mỗi số gồm n chữ số. Tính tích của hai số nguyên đó. 2) Ý tƣởng Biểu diễn X và Y dưới dạng X = A10n/2 + B và Y = C10n/2 + D Trong đó A, B, C, D là các số có n/2 chữ số. Chẳng hạn với X = 1234 thì A = 12 và B = 34 vì 12*10 2 + 34 = 1234 = X Với cách biểu diễn này thì XY = AC10n + (AD + BC)10n/2 + BD (*) Thay vì nhân trực tiếp 2 số có n chữ số, ta phân tích bài toán ban đầu thành một số bài toán nhân 2 số có n/2 chữ số. Sau đó, ta kết hợp các kết quả trung gian theo công thức (*). Việc phân chia này sẽ dẫn đến các bài toán nhân 2 số có 1 chữ số. Đây là bài toán cơ sở. Tóm lại: - Kích thước bài toán: số chữ số của X, Y - Phân tích: Chia bài toán ban đầu thành các bài toán nhân các số có n/2 chữ số. Quá trình phân chia dừng lại khi kích thước bài toán bằng 1. - Tổng hợp: Tổng hợp kết quả theo công thức (*). Chú ý: Với những số có một số lẻ chữ số ta thêm số 0 vào đầu để được số có một số chẵn chữ số. 3) Thiết kế thuật toán Theo công thức (*) ở trên việc nhân 2 số nguyên có n chữ số được phân chia thành 4 phép nhân các số nguyên có n/2 chữ số, 3 phép cộng và 2 phép nhân với 10 n và 10 n/2. Phép cộng các số cần O(n). Phép nhân với 10n tốn O(n). Gọi T(n) là thời gian nhân 2 số có n chữ số ta có phương trình truy hồi sau: C1 nếu n =1 4T( 2 n ) + C2n nếu n >1 Khi đó độ phức tạp tính toán sẽ được xác định như sau: Ta có với n>1: T(n)= 54 T(n) = 4T( 2 n )+c2n = 4(4T( 4 n )+c2 2 n ) + c2n = 16T( 4 n ) + 3c2n = 2 4 T( 22 n ) + 3c2n = 16( 4T( 8 n )+c2 4 n ) + 3c2n = 64T( 8 n ) + 7c2n = 2 6 T( 32 n ) + 7c2n ..... = 2 2i T( i2 n ) + (2 i - 1)c2n Quá trình sẽ dừng khi i2 n =1  n =2i  i = log2n Khi đó T(n) = nC)12()1(T2 2 nlognlog2 22  = C1n 2 + C2(n-1)n Và T(n) = O(n 2 ) Như vậy ta không cải tiến được gì với giải thuật nhân thông thường. Ta biến đổi công thức (*) lại như sau: XY = AC10 n + [(A -B)(D-C) + AC + BD]10 n/2 + BD (**) Theo công thức này, ta chỉ cần 3 phép nhân các số nguyên có n/2 chữ số, 6 phép cộng trừ và 2 phép nhân với 10n, 10n/2. Ví dụ 2.2. Ta minh hoạ quá trình này bằng việc nhân 981 với 1234. Trước tiên chúng ta điền thêm vào toán hạng ngắn hơn một số không vô nghĩa để làm cho hai toán hạng có cùng độ dài, vậy là 981 trở thành 0981. Sau đó tách từng toán hạng thành hai nửa: 0981 tách thành w = 09 và x = 81 1234 tách thành y = 12 và z = 34 Lưu ý rằng 981 = 102w + x và 1234 = 102y + z. Do đó, tích cần tìm có thể tính được là: 981 x 1234 = (10 2 w + x)( 10 2 y + z) = 10 4 wy + 10 2 (wz + xy) + xz 55 = 1080000 + 127800 + 2754 = 1210554 Thủ tục trên đến bốn phép nhân hai nửa: wy, wz, xy và xz. Để ý điểm mấu chốt ở đây là thực ra thì không cần tính cả wz lẫn xy, mà là tổng của hai số hạng này. Liệu có thể thu được wz + xy với chi phí của một phép nhân mà thôi hay không? Điều này có vẻ như không thể được cho đến khi chúng ta nhớ ra rằng mình cũng cần những giá trị wy và xz để đưa vào công thức trên. Lưu ý về điểm này, hãy xét tích: r = (w + x)(y+z) = wy + (wz + xy) + xz Chỉ sau một phép nhân, chúng ta thu được tổng của tất cả ba số hạng cần thiết để tính được tích mình mong muốn. Điều này gợi ý một cách tiến hành như sau: p = wy = 09 * 12 = 108 q = xz = 81 * 34 = 2754 r = (w + x)(y+z) = 90 * 46 = 4140 và cuối cùng 981 x 1234 = 10 4 p + 10 2 (r – p – q) + q = 1080000 + 127800 + 2754 = 1210554. Như vậy tích của 981 và 1234 có thể rút gọn về ba phép nhân của hai số có hai chữ số (09 với 12, 81 với 34 và 90 với 46) cùng với một số nào đó phép dịch chuyển (nhân với luỹ thừa của 10), phép cộng và phép trừ. Từ đó ta đưa ra thuật toán nhân số nguyên lớn là Nhan(x,y,n) { if (n == 1) Return x[0]*y[0]; Else { a = x[n-1]. . . x[n/2]; b = x[n/2-1] . . . x[0]; c = y[n-1]. . . y[n/2]; d = y[n/2-1] . . . y[0]; U = Nhan(a,c,n/2); 56 V = Nhan(b,d,n/2); W = Nhan(a+b,c+d,n/2); Return U*10 n + (W-U-V)*10 n/2 + V } } 4) Đánh giá độ phức tạp tính toán của thuật toán Ta có phương trình đệ quy sau: T(1) = 1 T(n) = 3T(n/2) + cn Giải phương trình ta được T(n) = O(nlog3) = O(n1.59). Rõ ràng cải tiến hơn giải thuật cũ rất nhiều. thuật toán này có thể nhân hai số nguyên lớn nhanh hơn rất nhiều so với thuật toán nhân cổ điển và n càng lớn thì sự cải thiện này càng đáng giá. 57 Bµi tËp ch-¬ng 2 1. Hãy đưa ra hai thuật toán được thiết kế theo kỹ thuật chia để trị. 2. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau: Tính tổng: 1 + 1/2 + 1/3 + ... + 1/n với n là một số nguyên dương. 3. Dùng kỹ thuật chia để trị thiết kế thuật toán giải bài toán sau: Tìm ước số chung lớn nhất của hai số nguyên dương. 4. Bài toán tháp Hà nội Có n chiếc đĩa với đường kính khác nhau được đặt chồng lên nhau ở vị trí A, đĩa bé ở trên đĩa to. Cần chuyển chồng đĩa sang vị trí B được lấy vị trí C làm trung chuyển với điều kiện: Mỗi lần chỉ được chuyển một đĩa và trong quá trình chuyển không bao giờ được đặt đĩa to ở trên đĩa bé. Hướng dẫn: Vận dụng kỹ thuật chia để trị: Bài toán chuyển N đĩa từ A sang B có thể chia thành các bài toán nhỏ hơn như sau: (a) Chuyển N-1 đĩa ở trên từ A sang C (b) Chuyển một đĩa từ A sang B (c) Chuyển N-1 đĩa từ C sang B. Như vậy bài toán đã được chuyển thành các bài toán tương tự với kích thước nhỏ hơn. Công việc được tiếp tục với (n-1) đĩa và cứ như thế cho đến khi chỉ còn một đĩa. 5. Bài toán hoán đổi hai phần trong dãy Cho a[1..n] là một mảng gồm n phần tử. Ta cần chuyển m phần tử đầu tiên của mảng với phần còn lại của mảng (n-m phân tử) mà không dùng một mảng phụ . Chẳng hạn, với n = 8, a[8] = (1, 2, 3, 4, 5, 6, 7, 8) Nếu m = 3, thì kết quả là : ( 4, 5, 6, 7, 8, 1, 2, 3) Nếu m = 5, thì kết quả là : ( 6, 7, 8, 1, 2, 3, 4, 5) Nếu m = 4, thì kết quả là : ( 5, 6, 7, 8, 1, 2, 3, 4) Hướng dẫn: - Nếu m = n – m: Hoán đổi các phần tử của 2 nửa mảng có độ dài bằng nhau : 58 - Nếu m n–m + Nếu m < n – m : hoán đổi m phần tử đầu với m phân tử cuối của phần còn lại. Sau đó trong mảng a[1..n-m] ta chỉ cần hoán đổi m phần tử đầu với phần còn lại. + Nếu m > n – m : hoán đổi n-m phần tử đầu tiên với n-m phần tử của phần sau. Sau đó trong mảng a[n-m+1 . . n] ta hoán đổi n-m phần tử cuối mảng với các phần tử của phần đầu. Như vậy, bằng cách áp dụng phương pháp chia để trị, ta chia bài toán thành 2 bài toán con : - Bài toán thứ nhất là hoán đổi hai mảng con có độ dài bằng nhau, cụ thể là hoán đổi nửa số phần tử đầu và cuối của mảng cho nhau bằng cách đổi chỗ từng cặp phần tử tương ứng. - Bài toán thứ hai cùng dạng với bài toán đã cho nhưng kích thước nhỏ hơn, nên có thể gọi thuật toán đệ qui để giải và quá trình gọi đệ qui sẽ dừng khi đạt tới sự hoán đổi 2 phần có độ dài bằng nhau Vậy mấu chốt của thuật toán là thực hiện thao tác hoán đổi 2 nhóm phần tử, lặp lại thao tác này trong khi số lượng phần tử của 2 nhóm còn khác nhau. Vì vậy ta sẽ thay thuật toán đệ qui bằng thuật toán lặp. // Hoán đổi m phần tử đầu của mảng với phần còn lại. Input : a[1..n], m. (m ≤n) Output : a[1..n] với tính chất m phần tử đầu mảng a (mảng nhập ) nằm cuối mảng kết quả, n-m phần tử cuối mảng nhập nằm ở đầu mảng kết quả. Mô tả thuật toán : Transpose(a,n,m) { i = m; j = n-m; m = m+1; Khi ( i != j) Nếu ( i > j) { Exchange(a,m-i,m,j); i = i – j; } Ngược lại { 59 j = j – i; Exchange(a,m-i,m+j,i); } Exchange(a,m-i,m,i); } Hàm exchange : input a, i,j, //vị trí m; // Số phần tử cần hoán đổi output a Exchange(a,i,j,m) { Với mọi p = 0 -> m-1 Đổichỗ (a[i+p], a[j+p]); } 6. Lập lịch thi đấu thể thao Có n = 2 k đối thủ thi đấu với nhau theo thể thức vòng tròn một lượt: Mỗi đấu thủ phải đấu với các đấu thủ khác 1 trận. Mỗi đấu thủ chỉ đấu nhiều nhất một trận mỗi ngày. Hãy xếp lịch thi đấu sao cho số ngày thi đấu là ít nhất. Hướng dẫn: Vì thể thức thi đấu là vòng tròn một lượt nên mỗi đấu thủ phải thi đấu đúng n-1 trận. Ta dễ dàng thấy rằng vì n là một số chẵn nên ta có thể sắp nhiều nhất là n/2 cặp thi đấu trong một ngày và do đó cần ít nhất n-1 ngày. Ta sẽ tìm cách xây dựng lịch để số ngày thi đấu là n-1. Lịch thi đấu là một bảng n dòng và n-1 cột. Các dòng được đánh số từ 1 đến n và các cột được đánh số từ 1 đến n-1, trong đó dòng i biểu diễn cho đấu thủ i, cột j biểu diễn cho ngày thi đấu j và ô(i, j) ghi đấu thủ phải thi đấu với đấu thủ i trong ngày j. Kỹ thuật chia để trị được áp dụng để xây dựng lịch thi đấu như sau: Ðể sắp lịch cho n đấu thủ, ta sẽ sắp lịch cho n/2 đấu thủ, để sắp lịch cho n/2 đấu thủ, ta sẽ sắp lịch cho n/4 đấu thủ... Quá trình này sẽ dẫn đến bài toán cơ sở là sắp lịch thi đấu cho 2 đấu thủ. Hai đấu thủ này sẽ thi đấu một trận trong một ngày, lịch thi đấu cho họ thật dễ sắp. Khó khăn chính là ở chỗ từ các lịch thi đấu cho hai đấu thủ, ta tổng hợp lại để được lịch 60 thi đấu của 4 đấu thủ, 8 cấu thủ, ... Góc trên bên trái của bảng chính là lịch thi đấu của n/2 đấu thủ từ 1 đến n/2 trong các ngày từ ngày 1 đến ngày [(n-1)/2], từ đó ta có góc dưới bên trái là lịch thi đấu trong các ngày này của các đấu thủ từ n/2+1 đến n: nó sẽ bằng các phần tử ở góc trên bên trái cộng thêm n/2. Góc dưới bên phải của bảng chính là góc trên bên trái và góc trên bên phải chính là góc dưới bên trái. Còn với cột [(n-1)/2] +1 thì n/2 đấu thủ đầu sẽ lần lượt đấu với n/2 đấu thủ sau và ngược lại. Chẳng hạn: Xuất phát từ lịch thi đấu cho hai đấu thủ ta có thể xây dựng lịch thi đấu cho 4 đấu thủ như sau: Lịch thi đấu cho 4 đấu thủ sẽ là một bảng 4 dòng, 3 cột. Lịch thi đấu cho 2 đấu thủ 1 và 2 trong ngày thứ 1 chính là lịch thi đấu của hai đấu thủ (bài toán cơ sở). Như vậy ta có Ô(1,1) = “2” và Ô(2,1) = “1”. Tương tự ta có lịch thi đấu cho 2 đấu thủ 3 và 4 trong ngày thứ 1. Nghĩa là Ô(3,1) =“4” và Ô(4,1) = “3”. (Ta cố thể thấy rằng Ô(3,1) = Ô(1,1) + 2 và Ô(4,1) = Ô(2,1) + 2 ). Ta lấy góc trên bên trái của bảng lắp vào cho góc dưới bên phải và lấy góc dưới bên trái lắp cho góc trên bên phải. Bây giờ để hoàn thành lịch thi đấu cho 4 đấu thủ ta điền nốt cột 2. Lịch thi đấu cho 8 đấu thủ là một bảng gồm 8 dòng, 7 cột. Góc trên bên trái chính là ch thi đấu trong 3 ngày đầu của 4 đấu thủ từ 1 đến 4. Các ô của góc dưới bên trái sẽ bằng các ô tương ứng của góc trên bên trái cộng với 4. Ðây chính là lịch thi đấu cho 4 đấu thủ 5, 6, 7 và 8 trong 3 ngày đầu. Bây giờ chúng ta hoàn thành việc sắp lịch bằng cách lấp đầy góc dưới bên phải bởi góc trên bên trái và góc trên bên phải bởi góc dưới bên trái và điền nốt cột 4. Dưới đây là các bảng xếp lịch thi đấu cho 2 đấu thủ, 4 đấu thủ và 8 đấu thủ theo cách xây dựng trên: 1 1 2 2 1 2 đấu thủ 1 2 3 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 4 đấu thủ 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 8 đấu thủ 61 7. Bài toán tìm cặp điểm gần nhất (láng giềng gần nhất) Trong mặt phẳng cho n điểm phân biệt. Hãy tìm hai điểm gần nhau nhất (khoảng cách Ơcolit là nhỏ nhất). Hướng dẫn: Xây dựng một thuật toán dựa trên kỹ thuật chia để trị với ý tưởng là: sắp xếp các điểm theo một trục toạ độ, như trục x chẳng hạn, rồi dùng thứ tự này để chia tập điểm thành hai phần. Trong toàn bộ tập điểm đã cho, cặp điểm gần nhất hoặc là cặp gần nhất trong cùng một bên nào đó, hoặc là một cặp điểm cắt ngang đường thẳng phân giới giữa hai tập điểm thành phần. Dĩ nhiên, trường hợp đáng chú ý là khi cặp điểm gần nhất cắt ngang đường phân giới. Cặp điểm gần nhất trong mỗi nửa bên rõ ràng là tìm được bằng các lời gọi đệ quy, nhưng còn các cặp có mỗi điểm ở một bên đường phân giới sẽ được kiểm tra như thế nào? Điều tất nhiên là chúng ta sẽ chỉ cần xét những điểm trong khoảng cách min ở hai bên đường phân giới (vì đang tìm cặp điểm gần nhất), với min là khoảng cách nhỏ hơn giữa các cặp điểm gần nhất ở mỗi nửa bên. Tuy nhiên, trong trường hợp xấu nhất thì nhận xét này là không đủ, vì có thể có nhiều cặp gần với đường phân giới; ví dụ như tất cả các điểm ở mỗi nửa bên có thể sắp thành một hàng ngay cạnh đường thẳng phân giới. Để xử lý tình huống trên, cần phải sắp các điểm theo y. Như vậy, chúng ra có thể giới hạn các khoảng cách phải tính như sau: - Xử lý các điểm theo chiều tăng của y - Kiểm tra xem mỗi điểm có nằm trong dải đứng chứa các điểm trong phạm vi min kể từ điểm phân giới - Với mỗi điểm trong dải trên, tính khoảng cách giữa điểm này với các điểm cũng trong dải và có tung độ y nhỏ hơn tung độ của điểm đang xét nhưng không nhỏ quá min. Khoảng cách giữa các điểm ở mỗi nửa bên tối thiểu là min nên số điểm phải kiểm tra sẽ ít hơn. Viết một hàm đệ quy vừa sắp theo y lại vừa tìm cặp điểm gần nhất. Thủ tục này sẽ chia đôi tập điểm, rồi gọi lại chính nó để sắp hai nửa bên theo y và tìm cặp điểm gần nhất trong mỗi nửa, sau đó trộn hai nửa bên để hoàn tất việc sắp theo y và áp dụng lại thủ tục trên để hoàn tất việc tính cặp điểm gần nhất. Khi sắp theo y, việc chia đôi có thể làm bằng bất kỳ cách nào, nhưng với phép tính cặp điểm gần nhất, việc chia đôi yêu cầu có một nửa bên có hoành độ x nhỏ hơn nửa bên còn lại. Điều này được thực hiên bằng cách sắp theo x trước khi chia đôi tập điểm. 62 Ch-¬ng 3 Kü thuËt tham lam 3.1. Néi dung kü thuËt 3.1.1. Bµi to¸n tèi -u tæ hîp Bài toán tối ưu tổ hợp có dạng tổng quát như sau: Cho hàm f(x) xác định trên một tập hữu hạn các phần tử D. Hàm f(x) được gọi là hàm mục tiêu, tập D được gọi là tập các phương án Mỗi phần tử xD có dạng x = (x1, x2, .. xn) được gọi là một phương án. Cần tìm một phương án x* D sao cho hàm f(x*) đạt min (max). Phương án x* như thế được gọi là phương án tối ưu. Ta có thể tìm thấy phương án tối ưu bằng phương pháp “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để xác định phương án tốt nhất. Mặc dù tập hợp D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng phương pháp “vét cạn” thì độ phức tạp tính toán sẽ có có cấp hàm mũ. 3.1.2. Néi dung kü thuËt tham lam Tham lam (còn gọi là tham ăn, háu ăn) hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp trong quá trình xây dựng một phương án x. Phương án x được xây dựng bằng cách lựa chọn từng thành phần xi cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi xi, ta sẽ chọn xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta không còn gì để chọn mà phải chấp nhận một giá trị cuối cùng còn lại. Áp dụng kĩ thuật tham lam sẽ cho một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu. 3.2 C¸c vÝ dô ¸p dông 3.2.1. Bµi to¸n ng-êi giao hµng 1) Bài toán 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 63 đầ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. Hãy 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. Nếu sử dụng phương pháp vét cạn ta xét tất cả các chu trình, mỗi chu trình tính tổng độ dài các cạnh của nó rồi chọn một chu trình có tổng độ dài nhỏ nhất. Như vậy chúng ta cần xét tất cả là (n-1)!/2 chu trình. Thực vậy, do mỗi chu trình đều đi qua tất cả các đỉnh (thành phố) nên ta có thể cố định một đỉnh. Từ đỉnh này ta có n-1 cạnh tới n-1 đỉnh khác, nên ta có n-1 cách chọn cạnh đầu tiên của chu trình. Sau khi đã chọn được cạnh đầu tiên, chúng ta còn n-2 cách chọn cạnh thứ hai, do đó ta có (n-1)(n-2) cách chọn hai cạnh. Cứ lý luận như vậy ta sẽ thấy có (n-1)! cách chọn một chu trình. Tuy nhiên với mỗi chu trình ta chỉ quan tâm đến tổng độ dài các cạnh chứ không quan tâm đến hướng vì vậy có tất cả (n - 1)!/2 chu trình. Ðó là một thuật toán có độ phức tạp tính toán là hàm mũ. 2) Thiết kế thuật toán - Ý tưởng: Gọi n thành phố người giao hàng phải đi qua là các thành phố 1, 2, ..., n. Xuất phát từ một thành phố i nào đó đi đến thành gần thành phố i nhất trong trong n-1 thành phố còn lại, chẳng hạn thành phố j, từ thành phố j đi đến thành phố gần thành phố j nhất trong n-2 thành phố còn lại. Quá trình được lặp lại cho đến khi đã đi hết n thành phố thì quay về thành phố i - ta được một chu trình. - Thuật toán: Giaohang (a, n, dau) /* Mảng a mà a[i][j] là độ dài từ thành phố i đến thành phố j n số thành phố dau: thành phố xuất phát xet[v]: ghi nhận trạng thái thành phố v- chưa đến bằng 0, đã đến bằng 1 cost: lưu độ dài chu trình Mảng ct có các phần tử lưu trữ lần lượt n thành phố đi qua */ { for(k = 1; k <= n; k++) 64 xet[k] = 0; cost = 0; v = dau; i = 1; ct[i] = v; xet[v] = 1; while(i < n) { min = vc;/*do dai tu v den thanh pho bat ky chua den*/ for (k = 1; k <= n; k++) if(!xet[k]) if(min > a[v][k]) { min = a[v][k]; w = k; } v = w; i++; ct[i] = v; xet[v] = 1; cost += min; } return cost; } 3) Đánh giá độ phức tạp tính toán của thuật toán Phép toán tích cực là phép kiểm tra (!xet[k]), phép kiểm tra này nằm trong vòng lặp for (k = 1; k <= n; k++) và vòng lặp while(i < n). Mỗi vòng lặp thực hiện n lần, do đó độ phức tạp tính toán là O(n2). Nhận xét: 65 Có thể giải quyết bài toán bằng kỹ thuật tham lam theo cách tiếp cận khác như sau: 1. Sắp xếp các cạnh theo thứ tự tăng dần của độ dài. 2. Lần lượt xét các cạnh có độ dài từ nhỏ đến lớn để đưa vào chu trình. Một cạnh sẽ được đưa vào chu trình nếu cạnh đó thỏa mãn hai điều kiện sau: • Không tạo thành một chu trình thiếu (không đi qua đủ n đỉnh) • Không tạo thành một đỉnh có cấp ≥ 3 (tức là không được có nhiều hơn hai cạnh xuất phát từ một đỉnh, do yêu cầu của bài toán là mỗi thành phố chỉ được đến một lần: một lần đến và một lần đi) Cho đến khi xây dựng được một chu trình. Thuật toán Giaohang() /* E là tập hợp các cạnh đã được sắp xếp theo chiều tăng của độ dài, Chu_trinh là tập hợp các cạnh được chọn để đưa vào chu trình */ { Chu_Trinh = Φ; Gia = 0; while(E Φ) { if (cạnh e có thể chọn) { Chu_Trinh = Chu_Trinh + [e] ; Gia = Gia + độ dài của e; } E = E-[e]; } } Thuật toán trên có độ phức tạp tính toán là O(n2) 3.2.2. Bµi to¸n chiÕc ba l« 1) Bài toán 66 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. 2) Thiết kế thuật toán Theo yêu cầu của bài toán thì ta cần những đồ vật có giá trị cao mà trọng lượng lại nhỏ để sao cho có thể mang được nhiều “đồ quý”, sẽ là hợp lý khi ta quan tâm đến yếu tố “đơn giá” của từng loại đồ vật tức là tỷ lệ giá trị/trọng lượng. Ðơn giá càng cao thì đồ càng quý. Từ đó ta có kĩ thuật tham lam áp dụng cho bài toán này là: 1. Tính đơn giá cho các loại đồ vật. 2. Xét các loại đồ vật theo thứ tự đơn giá từ lớn đến nhỏ. 3.Với mỗi đồ vật được xét sẽ lấy một số lượng tối đa mà trọng lượng còn lại của ba lô cho phép. 4. Xác định trọng luợng còn lại của ba lô và quay lại bước 3 cho đến khi không còn có thể chọn được đồ vật nào nữa. Ví dụ 3.1. Ta có một ba lô có trọng lượng là 37 và 4 loại đồ vật với trọng lượng và giá trị tương ứng được cho trong bảng dưới: Tên đồ vật Trọng lượng Giá trị A 15 30 B 10 25 C 2 2 D 4 6 Hình 3.1. Trọng lượng và giá trị của 4 loại đồ vật Tính đơn giá cho các loại đồ vật: 67 Tên đồ vật Trọng lượng Giá trị Đơn giá A 15 30 2 B 10 25 2,5 C 2 2 1 D 4 6 1,5 Hình 3.2. Đơn giá của 4 loại đồ vật Sắp xếp các loại đồ vật này theo thứ tự đơn giá giảm dần ta có bảng sau: Tên đồ vật Trọng lượng Giá trị Đơn giá B 10 25 2,5 A 15 30 2 D 4 6 1,5 C 2 2 1 Hình 3.3. Các đồ vật theo đơn giá giảm dần Theo đó thì thứ tự ưu tiên để chọn đồ vật là B, A, D, C. Vật B được xét đầu tiên và ta chọn tối đa 3 cái vì mỗi cái vì trọng lượng mỗi cái là 10 và ba lô có trọng lượng 37. Sau khi đã chọn 3 vật loại B, trọng lượng còn lại trong ba lô là 37 - 3*10 = 7. Ta xét đến vật A, vì A có trọng lượng 15 mà trọng lượng còn lại của balô chỉ còn 7 nên không thể chọn vật A. Xét vật D và ta thấy có thể chọn 1 vật D, khi đó trọng lượng còn lại của ba lô là 7-4 = 3. Cuối cùng ta chọn được một vật C. Như vậy chúng ta đã chọn 3 cái loại B, một cái loại D và 1 cái loại C. Tổng trọng lượng là 3*10 + 1*4 + 1*2 = 36 Tổng giá trị là 3*25+1*6+1*2 = 83. Thuật toán giải bài toán cái ba lô bằng kĩ thuật tham lam như sau: Tổ chức dữ liệu: - Mỗi đồ vật được biểu diễn bởi một mẩu tin có các trường: • Ten: Lưu trữ tên đồ vật. • Trong_luong: Lưu trữ trọng lượng của đồ vật. • Gia_tri: Lưu trữ giá trị của đồ vật 68 • Don_gia: Lưu trữ đơn giá của đồ vật • Phuong_an: Lưu trữ số lượng đồ vật được chọn theo phương án. - Danh sách các đồ vật được biểu diễn bởi một mảng các đồ vật. Thuật toán: input: mảng dsdv mà các trường Ten, Trong_luong, Gia_tri, Don_gia đã có giá trị. ouput: Phương án chọn đồ vật - được thể hiện ở giá trị của các trường Phuong_an của các đồ vật Hàm Chon(d,S) cho số lượng đồ vật có trọng lượng d được chọn, S là trọng lượng còn có thể cho thêm của ba lô. Chon(d,S) { i=0; while(S>d) { i++; S=S-d; } return(i); } Hàm Dovat(dsdv,W) tìm ra phương án chọn đồ vật Dovat(dsdv,W) { /*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/ for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(dsdv[i].don_gia<dsdv[j].don_gia) { tg=dsdv[i]; dsdv[i]=dsdv[j]; dsdv[j]=tg; 69 } /* Xây dựng phương án*/ for(i=1;i<=n-1;i++) { Dsdv[i].Phuong_an:= Chon(dsdv[i].Trong_luong, W); W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong; } } Trong trường hợp trọng lượng của các vật và W là các số nguyên thì ta bỏ hàm Chon(d,S) và khi đó thuật toán sẽ là: Dovat(dsdv,W) { /*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/ for(i=1;i<=n-1;i++) for(j=i+1;j<=n;j++) if(dsdv[i].don_gia<dsdv[j].don_gia) { tg=dsdv[i]; dsdv[i]=dsdv[j]; dsdv[j]=tg; } /* Xây dựng phương án*/ for(i=1;i<=n-1;i++) { Dsdv[i].Phuong_an:= W/dsdv[i].Trong_luong; W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong; } } 3) Đánh giá độ phức tạp tính toán của thuật toán Trong thuật toán Dovat(dsdv,W) ta phải sắp xếp mảng dsdv, công việc này 70 mất thời gian O(n2). Tiếp theo là công việc xây dựng phương án chọn đồ vật. Công việc này được thực hiện bởi vòng lặp for(i=1;i<=n-1;i++), vòng lặp được thực hiện n lần, mỗi lần lặp lại gọi hàm Chon(dsdv[i].Trong_luong, W). Trong hàm Chon(dsdv[i].Trong_luong, W) có vòng lặp while thực hiện nhiều nhất là n phép so sánh. Do đó công việc xây dựng phương án chọn đồ vật mất thời gian O(n2). Vậy độ phức tạp tính toán của thuật toán là O(n2). 3.2.3. Bµi to¸n t« mµu b¶n ®å 1) Bài toán Hãy dùng số màu ít nhất để tô màu cho một bản đồ với điều kiện: mỗi quốc gia được tô một màu và hai quốc gia kề nhau (có chung đường biên giới ) thì phải có màu khác nhau. Ta xây dựng một đơn đồ thị vô hướng: Mỗi quốc gia tương ứng với một đỉnh của đồ thị, hai quốc gia kề nhau thì hai đỉnh tương ứng kề nhau (có cạnh nối giữa chúng). Khi đó bài toán đã cho sẽ chính là bài toán: Hãy dùng số màu ít nhất để tô màu cho các đỉnh của một đơn đồ thị vô hướng sao cho hai đỉnh kề nhau phải có màu khác nhau. (Bài toán tô màu đồ thị) 2) Thiết kế thuật toán Có nhiều kỹ thuật được sử dụng để thiết kế thuật toán giải bài toán tô màu đồ thị và tìm được phương án tối ưu với thời gian hàm mũ. Ở đây chúng ta sẽ thiết kế thuật toán giải bài toán này theo tinh thần của kỹ thuật tham lam: kết quả có thể chỉ là một phương "tốt" chứ chưa đảm bảo là tối ưu nhưng thời gian là có thể chấp nhận được. Trước hết ta định nghĩa bậc của một đỉnh là số đỉnh trên đồ thị chưa được tô mầu mà đỉnh này được nối trực tiếp với đỉnh đang xét bằng một cạnh nối trực tiếp. Nếu đỉnh đó không được nối với bất kỳ đỉnh nào thì bậc của đỉnh đó là 0 -Bước 1 : Tìm đỉnh có bậc cao nhất trên đồ thị ( gọi là đỉnh u ) -Bước 2 : Tăng số màu cần tô lên 1 và tô màu cho đỉnh vừa tìm -Bước 3 : Tìm đỉnh v để tô màu giống u thỏa mãn các điều kiện sau : v đi đến đỉnh u thông qua duy nhất 1 đỉnh w khác và v có số bậc lớn nhất. Nếu không tìm được đỉnh như vậy ta sẽ tìm đỉnh v có bậc lớn nhất mà không kề với u. Nếu tìm được v thỏa mãn thì ta tô màu cho v chính là màu của đỉnh u. Sau đó nhập đỉnh u và 71 v vào làm 1 đỉnh. Tức : đỉnh w kể với v thì cũng coi như kề với u ( a[v,w] =1 thì a[u,w] =1 and a[w,u] = 1 ) -Bước 4 : Lập lại bước 3 cho đến khi v = 0. -Bước 5 : Lặp lại bước 1 cho đến khi tô hết mầu các đỉnh của đồ thị. Tổ chức dữ liệu: somau: Lưu trữ số màu cần tô n : Số đỉnh của đồ thị color : Mảng lưu màu của đỉnh đồ thị, color [i] = 0 nghĩa là đỉnh i chưa được tô màu a : ma trận kề - a[u,v] = 1 tức hai đỉnh u và c có cạnh nối, a[u,v] = 0 tức hai đỉnh không có cạnh nối count : Đếm số đỉnh đã tô màu ,Count = n: dừng Thuật toán Thuật toán được xây dựng qua các hàm sau: - dinh_bac_max(): Hàm tìm ra đỉnh có bậc lớn nhất - tomau(u ): tô màu cho đỉnh u - tim_dinh_cung_mau(u, v): tìm đỉnh v để tô màu cùng với màu đinh u - Nhapdinh(u,v): u,v được tô cùng màu thì các đỉnh kề với v được coi như kề với u. - main() Các hàm: dinh_bac_max () { max := -1;//Vi co the co dinh co bac la 0 for(i=1;i<=n;i++) if (color[i] == 0) /*Xét các đỉnh chưa được tô màu để tìm ra đỉnh bậc lớn nhất*/ { dem = 0; for(j=1;j<=n;j++) 72 if ((color[j] == 0) && (a[i][j] == 1)) dem++; if (dem > max) //Cập nhật giá trị lớn nhất { max = dem; u = i; } } return(u); } tomau(u); { count = count + 1; color[u] = somau; } tim_dinh_cung_mau(u, v ) { max = 0; for(i=1;i<=n;i++) if (color[i] == 0) && (a[u][i] == 0)) /* Xét các đỉnh mà u không kề mà đi đến u qua duy nhất 1 đỉnh khác */ { dem = 0; for(j=1;j<=n;j++) if (color[j] == 0) && (a[i][j] == 1) && (a[u][j] == 1)) dem++; if (dem > max) then // Cập nhật giá trị max { max = dem; 73 v = i; } } if (v > 0) return; /*Nếu tồn tại v chưa tô màu đi đến được u thông qua duy nhất 1 đỉnh khác*/ max = -1; // vì có thể tồn tại v mà bậc chỉ là 0 for(i=1;i<=n;i++) if (color[i] == 0) &&(a[u][i] ==0)) { dem = 0; for(j=1;j<=n;j++) if ((color[j] == 0) and (a[i][j] == 1)) dem++; if (dem > max) { max = dem; v = i; } } } Nhapdinh(u,v) { for(i=1;i<=n;i++) if (a[v,i] == 1) { a[u,i] = 1; a[i,u] = 1; } } 74 main() { somau = 0; do somau = somau+1; u = dinh_bac_max; tomau(u); do tim_dinh_cung_mau(u,v); /* Tìm đỉnh v có thể tô màu giống mầu của u*/ if (v > 0) { tomau(v); nhap_dinh(u,v); } while (v == 0); while (count == n); } 3) Đánh giá độ phức tạp tính toán của thuật toán Trong hàm main() có hai vòng lặp do ... while lồng nhau, mỗi vòng lặp thực hiện nhiều nhất n lần. Trong hai vòng lặp này có lời gọi hàm tim_dinh_cung_mau(u,v), trong hàm này phép toán tích cực là phép so sánh (có thời gian O(1)) được đặt trong hai vòng lặp lồng nhau là for(i=1;i<=n;i++) và for(j=1;j<=n;j++). Vậy độ phức tạp của thuật toán là O(n4) 3.2.4. Tìm cây khung nhỏ nhất 1) Bài toán Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = { 1,2,,n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số không âm c(e), gọi là độ dài của nó. Giả sử T =(V, ET) là cây khung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài của các cạnh của nó: 75 Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất. Để giải bài toán cây khung nhỏ nhất, tất nhiên có thể liệt kê tất cả các cây khung của đồ thị và chọn trong số chúng cây khung nhỏ nhất. Phương pháp như vậy, trong trường hợp đồ thị đầy đủ, sẽ đòi hỏi thời gian cỡ nn-2 , và rõ ràng không thể thực hiện được ngay cả với những đồ thị với số đỉnh cỡ hàng chục. Rất may đối với bài toán cây khung nhỏ nhất chúng ta đã có những thuật toán rất hiệu quả để giải chúng .Chúng ta sẽ xét một trong số những thuật toán như vậy, đó là thuật toán Prim 2) Thuật toán Prim Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất, phương pháp này sử dụng kỹ thuật tham lam. Cụ thể, bắt đầu từ một đỉnh nào đó tuỳ ý của đồ thị chẳng hạn là đỉnh s, đầu tiên ta nối s với đỉnh lân cận có độ dài nhỏ nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các đỉnh kề của đỉnh s, cạnh(s,y) có độ dài nhỏ nhất. Tiếp theo, trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm ba đỉnh và hai cạnh. Quá trình này sẽ được tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh, đó chính là cây khung nhỏ nhất cần tìm. Giả sử đồ thị cho bởi ma trận trọng số C= { c[i,j] i,j =1, 2,, n} với qui ước c[x, x] = 0 và c[x,y] =  nếu không có cạnh (x,y). Trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của một đỉnh x sẽ gồm hai thành phần và có dạng [ ax, bx], trong đó thành phần ax ghi nhận đỉnh của cây khung gần x nhất (cây khung đang xây dựng) còn thành phần bx dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối đỉnh x với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh x đến tập đỉnh của cây khung), tức là: bx = min { c[x,y]: y  VT } (VT là tập các đỉnh của cây khung đang xây dựng). Các nhãn sẽ được chỉnh dần trong một quá trình lặp. Tại mỗi bước lặp tìm được một đỉnh có nhãn “tốt nhất” để bổ sung vào cây khung. Đỉnh đã được chọn bổ sung vào    TEe ecTc )()( 76 cây khung sẽ không được tham gia chỉnh nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi tập VT có n phần tử. Thuật toán Prim được thể hiện nhu sau: CKNN() { // khởi tạo //Chọn s là một đỉnh nào đó của đồ thị VT={s}; ET=; bs=0; as=s; for (x  V \ VT) { ax = s; bx= c[s,x]; } kt=1; while(kt) { // tìm đỉnh có nhãn “tốt nhất” bổ sung vào cây khung p=v; //v là một đỉnh thuộc V\VT for (x  V \ VT) if(bx<bp) p=x; VT =VT  {p}; ET=ET{(p, ap)}; if (VT==n) { T= (VT, ET) là cây khung nhỏ nhất của đồ thị; kt=0; } else /* chỉnh nhãn */ 77 for (x V\VT) if (bx > c[p, x]) { bx:=c[p, x]; ax:=p; } } } 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 so sánh (bx<bp) khi tìm đỉnh có nhãn tốt nhất để bổ sung vào cây khung. Phép so sánh nằm trong vòng lặp for (x V\VT), vòng lặp này thực hiện nhiều nhất (n-1) lần. Vòng lặp for (x V\VT) nằm trong vòng lặp while(kt) có số lần thực hiện nhiều nhất (n-1) lần. Vậy độ phức tạp tính toán của thuật toán là O(n2) 3.2.5. Tìm đƣờng đi ngắn nhất 1) Bài toán Cho đồ thị có hướng (hoặc vô hướng) G=(V,E), V =n, E =m với các cạnh được gán trọng số, nghĩa là, mỗi cạnh (u,v)  E được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. ở đây ta chỉ xét đồ thị có trọng số của các cạnh là không âm. Chúng ta sẽ đặt a(u,v) =, nếu (u,v) E. Nếu dãy v0, v1, ... , vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau    p i ii vva 1 1 ),( (nếu chúng ta gán trọng số cho tất cả các cạnh đều bằng 1, thì ta thu được định nghĩa độ dài của đường đi như là số cạnh của đường đi). Bài toán tìm đường đi ngắn nhất trên đồ thị có thể phát biểu như sau: Tìm đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát sV đến đỉnh cuối cùng (đích) t  V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t. 78 Ta sẽ xem xét việc giải quyết bài toán này bằng thuật toán Dijkstra và xem xét tính chất tham lam trong thuật toán. 2) Thuật toán Dijkstra Thuật toán Dijkstra giải bài toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. Nhãn của một đỉnh x sẽ gồm hai thành phần và có dạng [ax, bx], trong đó thành phần ax chỉ đỉnh đi trước x trong đường đi còn thành phần bx là cận trên của độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn của các đỉnh sẽ được chỉnh dần trong một quá trình lặp. Cứ mỗi bước lặp sẽ có có một nhãn tạm thời được chọn làm nhãn cố định. Khi đỉnh x có nhãn trở thành cố định thì bx sẽ là độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn đã được cố định sẽ không tham gia sửa nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi nhãn đỉnh t được chọn làm nhãn cố định. Khi đó bt là độ dài đường đi nhắn nhất từ đỉnh s đến đỉnh t và đường đi là: s ->...->at->t. Thuật toán input: Đồ thị G = (V,E) với n đỉnh, ma trận trọng số C với c(u,u)=0, c(u,v) =, nếu (u,v) E. s V là đỉnh xuất phát, t V là đỉnh đích output: Độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh t. Dijkstra(c,s,t) { /* khởi tạo */ for x V do { bx= c[s,x]; ax=s; } U:= V\{s}; /* U là tập các đỉnh có nhãn tạm thời*/ p=s; while (p  t) { p=v; //v là một đỉnh thuộc U 79 for (x  U) if(bx<bp) p=x; U = U \ {p} ; /* Cố định nhãn đỉnh p */ for (x  U) /* Gán lại nhãn các đỉnh trong U */ if (bx >bp + c[p,x] ) { bx = bp + c[p,x] ax= p; } } } Kỹ thuật tham lam thể hiện trong thuật toán: tại mỗi bước lặp sẽ chọn một nhãn tạm thời làm nhãn cố định: Tìm đỉnh p U thoả mãn bp = min{ bu : u  U}; 3) Độ phức tạp tính toán của thuật toán Ở mỗi bước lặp để tìm ra đỉnh p cần phải thực hiện O(n) phép toán, và để gán nhãn lại cũng cần phải thực hiện một số lượng phép toán cũng là O(n). Thuật toán phải thực hiện n-1 bước lặp, vậy thời gian tính toán của thuật toán là O(n2). Trong thuật toán ta coi phép toán tích cực là phép so sánh (bx<bp) khi tìm đỉnh để cố định nhãn. Phép so sánh nằm trong vòng lặp for (xU), vòng lặp này thực hiện nhiều nhất (n-1) lần. Vòng lặp for (xU) nằm trong vòng lặp while (p t) có số lần thực hiện nhiều nhất (n-1) lần. Vậy độ phức tạp tính toán của thuật toán là O(n2) 3.2.6. Bµi to¸n ph©n c«ng c«ng viÖc 1) Bài toán Cần gia công m chi tiết máy J1, J2,...,Jm. Có n máy gia công giống nhau là P1, P2, ...Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị cắt ngang. Ðể gia công một chi tiết Ji trên một máy bất kỳ ta cần dùng một thời gian tương ứng là ti. Hãy phân công công việc cho các máy sao cho thời gian 80 gia công xong toàn bộ m chi tiết là ít nhất. 2) Thiết kế thuật toán Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 chi tiết với thời gian gia công là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Ta có một phương án phân công (L) như hình sau : Hình 3.4. Phương án phân công L Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên mình...Sơ đồ phân việc theo hình ở trên được gọi là lược đồ Gantt. Theo lược đồ này, ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách cảm tính ta thấy rằng phương án (L) vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rỗi. Xây dựng một thuật toán để tìm một phương án tối ưu cho bài toán này là một bài toán khó, đòi hỏi các kỹ thuật phức tạp mà chúng ta sẽ không đề cập ở đây. Bây giờ ta xét đến một thuật toán được thiết kế theo tinh thần của kỹ thuật tham lam để giải bài toán này mà kết quả là ta được một phương án tốt chứ chưa chắc đã là tối ưu. Ý tưởng: 1. Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công. 2. Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất. Thuật toán: - Mảng T lưu trữ thời gian gia công các chi tiết. - Mảng TT lưu trữ thứ tự các chi tiết: TT[i]=j là chi tiết j có thứ tự i. j3=8 j6=1 j4=1 j1=2 j5=5 j2=5 P2 P3 P1 81 - Mảng TG lưu trữ thời gian gia công các chi tiết cho từng máy theo phân công. Ban đầu TG[i]=0 với 1 i  n. Phancong(n,m) { // Khởi tạo mảng TG và TT for(i=1;i<=n;i++) TG[i]=0; for(i=1;i<=m;i++) TT[i]=i; // Sắp xếp mảng TT theo chiều giảm dần của thời gian gia công for(i=1;i<=m;i++) for(j=i+1;j<=m;j++) if(T[i]<T[j]) { tg=TT[i]; TT[i]=TT[j]; TT[j]=tg; } // Phân công công việc min=0; for(i=1;i<=m;i++) { j=1; while(TG[j]!=min) j++; Phân chi tiết TT[i] cho máy j; TG[j]=TG[j]+T[TT[i]]; min=TG[1] ; for(j=1;j<=n;j++) if (TG[j]<min) min=TG[j]; } } 82 Với bài toán cụ thể trên theo thuật toán này ta sẽ có một phương án L* như sau : Hình 3.5. Phương án L* Dễ nhận thấy rằng phương án L* vừa tìm được cũng chính là phương án tối ưu vì thời gian hoàn thành là 8, đúng bằng thời gian gia công của chi tiết J3. Tuy nhiên ta biết rằng thuật toán này chỉ cho kết quả là một phương án "tốt", không có gì đảm bảo rằng phương án đó là phương án tối ưu. Trường hợp trên có thể coi là một trường hợp "may mắn". Để thấy điều này ta xét ví dụ sau: Ví dụ 3.2. Có 2 máy P1, P2 và 5 chi tiết j1, j2, j3, j4, j5 với thời gian gia công là: t1=3, t2=3, t3=2, t4=2, t5=2. Khi đó phương án tìm được theo thuật toán có thời gian gia công xong các chi tiết là 7, trong khi đó thời gian gia công xong 5 chi tiết đã cho theo phương án tối ưu là 6. Đièu này được minh hoạ trong hình dưới đây: j6=1 j4=1 j1=2 j5=8 j2=5 j3=8 P2 P3 P1 j5=2 j1=3 j4=2 j2=3 j3=2 P2 P1 Hình 3.6. Phương án tìm được theo thuật toán j5=2 j1=3 j4=2 j3=3 j2=3 P2 P1 Hình 3.7. Phương án tối ưu 83 Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật toán đưa ra và T o là thời gian tối ưu thì người ta đã chứng minh được rằng: n3 1 3 4 T T 0 *  Với kết quả này, ta có thể xác lập được sai số mà chúng ta gặp phải nếu dùng thuật toán thay vì tìm một lời giải tối ưu. Chẳng hạn với số n=2 ta có: 6 7 T T 0 *  và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này, số máy càng lớn thì sai số càng lớn. Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, sai số tối đa sẽ là 4/3T o, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật toán thiết kế theo kỹ thuật tham lam trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt. 3) Đánh giá độ phức tạp tính toán của thuật toán Ta có thể coi phép toán tích cực trong thuật toán là phép so sánh: if (TG[i]<min) Phép so sánh này nằm trong vòng lặp for(j=1;j<=n;j++) nên được thực hiện n lần. Vòng lặp for(i=1;i<=n;i++) được đặt trong vòng lặp for(i=1;i<=m;i++) do vậy phép toán tích cực if (TG[i]<min) được thực hiện n.m lần. Do vậy độ phức tạp tính toán của thuật toán là O(n.m). 84 Bµi tËp ch-¬ng 3 1.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, một giá trị vi và số lượng là si. Dùng kỹ thuật tham lam tìm một cách lựa chọn các đồ vật đựng vào ba lô sao cho tổng giá trị các đồ vật được đựng trong ba lô là lớn nhất. 2. Tìm số màu ít nhất để tô cho các đỉnh của các đồ thị sau sao cho không có hai đỉnh nào kề nhau được tô cùng một màu: a. Đồ thị vô hướng đầy đủ Kn. b. Đồ thị vòng tròn Cn c. Đồ thị bánh xe Wn d. Đồ thị phân đôi đầy đủ Kn,m 3. Xếp lịch thi Một trường đại học tổ chức học theo tín chỉ. Nếu sinh viên tích lũy đủ số chứng chỉ cho một số môn quy định của một ngành là có quyền nhận bằng tốt nghiệp của ngành đó. Đối với các đại học như thế, việc học và thi không tổ chứa theo lớp mà theo các môn học. Hàng năm nhà trường thông báo các môn sẽ học để sinh viên tự đăng ký học các môn học theo ngành mình chọn. Cuối năm nhà trường tổ chức thi cho các môn đã giảng trong năm. Mỗi môn thi trong một ngày nhưng trong một ngày có thể tổ chức thi nhiều môn. Do một sinh viên có thể đăng ký thi nhiều môn nên lịch thi cần phải bố trí để nếu có một sinh viên đăng ký thi hai môn nào đó thì các môn đó không được thi cùng ngày. Dùng kỹ thuật tham lam thiết kế lịch thi sao cho tổng số ngày thi càng ít càng tốt. Hướng dẫn: Đưa bài toán về bài toán tô màu đồ thị. Ta xây dựng đồ thị như sau : + Mỗi đỉnh của đồ thị là một môn học + Hai đỉnh của đồ thị được gọi là có cạnh nối nếu có ít nhất một sinh viên tham gia học 2 môn đó. Như vậy ta xây dựng được một đồ thị vô hướng N đỉnh, trong đó a[i,j] = 1 nếu có cạnh nối, a[i,j] = 0 nếu không có cạnh nối. Sau khi xây dựng được đồ thị trên ta áp dụng thuật toán tô màu đồ thị . Ta sẽ tìm ra 85 được kết quả (số ngày ít nhất cần tổ chức thi ). 4. Bài toán trả tiền của máy rút tiền tự động ATM. Trong máy rút tiền tự động ATM, ngân hàng đã chuẩn bị sẵn các loại tiền có mệnh giá 100.000 đồng, 50.000 đồng, 20.000 đồng và 10.000 đồng. Giả sử mỗi loại tiền đều có số lượng không hạn chế. Khi có một khách hàng cần rút một số tiền n đồng (tính chẵn đến 10.000 đồng, tức là n chia hết cho 10000). Hãy dùng kỹ thuật tham lam xây dựng thuật toán tìm phương án trả tiền sao cho trả đủ n đồng và số tờ giấy bạc phải trả càng ít càng tốt. Đánh giá độ phức tạp tính toán của thuật toán. Hướng dẫn: Gọi X = (X1, X2, X3, X4) là một phương án trả tiền, trong đó X1 là số tờ giấy bạc mệnh giá 100.000 đồng, X2 là số tờ giấy bạc mệnh giá 50.000 đồng, X3 là số tờ giấy bạc mệnh giá 20.000 đồng và X4 là số tờ giấy bạc mệnh giá 10.000 đồng. Theo yêu cầu ta phải có X1 + X2 + X3 + X4 nhỏ nhất và X1 * 100.000 + X2 * 50.000 + X3 * 20.000 + X4 * 10.000 = n. Áp dụng kĩ thuật tham lam để giải bài toán này là: để có số tờ giấy bạc phải trả (X1 + X2 + X3 + X4) nhỏ nhất thì các tờ giấy bạc mệnh giá lớn phải được chọn nhiều nhất. Trước hết ta chọn tối đa các tờ giấy bạc mệnh giá 100.000 đồng, nghĩa là X1 là số nguyên lớn nhất sao cho X1 * 100.000 ≤ n. Tức là X1 = n DIV 100.000. Chảng hạn khách hàng cần rút 1.290.000 đồng (n = 1290000), phương án trả tiền như sau: X1 = 1290000 DIV 100000 = 12. Số tiền cần rút còn lại là 1290000 – 12 * 100000 = 90000. X2 = 90000 DIV 50000 = 1. Số tiền cần rút còn lại là 90000 – 1 * 50000 = 40000. X3 = 40000 DIV 20000 = 2. Số tiền cần rút còn lại là 40000 – 2 * 20000 = 0. X4 = 0 DIV 10000 = 0. Ta có X = (12, 1, 2, 0), tức là máy ATM sẽ trả cho khách hàng 12 tờ 100.000 đồng, 1 tờ 50.000 đồng và 2 tờ 20.000 đồng. 5. Chỉ ra việc sử dụng kỹ thuật tham lam trong thuật toán Kruskal giải bài toán cây khung nhỏ nhất và đánh giá độ phức tạp tính toán của thuật toán.