Chia để trị -- divide and conquer

Chia để trị theo mình là một trong những phương pháp hiệu quả nhất để thiết kế thuật toán. Bài trước chúng ta đã làm quen với Quick Sort, Merge SortLinear Selection sử dụng chia để trị. Bài này khái quát hóa phương pháp và sau đó chúng ta xem xét các ví dụ áp dụng. Nguyên lí của chia để trị gồm hai bước như sau:

Divide and Conquer Principle:

  • Bước 1 (divide): Chia bài toán lớn thành các bài toán con nhỏ hơn
  • Bước 2 (conquer): Gọi đệ quy giải các bài toán con, sau đó dựa trên lời giải của bài toán con để giải bài toán lớn.

 
Cả hai bước đều yêu cầu những kĩ thuật nhất định và phương pháp tốt nhất để có thể áp dụng hai bước vào các bài toán khác nhau là thực hành nhiều. Trong bài này mình sẽ đưa ra các ví dụ minh họa hai bước, và đừng quên xem lại các phương pháp giải hệ thức truy hồi vì nó sẽ là công cụ chính để phân tích thời gian trong bài này. Ngoại trừ tìm kiếm nhị phân, mình không có code để minh họa giả mã cho các bài toán khác. Nếu bạn có, xin email về địa chỉ email trong phần About để chia sẻ cho các bạn đọc khác.
About
Tính lũy thừa

Problem 1: Cho một số nguyên a và một số nguyên n\geq 1. Tính a^n.

 
Phương pháp mà bạn có thể nghĩ ngay tới là sử dụng công thức: a^n = a\cdot a^{n-1}. Ta có giả mã

SLOWPOWER(a,n):
    x \leftarrow a
    for i \leftarrow 2 to n
        x \leftarrow x\cdot a
    return x

 
Thời gian tính của SLOWPOWERO(n). Ok, bây giờ ta áp dụng phương pháp chia để trị để giải bài toán nhanh hơn. Ở đây ta có quan sát:

a^n = a^{\lfloor n/2 \rfloor}\cdot a^{\lceil n/2 \rceil}

Như vậy nếu ta biết a^{\lfloor n/2 \rfloor}a^{\lceil n/2 \rceil} ta có thể tính a^n. Nhận thấy là tính a^{\lfloor n/2 \rfloor}a^{\lceil n/2 \rceil} đều là các bài toán nhỏ hơn vì lũy thừa nhỏ hơn. Như vậy ta có:

FASTPOWER(a,n):
    if n=1
        return a
    else
        x\leftarrow FASTPOWER(a, \lfloor n/2 \rfloor)
        if n is even
            return x\cdot x
        else n
            return x\cdot x\cdot a

 
Như vậy thời gian tính của thuật toán là:

T(n) \leq T(\lfloor n/2 \rfloor) + 2

 
Giải ra ta được T(n) = O(\log n).

Nhân hai số nguyên n bit

Trong phần này ta sẽ thảo luận bài toán sau:

Problem 2: Cho hai số nguyên X,Y, mỗi số có độ dài n bít. Tính tích XY.

 

Như ta đã biết bằng phương pháp đặt tính nhân của cấp 1, ta có thể nhân hai số nguyên n bít bằng O(n^2) phép cộng bit. Trong bài này, mình sẽ giới thiệu phương pháp nhân hai số n bít trong thời gian O(n^{\log_2 3})

Theorem: Tồn tại một thuật toán nhân hai số nguyên n bít X,Y trong thời gian O(n^{\log_2 3}) = O(n^{1.585...})

 

Trước khi đi vào thuật toán, mình giới thiệu câu đố nhân hai số phức của Gauss. Câu đố này sẽ cung cấp tư tưởng chính của thuật toán sẽ trình bày.

Gauss Puzzle: Bạn có hai số phức a + bi, c+di và bạn cần tính (a+bi)(c+di) = (ac-bd) + (ad+bc)i . Giả sử rằng để thực hiện phép nhân, bạn phải trả 100$ và để thực hiện một phép cộng hoặc một phép trừ bạn phải trả 1$. Như vậy nếu thực hiện nhân số phức bằng cách tính tích ac, bd, ad, bc, một phép cộng và một phép trừ, bạn phải trả 402$. Câu hỏi là bạn có thể thực hiện nhân số phức với ít hơn 402$ không?

 
Lời giải là có, và bạn có thể thực hiện nhân hai số phức chỉ với 305$. Cách làm như sau:

\begin{array}{lll} X_1 & = & a + b \\ X_2 & = & c+d \\ X_3 & = & X_1X_2 = ac+ad + bc + bd \\ X_4 & = & ac \\ X_5 & = & bd \\ X_6 & = & X_4-X_5 = ac - bd \\ X_7 & = & X_3 - X_4 - X_5 = bc+ad \end{array}

 
Trở lại với bài toán nhân số nguyên. Để đơn giảm ta giả sử n = 2^k. Hai số nguyên X,Y có thể được viết lại như sau:

\begin{array}{lll} X & = & a2^{n/2} + b \\ Y & = & c2^{n/2}+d \end{array}

 
Trong đó a,b,c,d là các số nguyên n/2 bit.
Hình 1
Như vậy ta có:

XY = (a2^{n/2} + b)(c2^{n/2}+d) = ac2^n + (ad+bc)2^{n/2}  + bd

 
Như vậy để tính XY, ta có thể tính các tích ac, ad, bd, bc, bd và sau đó thực hiện các phép dịch trái (nhân với 2^n tương đương với dịch trái n bít) và cộng. Chú ý là các số a,b,c,d có chiều dài n/2 bít, do đó mất thời gian T(n/2) để thực hiện phép nhân. Như vậy ta có thể tính XY trong thời gian:

T(n) = 4T(n/2) + O(n)

 
Giải công thức truy hồi trên ta được T(n) = O(n^2). Oops! Không nhanh hơn thuật toán nhân cấp 1.

OK. Nếu để ý kĩ ta có thể thấy có sự tương đồng khi tính XY và Gauss Puzzle. Sử dụng phương pháp như của Gauss (bài tập), ta có thể tính ac, ad+bc, bd sử dụng 3 phép nhân hai số n/2 bít và vài phép cộng. Như vậy ta có thể tính X.Y trong thời gian:

T(n) = 3T(n/2) + O(n) = O(n^{\log_2 3})

 
Giả mã của chương trình như sau:

FASTMULT(x,y,n):
    if n=1
        return x\cdot y
    else
        m \leftarrow n/2
        a \leftarrow \lfloor x/2^m \rfloor; b \leftarrow x \mod 2^m
        c \leftarrow \lfloor y/2^m \rfloor; d \leftarrow y \mod 2^m
        e\leftarrow FASTMULT(a,c, m)
        f\leftarrow FASTMULT(b,d, m)
        g\leftarrow FASTMULT(a - b,c -d, m)
        return 2^{n}e + 2^m(e+f-g) + f

 
Thuật toán nhanh nhất hiện tại để nhân hai số nguyên n bít phát minh bới Martin Fürer với thời gian là n\log n 2^{\log^* n} trong đó hàm \log^*n được định nghĩa như sau:
\log^*(n) = \begin{cases} 1, & \mbox{if } n \leq 2 \\ 1 + \log^*(\log n) & \mbox{otherwise}\end{cases}
Ta có thể hiểu hàm \log^* n tăng cực kì chậm. Với n=2^{2^{16}} \simeq 2\cdot 10^{19728}, \log^*(n) = 5.
 
Tìm kiếm nhị phân

Tìm kiếm nhị phân (binary search) là một trong những thuật toán được sử dụng rộng rãi nhất trong thiết kế giải thuật. Bài toán như sau:

Problem 3: Cho một mảng A[1,2,\ldots,n] đã sắp xếp theo chiều tăng dần và một số nguyên a. Tìm vị trí của a trong mảng.

 
Nếu duyệt hết các phần tử của mảng từ đầu đến cuối, ta sẽ mất O(n) để tìm. Tuy nhiên ta có thể lợi dụng tính chất mảng A[1,2,\ldots,n] đã sắp xếp để thiết kế giải thuật tốt hơn:

Theorem: Tồn tại một thuật toán tìm ra một phần tử của mảng A[1,2,\ldots,n] đã sắp xếp có giá trị a trong thời gian O(\log n).

 
Ở đây để đơn giản ta sẽ giả sử mảng A có ít nhất một phần tử có gía trị a. Ý tưởng của tìm kiếm nhị phân khá đơn giản: so sánh a với phần tử A[n/2]. Nếu a < A[n/2], ta tìm kiếm trên A[1,2,\ldots, n/2-1]. Nếu a  data-recalc-dims= A[n/2]" />, ta tìm kiếm trên A[n/2+1,\ldots, n]. Giả mã như sau:

BinarySearch(A[1,2,\ldots,n],a):
    if n=1
        return n
    else
        m \leftarrow \lfloor n/2 \rfloor
        if a < A[m]            return BinarySearch(A[1,2,\ldots,m-1],a)
        else if a  data-recalc-dims= A[m]" />
           return BinarySearch(A[m+1,2,\ldots,n],a)
        else
           return m

 
Code của giả mã bằng C. Code đầy đủ của thuật toán được đính ở cuối bài.

// x, y is the first and last index of array _array
int binary_search(int _array[], int x, int y, int a){
   if(x == y) return x;
   else if( x< y){
        int m = (x+y)/2;
	if(_array[m] < a) {
	        return binary_search(_array, m+1, y, a);
	}else if(_array[m] > a){
		return binary_search(_array, x, m-1, a);
	} else {
		return m;
	}
   }
   return -1;
 }

 
Ta thấy ở mỗi bước tìm kiếm, chúng ta loại bỏ được ít nhất một nửa số phần tử cuả mảng. Như vậy:

T(n) = T(n/2) + O(1) = O(\log n)

