Bài giảng Phân tích và thiết kế thuật giải: Bài 2

PHÂN TÍCH THIẾT KẾ THUẬT GIẢI

CHIẾN LƯỢC CHIA ĐỂ TRỊ

TS. NGÔ QUỐC VIỆT 2015

Nội dung

1. Giới thiệu 2. Các thuật giải chia để trị 3. Bài tập 4. Hỏi đáp.

2 Ngô Quốc Việt

Giới thiệu

 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’.

3 Ngô Quốc Việt

Giới thiệu

 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

4 Ngô Quốc Việt

Giới thiệu

 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)).

5 Ngô Quốc Việt

Minh hoạ với MergeSort

 𝑇(𝑛) là số phép so sánh trong mergesort

6 Ngô Quốc Việt

Minh hoạ với MergeSort

 Dễ dàng chứng minh với cây đệ quy

7 Ngô Quốc Việt

Minh hoạ với MergeSort

 Chứng minh bằng quy nạp theo n.

 Đúng với n = 1.  Giả sử:  Chứng minh:

8 Ngô Quốc Việt

Minh hoạ với MergeSort

 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.

9 Ngô Quốc Việt

Bài toán đếm nghịch thế

 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)

10 Ngô Quốc Việt

Bài toán đếm nghịch thế

 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

11 Ngô Quốc Việt

Bài toán đếm nghịch thế

12 Ngô Quốc Việt

Bài toán đếm nghịch thế

 Đếm nghịch thế giữa hai nửa đã được sắp xếp.

13 Ngô Quốc Việt

Bài toán đếm nghịch thế

 Cài đặt

14 Ngô Quốc Việt

Bài toán Subset Sum Recursive

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

15 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 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.

16 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 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

17 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 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, )

1

2

18 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 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

19 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 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).

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 .

20 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

P1 

l P2 

 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 = 𝑂 𝑛

21 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

22 Ngô Quốc Việt

Bài toán tìm cặp điểm gần nhất

 Độ 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.

23 Ngô Quốc Việt

ClosestPair(ptsByX, ptsByY, n)

// Combine

midPoint ptsByX[mid]

if (n = 1) return 1

lrDist min(distL, distR)

if (n = 2) return distance(ptsByX[0], ptsByX[1])

Construct array yStrip, in increasing y order,

of all points p in ptsByY s.t.

// Divide into two subproblems

|p.x − midPoint.x| < lrDist

mid  n/2 -1

copy ptsByX[0 . . . mid] into new array XL in x order.

// Check yStrip

copy ptsByX[mid+1 . . . n − 1] into new array XR

minDist  lrDist

for (j 0; j ≤ yStrip.length − 2; j++) {

copy ptsByY into arrays Y L and Y R in y order, s.t.

k  j + 1

XL and Y L refer to same points, as do XR,Y R.

while (k yStrip.length − 1 and

yStrip[k].y − yStrip[j].y < lrDist) {

// Conquer

d  distance(yStrip[j], yStrip[k])

distL  ClosestPair(XL, Y L, n/2)

minDist  min(minDist, d)

distR  ClosestPair(XR, Y R, n/2)

k++

}

return minDist

Ngô Quốc Việt 24

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

}

25 Ngô Quốc Việt

Nhân hai số nguyên lớn

 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

26 Ngô Quốc Việt

Nhân hai số nguyên lớn

 Tách số I n-chữ số thành hai nửa: 𝐼ℎ, 𝐼𝑙, tương tự số J

thành 𝐽ℎ, 𝐽𝑙

𝑛 2 + 𝐼𝑙 𝐼 = 𝐼ℎ ∗ 10 𝑛 2 + 𝐽𝑙 𝐽 = 𝐽ℎ ∗ 10

𝑛 𝐼 ∗ 𝐽 = 𝐼ℎ ∗ 𝐽ℎ∗ 10𝑛 + 𝐼𝑙 ∗ 𝐽ℎ + 𝐼ℎ ∗ 𝐽𝑙 ∗ 10 2 + 𝐼𝑙 ∗ 𝐽𝑙 + Θ 𝑛 = 𝑂 𝑛2  không  Độ phức tạp: 𝑇 𝑛 = 4𝑇

𝑛 2

cải tiến

27 Ngô Quốc Việt

Nhân hai số nguyên lớn

𝑃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ừ 2 + 𝑂 𝑛 ≈ 𝑂 𝑛𝑙𝑜𝑔23 ≪ 𝑂 𝑛2  𝑇 𝑛 = 3𝑇 𝑛

28 Ngô Quốc Việt

Nhân hai số nguyên lớn

 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

http://en.wikipedia.org/wiki/Karatsuba_algorithm

29 Ngô Quốc Việt

int n = max(number of digits in a, number of digits in 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 số nguyên lớn BigInteger multiply(BigInteger a, BigInteger b) { }

30 Ngô Quốc Việt

Nhân hai ma trận vuông  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

31 Ngô Quốc Việt

Nhân hai ma trận vuông

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

32 Ngô Quốc Việt

• 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

Nhân hai ma trận vuông 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)

33 Ngô Quốc Việt

Bài tập

Thực hành: Cài đặt bài toán tìm cặp điểm gần nhất. Thực hành: Cài đặt bài toán tìm dãy con có tổng bằng T. Thực hành: Cài đặt bài toán tìm cặp điểm gần nhất.

34 Ngô Quốc Việt