Quy hoạch động -- Dynamic Programming IV

Trong bài này chúng ta sẽ thảo luận bài toán xây dựng cây nhị phân tìm kiếm tối ưu. Chúng ta cũng thảo luận giải thuật cuả Knuth trong bài toán này. Ý tưởng của Knuth sau này được Yao[4] mở rộng với trường hợp Bất Đẳng Thức Hình Chữ Nhật (Quadrangle Inequality) để cải tiến quy hoạch động, một kĩ thuật mà mình sẽ giới thiệu ở phần sau.

Cây nhị phân tìm kiếm tối ưu

Cây nhị phân tìm kiếm (binary search tree) là một cây nhị phân có tính chất sau:

  1. Mỗi nút là một khóa tìm kiếm
  2. Với mỗi cây con, khóa của nút gốc lớn hơn khóa của mọi nút của cây con trái và nhỏ hơn khóa của mọi nút của cây con phải
Problem 4: Cho một mảng K[1,2,\ldots, n] đã sắp xếp theo chiều tăng dần trong đó các phần tử đôi một khác nhau. Mỗi phần tử K[i] có tần số tìm kiếm f[i]. Tìm cây nhị phân với khóa là các phần tử của mảng K sao cho tổng số lượng các phép so sánh là nhỏ nhất.

 
Ví dụ: Ta có mảng K[1,2,\ldots, 6] = \{1,2,3,4,5,6\} và mảng tần số tương ứng f[1,2,\ldots, 6] =\{1,5,3,4,2,3\}. Một trong số các cây nhị phân tìm kiếm hợp lệ như trong hình sau:
opt-bin-fig
Các số trong hình vuông nhỏ là tần số tìm kiếm, các số trong hình tròn là khóa tìm kiếm. Ta có thể thấy:

  1. Số lần so sánh thực hiện ở nút gốc là 1+5+3+4+2+3 = 18 vì mỗi khi tìm kiếm một khoá, nút gốc luôn được so sánh đầu tiên.
  2. Số lần so sánh thực hiện ở nút có khóa 2 và 6 lần lượt là 5+ 1 + 3 = 9, 2 + 3 = 5.
  3. Số lần so sánh thực hiện ở nút có khóa 1,3,5 lần lượt là 1, 3, 2.

Như vậy tổng số phép so sánh là 38. Có thể kiểm tra (bằng cách thử xây dựng các cây nhị phân tìm kiếm hợp lệ khac nhau) rằng cây nhị phân trong hình tương ứng với Kf trong ví dụ có tổng số lượng các phép so sánh là nhỏ nhất.

Qua ví dụ trên có thể rút ra số lần so sánh thực hiện ở nút gốc không phụ thuộc vào cách chọn khóa cho nút gốc và luôn là f[1]+f[2] + \ldots + f[n].

Ta sẽ phát triển công thức đệ quy cho bài toán này. Gọi Opt(1,2,\ldots, n) là số phép so sánh của cây nhị phân tìm kiếm tối ưu cho mảng K[1,2,\ldots ,n]. Nếu K[r] là khóa của nút gốc, ta có:

Opt(1,\ldots, n) = Opt(1,\ldots, r-1)+ Opt(r+1,\ldots, n) + \sum_{i=1}^nf[i]

Vì ta không biết nút nào là nút gốc, ta có thể thử tất cả các lựa chọn có thể có cho nút gốc. Do đó ta có:

Opt(1\ldots n) = \min_{1\leq r \leq n}\{Opt(1\ldots r-1)+ Opt(r+1\ldots n)\} + \sum_{i=1}^nf[i]

 
Gọi C[i,j] là số phép so sánh của cây nhị phân tìm kiếm tối ưu cho mảng con K[i,\ldots,j]. Đặt F[i,j] = \sum_{k=i}^j f[k]. Ta có:

