Bài giảng Phân tích và thiết kế thuật toán - Phạm Thế Bảo - Chương 8: Chia để trị Divide and conquer

14/04/2008
1
CHIA ĐỂ TRN 
DIVIDE AND CONQUER
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung
• Kỹ thuật quan trọng, được áp dụng rộng rãi để
thiết kế các giải thuật có hiệu quả.
• Để giải quyết một bài toán kích thước n, ta chia
bài toán này thành một số bài toán con có kích
thước nhỏ hơn. Giải các bài toán con này rồi tổng
hợp kết quả lại để được lời giải ban đầu.
• Những bài toán con này cũng có thể được chia
thành các bài toán có kích thước nhỏ hơn nữa để
giải quyết. Quá trình này sẽ đưa đến những bài
toán mà lời giải là hiển nhiên hay dễ dàng thực
hiện. Ta gọi những bài toán này là bài toán cơ sở.
Phạm Thế Bảo
14/04/2008
2
Một số bài toán tiêu biểu
• MergeSort và QuickSort
ố• Nhân s nguyên lớn
• Xếp lịch thi đấu thể thao
• Bài toán con cân bằng
• …
Phạm Thế Bảo
MergeSort và QuickSort
• Chia tập dữ liệu làm 2 tập con, quá trình chia
đế khi hỉ ò 01 hầ tử Æ dừ (bài t án c c n p n ng o n
cơ sở), tổng hợp 2 tập con bằng cách trộn có
thứ tựÆ tập dữ liệu được sắp xếp.
• Giống MergeSort nhưng cần phần tử cầm canh
đứng giữa để chia thành 2 tập con: một tập sẽ
có các phần tử có giá trị nhỏ hơn hay bằng, tập
còn lại sẽ có các phần tử có giá trị lớn hơn.
Phạm Thế Bảo
14/04/2008
3
Bài toán nhân hai số nguyên lớn
• Trong các ngôn ngữ lập trình, kiểu dữ liệu số
nguyên đều có miền giá trị hạn chế,
ví dụ: Pascal, C số nguyên từ -32768 đến 32767
• Khi gặp ứng dụng cần số nguyên lớn hơn
(hàng chục hay hàng trăm chữ số), chúng ta
phải đi xây dựng cấu trúc dữ liệu số nguyên
lớn Các thao tác đi kèm là: cộng trừ nhân. , , , …
• Chúng ta xem xét cách nhân 02 số nguyên lớn
có n chữ số sao cho hiệu quả.
Phạm Thế Bảo
• Nếu chúng ta dùng cách nhân thông thường,
nghĩa là từng chữ số nhân với nhau rồi cộng lại
thì chi phí là O(n2).
• Áp dụng kỹ thuật chia để trị. Ta chia 02 số
nguyên X, Y thành các số nguyên lớn có n/2
chữ số: X=A10n/2+B và Y=C10n/2+D
Ví dụ: A=1234 thì A=12x102 +34
Khi đó X.Y = AC10n+(AD+BC)10n/2+BD.
Giố h ê l i hi iế để ó bàing n ư tr n ta ạ c a t p tục c
toán cơ sở dễ dàng thực hiện.
Phạm Thế Bảo
14/04/2008
4
• Theo cách làm trên thì phải thực hiện 4 phép
nhân các số nguyên lớn n/2 chữ số (AC, AD,
BC, BD), sau đó dùng 3 phép cộng các số
nguyên lớn n chữ số và 2 phép nhan với 10n và
ể ổ10n /2 đ t ng hợp.
• Phép cộng số nguyên lớn cần O(n), phép nhân
10n có thể thực hiện đơn giản bằng cách thêm
n chữ số 0 Æ cũng cần O(n). Gọi T(n) là thời
gian nhân hai số nguyên lớn ta có phương,
trình đệ quy:
Phạm Thế Bảo
• Giải phương trình ta có T(n) =
Æ không cải thiện!
• Viết lại: 
X Y AC10n+[(A B)(D C)+AC+BD]10n/2+BD. = - -
Công thức này chỉ cần tính 3 phép nhân của các
số nguyên lớn n/2 chữ số: AC,BD và (A-B)(D-
C), 6 phép cộng trừ và 2 phép nhân với 10n. 
Lập luận tương tự ta có phương trình đệ quy:
T(1)=1
T(n)=
Phạm Thế Bảo
Nghiệm?
14/04/2008
5
Nghiệm của phương trình T(n)=
Æ cải thiện hơn.
Thuật giải thô:
longDigit multi2Integer(longDigit X, longDogit Y, int n){
if( 1) th t X*Yn= en re urn ;
A=left(X,n/2);
B=right(X,n/2);
C=left(Y,n/2);
D=right(Y,n/2);
m1=multi2Integer(A,C,n/2);
2 lti2I t (A B D C /2)m =mu n eger - , - ,n ;
m3=multi2Integer(B,D,n/2);
return (m1*10n +(m1+m2+m3)*10n/2 +m3);
}
Phạm Thế Bảo
Xếp lịch thi đấu thể thao
• Xét việc xếp lịch thi đấu vòng tròn một lượt
cho n đội đá banh Mỗi đội thi đấu với nhau. ,
mỗi đội chỉ đấu nhiều nhất một trận một ngày.
Làm sao ta xếp lịch thi đấu cho số ngày ít nhất.
• Ta có tổng số trận đấu của toàn giải là
nếu n chẵn thì ta có thể sắp n/2 cặp thi đấu
ộ à Æ ầ í hấ ( 1) à Nếtrong m t ng y c n t n t n- ng y. u
n lẻ thì ta có thể sắp (n-1)/2 cặp thi đấu trong
một ngàyÆ cần ít nhất n ngày
Phạm Thế Bảo
14/04/2008
6
• Lịch thi đấu là một bảng n dòng và n-1 cột và được
đánh số tứ 1 trở đi, dòng i đại diện cho đội thứ i và cột j
đại diện cho ngày thi đấu j, ô(i,j) ghi đội phải thi đấu
với đội i trong ngày j.
• Dùng chiến lược chia để trị: để sắp lịch cho n đội, ta
sắp cho n/2 đội, để sắp lịch cho n/2 đội ta sắp lịch cho
ắ ấn/4 đội, … Æ s p lịch thi đ u cho 2 đội (bài toán cơ
sở).
• Từ lịch thi đấu của 2 đội, chúng ta sắp lịch thi đấu cho
4 đội như sau:
– Lịch thi đấu cho 4 đội là một bảng 4 dòng 3 cột.
– Lịch thi đấu cho 2 đội 1 và 2 trong ngày 1 chính là lịch thi
đấu của 2 đội (bài toán cơ sở) Vậy ô(1 1)=2 ô(2 1)=1. , , , .
Tương tự cũng có lịch thi đấu cho 2 đội 3 và 4 trong ngày
1: ô(3,1)=4 và ô(4,1)=3. Ta có thể thấy ô(3,1)=ô(1,1)+2 và
ô(4,1)=ô(2,1)+2.
– Lịch thi đấu của 4 đội, 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. Phạm Thế Bảo
Ngày 1
Đội 1 2
Đội 2 1
Ngày 1 Ngày 2 Ngày 3
Đội 1 2
Đội 2 1
Đội 3 4
Đội 4 3
Ngày 1 Ngày 2 Ngày 3
Đội 1 2 4
Đội 2 1 3
Đội 3 4 2
Đội 4 3 1
Phạm Thế Bảo
Ngày 1 Ngày 2 Ngày 3
Đội 1 2 3 4
Đội 2 1 4 3
Đội 3 4 1 2
Đội 4 3 2 1
14/04/2008
7
Ngày 1 Ngày 2 Ngày 3 Ngày 4 Ngày 5 Ngày 6 Ngày 7
Đội 1 2 3 4
Đội 2 1 4 3
6 7 8
5 8 7
i 5
i 6
Đội 3 4 1 2
Đội 4 3 2 1
Đội 5 6 7 8
Đội 6 5 8 7
Đội 7 8 5 6
Đội 8 7 6 5
8 5 6
7 6 5
2 3 4
1 4 3
4 1 2
3 2 1
i 7
i 8
i 1
i 2
i 3
i 4
Phạm Thế Bảo
Bài tập: cài đặt chương trình
Bài toán con cân bằng
• Với kỹ thuật chia để trị, nếu bài toán ban đầu
đ thà h á bài t á ó kí h th ớ ầược n c c o n con c c ư c g n
bằng nhau thì hiểu suất sẽ cao hơn.
• Ví dụ: MergeSort chia làm 2 tập con bằng
nhau (n/2 phần tử - có thể sai khác 1) thì độ
phức tạp là O . Đối với QuickSort, nếu
phân hoạch không tốt thì độ phức tạp vẫn là
O(n2), trường hợp xấu nhất.
Phạm Thế Bảo