Phân tích thiết kế thuật giải - Chiến lược chia để trị

CHIẾN LƯỢC CHIA ĐỂ TRỊ TS. NGÔ QUỐC VIỆT 2015 PHÂN TÍCH THIẾT KẾ THUẬT GIẢI Nội dung Ngô Quốc Việt 2 1. Giới thiệu 2. Các thuật giải chia để trị 3. Bài tập 4. Hỏi đáp. Giới thiệu Ngô Quốc Việt 3  Chia bài toán lớn thành 2 hay nhiều “phần” nhỏ  Giải quyết mỗi phần theo cách đệ quy.  Kết hợp các lời giải “con” để tạo thành lời giải sau cùng.  Thuật giải có tối thiểu hai gọi hàm đệ quy được gọi là chia để trị. Ví dụ: thuật giải mergesort.  Các thuật giải: tính số Fibonacii theo đệ quy (có hai lời gọi đệ quy) nhưng không là chia để trị vì không có bước ‘chia’. Giới thiệu Ngô Quốc Việt 4  MergeSort  Tập con có tổng lớn nhất  Nhân 2 số nguyên lớn  Tìm cặp điểm gần nhất  Thuật giải Strassen - Nhân hai ma trận Giới thiệu Ngô Quốc Việt 5  Chiến lược phổ biến là chia đôi tập dữ liệu n phần tử thành hai tập con kích thước ½ n.  Giải quyết mỗi phần theo đệ quy  Kết hai lời giải con thành lời giải tổng quát với độ phức tạp tuyến tính.  Vét cạn: O(n2)  Chia để trị: O(n.log(n)). Minh hoạ với MergeSort Ngô Quốc Việt 6  𝑇(𝑛) là số phép so sánh trong mergesort )log()( nnOnT  Minh hoạ với MergeSort Ngô Quốc Việt 7  Dễ dàng chứng minh với cây đệ quy Minh hoạ với MergeSort Ngô Quốc Việt 8  Chứng minh bằng quy nạp theo n.  Đúng với n = 1.  Giả sử:  Chứng minh: nnnT 2log)(  )2log2()2( 2 nnOnT  nnTnT 2)(2)2(  nnn 2)(log2 2  nnn 2)1)2((log2 2  )2(log2 2 nn Minh hoạ với MergeSort Ngô Quốc Việt 9  Chứng minh bằng quy nạp theo n.  Đúng với n = 1.  Định nghĩa:  Giả sử đúng với: 1, 2, , n-1.    2/;2/ 21 nnnn  Bài toán đếm nghịch thế Ngô Quốc Việt 10  Yêu cầu cơ bản: đếm nghịch thế trong một dãy.  Yêu cầu nâng cao: đếm sự khác biệt (nghịch thế) giữa hai dãy. Nguyên nhân vì khái niệm “tăng” / ”giảm” do chủ quan.  Thuật giải vét cạn: so sánh từng cặp (hãy trình bày thuật giải) )()( 2nOnT  Bài toán đếm nghịch thế Ngô Quốc Việt 11  Chia để trị:  Chia thành 2 dãy con.  Đếm đệ quy trong từng dãy con.  Kết hợp: tổng nghịch thế của hai dãy con Bài toán đếm nghịch thế Ngô Quốc Việt 12 Bài toán đếm nghịch thế Ngô Quốc Việt 13  Đếm nghịch thế giữa hai nửa đã được sắp xếp.       )log()()(2/2/)( nnOnTnOnTnTnT  Bài toán đếm nghịch thế Ngô Quốc Việt 14  Cài đặt Bài toán Subset Sum Recursive Ngô Quốc Việt 15 Cho mảng n phần tử, tìm mảng con các phần tử liên tục sao cho tổng của chúng là lớn nhất (hoặc bằng giá trị T cho trước)  Vét cạn: hai vòng lặp. Vòng lặp ngoài: lấy phần tử đầu, vòng lặp trong: tìm maximum các tổng giữa phần tử đầu của vòng lặp ngoài và các phần tử của lặp trong. Độ phức tạp: 𝑂 𝑛2 .  Chia để trị: độ phức tạp 𝑂 𝑛𝑙𝑜𝑔𝑛  Chia mảng thành hai nửa  Tìm Maximum subarray sum của nửa trái  Tìm Maximum subarray sum của nửa phải  Tìm Maximum subarray sum của subarray giao giữa hai nửa, tính từ chỗ chia Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 16  Cho n điểm trong mặt phẳng, tìm cặp điểm có khoảng cách ngắn nhất so với các cặp khác.  Giải pháp vét cạn: kiểm tra khoảng cách mọi cặp điểm p và q  𝑂(𝑛2).  Giải pháp 1: chia mặt phẳng thành 4 vùng bằng nhau  không đều. Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 17  Chia: tập điểm thành hai nửa S1,S2 sao cho số điểm hai bên bằng nhau.  Trị: Tìm cặp gần nhất trong mỗi nửa.  Kết hợp: tìm cặp gần nhất, mỗi điểm thuộc nửa khác nhau  Vấn đề: cặp gần nhất là một điểm thuộc S1 và điểm thuộc S2  vét cạn mọi cặp có thể  𝑂 𝑛 2 . 𝑂 𝑛 2 = 𝑂(𝑛2) Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 18  Chia tập S thành S1 và S2 dựa trên đường thẳng dọc có hoành độ tại x trung bình.  Tìm đệ quy cặp gần nhất trên S1 và S2.  Giả sử *𝑝1, 𝑝2+ là cặp gần nhất trong S1 và 𝑞, 𝑞2 trong S2.  Đặt 1 = 𝐷(𝑝1, 𝑝2) và 2 = 𝐷(𝑞1, 𝑞2)  Đặt  = min (1, ) S1 l S2 2 1 p1 p2 q2 q1 Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 19  Cải tiến: chỉ xét cặp điểm có khoảng cách nhỏ hơn  = 𝑀𝐼𝑁 của hai cặp điểm đã xét.  Chỉ xét các điểm nằm cách đường L (phân chia) ít hơn  = 𝑀𝐼𝑁. Xét theo tung độ Y.  Sắp tăng dần các điểm thoả đk trên theo tung độ Khoảng cách MIN trong ví dụ này là 12 Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 20  Sắp xếp các điểm trong dải có kích thước 2 tăng dần theo tung độ Y. Với =min(12,21).  ji Nhận xét: gọi si là điểm trong dải 2 có khoảng cách i đến đường L. Nếu Thì, khoảng cách giữa si, sj cũng lớn hơn . Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 21  Có bao nhiêu điểm thuộc hình chữ nhật 𝑅 =   2  Tối đa 8 điểm thuộc các đỉnh hình chữ nhật (vì không thể có hai điểm khác nằm trong hình chữ nhật R).  Nếu cho R chạy dọc trên dải  độ phức tạp là 7 ∗ 𝑂 𝑛/2 = 𝑂 𝑛 P1 l P2 p  S1 S2    R Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 22 Bài toán tìm cặp điểm gần nhất Ngô Quốc Việt 23  Độ phức tạp:  Liệu có thể đạt: 𝑂(𝑛. log (𝑛)).  Có thể: bằng cách không sắp xếp ngay các điểm trong dải 2 mà thực hiện.  Mỗi lần đệ quy trả về hai danh sách: danh sách 1 chứa các điểm xếp theo y. Danh sách kia chứa các điểm sắp theo x.  Sắp xếp bằng cách trộn hai danh sách trên. Ngô Quốc Việt 24 ClosestPair(ptsByX, ptsByY, n) if (n = 1) return 1 if (n = 2) return distance(ptsByX[0], ptsByX[1]) // Divide into two subproblems mid  n/2 -1 copy ptsByX[0 . . . mid] into new array XL in x order. copy ptsByX[mid+1 . . . n − 1] into new array XR copy ptsByY into arrays Y L and Y R in y order, s.t. XL and Y L refer to same points, as do XR,Y R. // Conquer distL  ClosestPair(XL, Y L, n/2) distR  ClosestPair(XR, Y R, n/2) // Combine midPoint ptsByX[mid] lrDist min(distL, distR) Construct array yStrip, in increasing y order, of all points p in ptsByY s.t. |p.x − midPoint.x| < lrDist // Check yStrip minDist  lrDist for (j 0; j ≤ yStrip.length − 2; j++) { k  j + 1 while (k yStrip.length − 1 and yStrip[k].y − yStrip[j].y < lrDist) { d  distance(yStrip[j], yStrip[k]) minDist  min(minDist, d) k++ } } return minDist Ngô Quốc Việt 25 closest_pair(p) { mergesort(p, 1, n) // n is number of points return rec_cl_pair(p, 1, 2) } rec_cl_pair(p, i, j) { if (j - i < 3) { \\ If there are three points or less... mergesort(p, i, j) // based on y coordinate return shortest_distance(p[i], p[i+1], p[i+2]) } xval = p[(i+j)/2].x deltaL = rec_cl_pair(p, i, (i+j)/2) deltaR = rec_cl_pair(p, (i+j)/2+1, j) delta = min(deltaL, deltaR) merge(p, i, j) // merge points based on y coordinate v = vert_strip(p, xval, delta) for k=1 to size(v)-1 for s = (k+1) to min(t, k+7) delta = min(delta, dist(v[k], v[s])) return delta } Nhân hai số nguyên lớn Ngô Quốc Việt 26  Nhân 2 số nguyên có n-chữ số  n phép nhân số n-chữ số với số một chữ số  Cộng n số  số có tối đa 2n chữ số  Độ phức tạp: 𝑂(𝑛2)  Nhân: 𝑛𝑂(𝑛)  Cộng: 𝑛𝑂(𝑛)  Giải pháp chia để trị sẽ giảm độ phức tạp Nhân hai số nguyên lớn Ngô Quốc Việt 27  Tách số I n-chữ số thành hai nửa: 𝐼ℎ, 𝐼𝑙, tương tự số J thành 𝐽ℎ, 𝐽𝑙 𝐼 = 𝐼ℎ ∗ 10 𝑛 2 + 𝐼𝑙 𝐽 = 𝐽ℎ ∗ 10 𝑛 2 + 𝐽𝑙 𝐼 ∗ 𝐽 = 𝐼ℎ ∗ 𝐽ℎ∗ 10 𝑛 + 𝐼𝑙 ∗ 𝐽ℎ + 𝐼ℎ ∗ 𝐽𝑙 ∗ 10 𝑛 2 + 𝐼𝑙 ∗ 𝐽𝑙  Độ phức tạp: 𝑇 𝑛 = 4𝑇 𝑛 2 + Θ 𝑛 = 𝑂 𝑛2  không cải tiến Nhân hai số nguyên lớn Ngô Quốc Việt 28 𝑃1 = 𝐼ℎ + 𝐼𝑙 ∗ 𝐽ℎ + 𝐽𝑙 = 𝐼ℎ ∗ 𝐽ℎ + 𝐼ℎ ∗ 𝐽𝑙 + 𝐼𝑙 ∗ 𝐽ℎ + 𝐼𝑙 ∗ 𝐼𝑙 𝑃2 = 𝐼ℎ ∗ 𝐽ℎ 𝑃3 = 𝐼𝑙 ∗ 𝐽𝑙 𝐼 ∗ 𝐽 = 𝑃2 ∗ 10 𝑛 + 𝑃1 − 𝑃2 − 𝑃3 ∗ 10 𝑛 2 + 𝑃3  Tính mỗi 𝑃2, 𝑃3, cần phép nhân hai số 𝑛/2 chữ số; 𝑃1 cần một phép nhân hai số 𝑛/2 chữ số, hai phép cộng số 𝑛/2 chữ số có độ phức tạp 𝑂 𝑛/2  Tính 𝐼 ∗ 𝐽 cần thêm hai phép cộng, hai phép trừ  𝑇 𝑛 = 3𝑇 𝑛 2 + 𝑂 𝑛 ≈ 𝑂 𝑛 𝑙𝑜𝑔23 ≪ 𝑂 𝑛2 Nhân hai số nguyên lớn Ngô Quốc Việt 29  Ví dụ: nhân 𝐼 = 12345 và 𝐽 = 6789  𝐼 = 12345 = 𝟏𝟐 ∗ 103 + 𝟑𝟒𝟓  𝐽 = 6789 = 𝟔 ∗ 103 + 𝟕𝟖𝟗  𝑃3 = 345 ∗ 789, 𝑃2 = 12 ∗ 6  𝑃1 = 𝟏𝟐 + 𝟑𝟒𝟓 × 𝟔 + 𝟕𝟖𝟗 − 𝑃2 − 𝑃3 = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538  𝐼 ∗ 𝐽 = 72 ∗ 106 + 11538 ∗ 103 + 272205 = 83810205 Nhân hai số nguyên lớn Ngô Quốc Việt 30 BigInteger multiply(BigInteger a, BigInteger b) { int n = max(number of digits in a, number of digits in b) if(n == 1) { return a.intValue() * b.intValue(); } else { BigInteger aR = bottom n/2 digits of a; BigInteger aL = top remaining digits of a; BigInteger bR = bottom n/2 digits of b; BigInteger bL = top remaining digits of b; BigInteger x1 = Multiply(aL, bL); BigInteger x2 = Multiply(aR, bR); BigInteger x3 = Multiply(aL + aR, bL + bR); return x1 * pow(10, n) + (x3 - x1 - x2) * pow(10, n / 2) + x2; } } Nhân hai ma trận vuông Ngô Quốc Việt 31  Chia thành các ma trận con [Strassen -1969]  8 phép nhân, 4 phép cộng ma trận 𝑛/2 ∗ 𝑛/2  Độ phức tạp: 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑂 𝑛2 ≈ 𝑂 𝑛3 X =        2221 1211 aa aa A        2221 1211 bb bb B        2221 1211 cc cc C 2112111111 babac  2212121112 babac  2122112121 babac  2222122122 babac  Nhân hai ma trận vuông Ngô Quốc Việt 32 Tích hai ma trận có thể được tính như sau [Strassen -1969] C00 C01 A00 A01 B00 B01 = * C10 C11 A10 A11 B10 B11 M1 + M4 - M5 + M7 M3 + M5 = M2 + M4 M1 + M3 - M2 + M6 Nhân hai ma trận vuông Ngô Quốc Việt 33 M1 = (A00 + A11)  (B00 + B11) M2 = (A10 + A11)  B00 M3 = A00  (B01 - B11) M4 = A11  (B10 - B00) M5 = (A00 + A01)  B11 M6 = (A10 - A00)  (B00 + B01) M7 = (A01 - A11)  (B10 + B11) • Nếu kích thước ma trân vuông không là 2 lũy thừa giải quyết bằng cách bổ sung thêm các zero. • Số phép nhân: 7 • 𝑇 𝑛 = 7𝑇 𝑛 2 + 𝑂 𝑛2 = 7𝑙𝑜𝑔2𝑛 + 𝑂 𝑛2 = 𝑛𝑙𝑜𝑔27 + 𝑂 𝑛2 ≈ 𝑛2.807 + 𝑂 𝑛2 • Độ phức tạp giảm, nhưng chưa hoàn toàn hiệu quả nên không được dùng Bài tập Ngô Quốc Việt 34 1. Thực hành: Cài đặt bài toán tìm cặp điểm gần nhất. 2. Thực hành: Cài đặt bài toán tìm dãy con có tổng bằng T. 3. Thực hành: Cài đặt bài toán tìm cặp điểm gần nhất.