Code: binary search

Tham khảo
 
[1] Jeff Erickson. Algorithm Lecture Notes, UIUC.
[2] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. 1st Edition). McGraw-Hill Higher Education, (2008).
[3] Anupam Gupta and John Lefferty. Great Theoretical Ideas in Computer Science Lecture Notes, CMU, 2008.

Bài Tập
 
Bài tập trong phần này được trích từ chapter 2 của cuốn sách Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani.
 
Bài 1 Giả sử ta có một mảng gồm n phần tử và các phần tử có thể trùng nhau. Thiết kế giải thuật loại bỏ tất cả các phần từ trùng nhau (giữ lại một copy) trong thời gian O(n\log n).
 
Bài 2 Giả sử trong bộ nhớ máy tính có một mảng vô hạn các phần tử A[1,2,3,\ldots, \infty] trong đó n phần tử đầu tiên được xắp xếp theo chiều tăng dần và còn lại là \infty. Tuy nhiên, bạn không biết n, nghĩa là bạn không biết trong mảng có bao nhiêu phần tử khác \infty. Mỗi lần bạn truy cập vào một vị trí lớn hơn n thì máy tính sẽ trả lại \infty. Bây giờ bạn có một số nguyên x và muốn tìm vị trí cuả mảng chứa gía trị x. Hãy thiết kế giải thuật tìm vị trí của x trong mảng với thời gian O(\log n).
 
Bài 3 Bạn có một mảng A[1,2,3,\ldots, n] gồm các số nguyên đôi một khác nhau và bạn muốn tìm chỉ số i của mảng sao cho A[i]= i. Hãy thiết kế thuật toán với thời gian O(\log n).

 
Bài 4 (Closest Pair) Cho một tập n điểm trên một mặt phẳng p_1 = (x_1,y_1),p_2 = (x_2,y_2), \ldots, p_n = (x_n,y_n). Xác định cặp điểm gần nhất, đó là cặp điểm p_i\not=p_j sao cho khoảng cách giữa p_i,p_j là nhỏ nhất. Khoảng cách đó được tính bởi công thức \sqrt{(x_i-x_j)^2 + (y_i - y_j)^2}. Để đơn giản ở đây giả sử n = 2^k, tất cả các tọa độ trên trục x đôi một khác nhau và tất cả các tọa độ trên trục y đôi một khác nhau. Ý tưởng cơ bản như sau:

  • Tìm giá trị x sao cho một nửa số điểm có tọa độ x_i < x và nửa còn lại có tọa độ x_i  data-recalc-dims= x" />. Gọi hai nửa đó là L, R.
  • Đệ quy để tìm cặp điểm gần nhất của LR. Gọi 2 cặp điểm đó là p_L,q_L \in Lp_R,q_R \in R với khoảng cách lần lượt là d_L,d_R. Gọi d = \min (d_L,d_R).
  • Bây giờ ta cần tìm một điểm trong L và một điểm trong R sao cho khoảng cách giữa hai điểm đó nhỏ hơn d. Ta có thể loại bỏ đi những điểm có x_i < x-dx_i  data-recalc-dims= x+d" /> và sắp xếp những điểm còn lại theo chiều tăng của tọa độ y.
  • Bây giờ duyệt danh sách đã sắp xếp, với mỗi điểm, tính khoảng cách giữa nó và 7 điểm sau nó trong danh sách đã sắp xếp. Gọi p_M,q_M là hai cặp điểm gần nhất tìm được
  • Đáp số là căp điểm gần nhất giữa ba cặp điểm \{p_L,q_L\},\{p_R,q_R\},\{p_M,q_M\}

Câu hỏi như sau:

  1. Chứng minh thuật toán ở trên là đúng dựa trên tính chất sau: bất kì hình vuông nào có kích thước d\times d trong mặt phẳng chứa tối đa 4 điểm của L
  2. Viết giả mã cho thuật toán trên và chứng minh rằng thời gian tính của thuật toán được cho bởi công thức sau:

     T(n) = 2T(\frac{n}{2}) + O(n\log n)

    Chứng minh rằng thời gian chạy là T(n) = O(n\log^2 n).

  3. Liệu bạn có thể thiết kế giải thuật với thời gian O(n\log n) không?

Tags: , ,

  1. hoahuongduong’s avatar

    những thao tác tính a, b, c, d trong thuật toán nhân 2 số n bit đều là chia các số n bit sao ko phân tích thời gian hả ad ?

    Reply

    1. Hùng Lê’s avatar

      Hi bạn,
      Các thao tác chia này chỉ là các thao tác "dịch bít" trong máy tính. Do đó, chỉ mất thời gian O(n) cho mỗi phép chia.

      Một cách hiểu đó là cũng giống như khi bạn nhân (chia) một số cho lũy thừa của 10, thì bạn chỉ việc dịch dấu phẩy sang bên phải (trái).

      Hi vọng trả lời đúng câu hỏi của bạn.

      Reply

Reply

Your email address will not be published. Required fields are marked *