C[i,j] = \min_{i\leq r \leq j}\{C[i,r-1] + C[r+1,j]\} + F[i,j]


 
Như các bài toán khác, quy hoạch động trong bài toán nay quy về cập nhật các phần tử của mảng C[1,n]. Tuy nhiên, một điểm cần chú ý ở đây chính là thứ tự cập nhật các phần tử của mảng.
table-filling
Trong hình trên, các phân tử của mảng tô màu xanh là các phần tử C[i,i] và được khởi tạo C[i,i]=f[i]. Giả sử ta muốn cập nhật phần tử được tô màu đen của mảng (ảnh ngoài cùng bên trái), ta phải chắc chắn rằng các phần tử được tô màu đỏ đã được cập nhật trước đó. Do đó ta có thể có 3 cách cập nhật bảng (3 hình với các mũi tên) như trên hình trên. Các mũi tên chỉ thứ tự các phần tử được cập nhật. Trong giả mã dưới đây, bảng được cập nhật theo hình thứ nhất (cập nhật kiểu đường chéo). Mũi tên xanh sẽ tương ứng với vòng lặp ngoài cùng của giả mã. Các kiểu cập nhật khác coi như bài tập cho bạn đọc. Hàm PreCompute(f[1,2,\ldots,n]) tính F[1,2,\ldots,n][1,2,\ldots,n]. Hàm ComputeCost(i,i+d) tính C[i,i+d] theo công thức đệ quy ở trên. Ta lưu thêm mảng R[1,2,\ldots,n][1,2,\ldots,n] trong đó R[i,j] lưu lại gốc của cây nhị phân tìm kiếm tối ưu của mảng con A[1,2,\ldots,j]. Mảng R[1,2,\ldots,n][1,2,\ldots,n] có thể được sử dụng để truy vết in ra cây nhị phân tìm kiếm tối ưu.

OptBinSearchTree(A[1,2,\ldots, n]):
    PreCompute(f[1,2,\ldots,n])
    for i \leftarrow 1 to n
        C[i,i] \leftarrow F[i][i]
        R[i,i] \leftarrow i
    for d \leftarrow 1 to n-1
       for i \leftarrow 1 to n-d
            ComputeCost(i,i+d)
    return C[1,n]

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

int opt_binary_search_tree(int f[], int size){
	int i = 0, j = 0;
	for(i = 0; i <= size; i++){
		memset(F[i], 0, sizeof(F[i]));// set everything to 0
		memset(C[i], 0, sizeof(C[i]));// set everything to 0
	}
	precompute_cost(f, size);
	for(i = 0; i <= size; i++){
			R[i][i] = i;
			C[i][i] = F[i][i];
		}
	int d = 1;
	for(d = 1; d < size; d++){
		for(i = 1; i <= size-d; i++){
		  compute_opt_cost(i, i+d);
		 }
	}
	return C[1][size];
}

Bảng F[1,\ldots,n][1,\ldots,n] có thể được tính bằng quy hoạch động trong thời gian O(n^2) dựa vào công thức: F[i,j] = F[i,j-1] + f[j]. Giả mã như sau:

PreCompute(f[1,2,\ldots, n]):
    for i \leftarrow 1 to n
        F[i,i-1] \leftarrow 0
        for j \leftarrow i to n
           F[i,j] \leftarrow F[i,j-1] + f[j]

 
Code bằng C của giả mã:

void precompute_cost(int f[], int size){
	int i = 0, j = 0;
	for(i = 1; i <= size; i++){
		for(j = i; j <= size; j++){
			F[i][j] = F[i][j-1] + f[j-1];
		}
	}
}

Giả mã của hàm ComputeCost(i,i+d).

ComputeCost(i,j):
    C[i,j] \leftarrow +\infty
    for r \leftarrow i to j
        tmp \leftarrow C[i,r-1] + C[r+1,j]
        if tmp \leq C[i,j]
            C[i,j] \leftarrow tmp
            R[i,j] \leftarrow r
    C[i,j] \leftarrow C[i,j] + F[i,j]

 
Code bằng C của giả mã:

void compute_opt_cost(int i, int j){
	  int r = 0;
	  int tmp = 0;
	  C[i][j] = INFTY;
	  for(r = i; r <= j ; r++){
		  tmp = C[i][r-1] + C[r+1][j];
		  if(tmp <= C[i][j]){
			  C[i][j] = tmp;
			  R[i][j] = r;
		  }
	  }
	  C[i][j] = C[i][j] + F[i][j];
}

Phân tích thời gian Thời gian để cập nhật mảng F[1,2,\ldots, n][1,2,\ldots, n] trong hàm PreCompute(f[1,2,\ldots,n])O(n^2). Mỗi phần tử của mảng C[1,2,\ldots, n][1,2,\ldots, n] được cập nhật trong thời gian O(n) (có thể phân tích chặt hơn nhưng thời gian tiệm cận vẫn không đổi). Như vậy thuật toán có thời gian tính là O(n^3). Thuật toán cần hai mảng 2 chiều CF kích thướng n \times n. Như vậy bộ nhớ cần dùng là O(n^2). Hiện tại chưa có thuật toán nào tính chính xác cây nhị phân tìm kiếm tối ưu mà bộ nhớ o(n^2).

Với ví dụ trên, mảng R đầu ra của thuật toán là:

\begin{bmatrix} 1&2&2&3&4&4 \\ 0&2&2&3&4&4& \\ 0&0&3&4&4&4 \\ 0&0&0&4&4&5 \\ 0&0&0&0&5&6 \\ 0&0&0&0&0&6& \end{bmatrix}

Với ví dụ trên, ta quan sát thấy mảng R đầu ra có hàng và cột là các dãy tăng dần. Tính chất này không phải ngãu nhiên mà đúng với mọi n và được chứng minh lần đầu tiên bởi Donald Knuth [1]. Knuth sử dụng tính chất này để giảm thời gian của thuật toán quy hoạch động xuống còn O(n^2).

Thuật toán O(n^2)

Mỗi mảng con K[i,\ldots, j] có thể có nhiều hơn một cây nhị phân tìm kiếm tối ưu. Trong số các cây nhị phân tìm kiếm tối ưu đó, chọn cây có gốc r có khóa lớn nhất (đồng nghĩa với trong số các gốc của các cây nhị phân tìm kiếm tối ưu, r có chỉ số trong mảng K lớn nhất). Gọi R[i,j] là gốc đó. Nếu để ý kĩ thủ thục ComputeCost(i,i+d) với điều kiện so sánh: tmp \leq C[i,j] (thay vì tmp  < C[i,j]), thủ tục đó trả lại cây của mảng K[i,\ldots,j] có gốc lớn nhất. Knuth chứng minh bổ đề sau:

Lemma (Donald Knuth [1]):

 R[i,j-1] \leq R[i,j] \leq R[i+1,j]

 
Mình sẽ chứng minh bổ đề này trong bài viết thảo luận các kĩ thuật nâng cao áp dụng trong quy hoạch động.
knuth-obs
Do đó trong thủ tục ComputeCost(i,i+d), thay vì duyệt từ i đến j để tìm gốc, ta chỉ cần duyệt từ R[i,j-1] đến R[i+1,j]. Giả mã như sau:

KnuthComputeCost(i,j):
    C[i,j] \leftarrow +\infty
    for r \leftarrow R[i,j-1] to R[i+1,j]
        tmp \leftarrow C[i,r-1] + C[r+1,j]
        if tmp \leq C[i,j]
            C[i,j] \leftarrow tmp
            R[i,j] \leftarrow r
    C[i,j] \leftarrow C[i,j] + F[i,j]

 
Code bằng C của giả mã:

void knuth_opt_cost(int i, int j){
	  int r = 0;
	  int tmp = 0;
	  C[i][j] = INFTY;
	  for(r = R[i][j-1]; r <= R[i+1][j] ; r++){
		  tmp = C[i][r-1] + C[r+1][j];
		  if(tmp <= C[i][j]){
			  C[i][j] = tmp;
			  R[i][j] = r;
		  }
	  }
	  C[i][j] = C[i][j] + F[i][j];
}

Các thủ tục khác không thay đổi, ta chỉ việc thay thế thủ tục ComputeCost bằng KnuthComputeCost

Phân tích thời gian Ta có bổ đề sau:

Lemma: Thời gian tính toán của thuật toán OptBinSearchTree với thủ tục KnuthComputeCostO(n^2).

 
Chứng minh
Với mỗi d, số thao tác thuật toán thực hiện là:

\begin{array} {l} T(d) &= \sum_{i=1}^{n-d} R[i+1,i+d] - R[i,i+d-1] + O(1)  \\ & = \sum_{i=1}^{n-d} R[i+1,i+d] - \sum_{i=1}^{n-d}R[i,i+d-1] + O(n-d) \\& =  \sum_{i=2}^{n-d+1} R[i,i+d-1] -  \sum_{i=1}^{n-d}R[i,i+d-1] + O(n-d) \\ &= R[n-d+1, n] - R[1,d] + O(n-d) \\ &\leq n + O(n-d) = O(n) \end{array}

Do đó, tổng số thao tác thực hiện của thuật toán là:

\sum_{d=1}^{n-1} T(d) \leq \sum_{d=1}^{n-1} O(n) = O(n^2)

Code: opt-bst, data.
Tham khảo
[1] Knuth, D.E. "Optimum binary search trees", Acta Informatica 1 (1): 14–25.
[2] Jeff Erickson, Dynamic Programming Lecture Notes, UIUC.
[3] Nagaraj, S. V. "Optimal binary search trees." Theoretical Computer Science 188.1 (1997): 1-44.
[4] Yao, F. Frances. "Efficient dynamic programming using quadrangle inequalities." In Proceedings of the twelfth annual ACM symposium on Theory of computing, pp. 429-435. ACM, 1980.

Tags: , , , , ,

  1. Hortensia Tucciarone’s avatar

    Great article thank you for sharing.

    Reply

Reply

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