Quy hoạch động -- dynamic programming I

Ở bài trước chúng ta đã giới thiệu về quay lui và xem xét một vài ví dụ về quay lui, trong đó có bài toán Subset Sum. Giải thuật quay lui chúng ta thảo luận ở bài trước cho bài toán này có thời gian cỡ O(2^n), bất kể giá trị của tổng T. Với n = 30, thuật toán quay lui chạy khá chậm. Ở bài này chúng ta sẽ thiết kế thuật toán với thời gian O(n^2T) và do đó, nếu T không quá lớn, chúng ta có thể giải bài toán này khá nhanh trong thực tế với thời gian O(nT).

Quy hoạch động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Khác với chia để trị, quy hoạc động, thay vì gọi đệ quy, sẽ tìm lời giải của các bài toán con và lưu vào bộ nhớ (thường là một mảng), và sau đó lấy lời giải của bài toán con ở trong mảng đã tính trước để giải bài toán lớn. Việc lưu lại lời giải vào bộ nhớ khiến cho ta không phải tính lại lời giải của các bài toán con mỗi khi cần, do đó, tiết kiệm được thời gian tính toán. Trước hết hãy xem xét một vài ví dụ minh họa.

Dãy số Fibonacci

Bài toán dãy số Fibonacci như sau:

Problem 1: Tính F_n biết F_n thỏa mãn biểu thưc sau:

F_n = F_{n-1} + F_{n-2} \qquad F_0 = 0, F_1 = 1

 
Dựa vào định nghĩa của dãy số Fibonacci, ta có thủ tục đệ quy sau để tính F_n:

RecFib(n):
    if n < 2
        return n
    else
        return RecFib(n-1) + RecFib(n-2)

 
Số phép cộng phải thực hiện của thủ tục đệ quy trên để tính F_n là:

 
Như vậy thời gian tính là hàm số mũ. Một câu hỏi là liệu chúng ta có thể tính nhanh hơn đệ quy được không. Trước hết chúng ta hãy nhìn vào cây đệ quy (có nhắc đến ở đây) của thuật toán. Mỗi nút của cây là giá trị F_n và nút con là các giá trị cần thiết tương ứng với hàm đệ quy của F_n. Các nút lá là F_0 hoặc F_1. Ví dụ cây đệ quy để tính F_5:
fib-recur
Như vậy nhìn vào cây ta thấy để tính F_5, thủ tục đệ quy sẽ tính lại F_2 3 lần và F_3 2 lần. Nguyên nhân có tính toán lặp đi lặp lại như vậy là vì sau khi tính F_2 bằng hàm RecFib(2), thuật toán không lưu lại giá trị đã tính.

Cải tiến 1 (memorization): lưu lại những gì đã tính. Theo nhận xét ở trên, ta có thể cải tiến thuật toán như sau: ta dùng môt mảng F[1,2,\ldots,n] để lưu lại giá trị đã tính, i.e, F[i] = F_i. Khi goị đệ quy, nếu F_i đã được tính trước đó rồi (F[i] đã xác định), ta chỉ việc trả lại F[i]. Giả mã như sau:

MemFib(n):
    if  n < 2
        return n
    else
        if F[n] is undefined
          F[n] \leftarrow MemFib(n-1) + MemFib(n-2)
        return F[n]

 
Code của giả mã bằng C. Code đầy đủ được cho ở cuối bài:

int memorized_fib(int n){
	if(n < 2) return n;
	else {
		if(F[n] == 0){
			F[n] = memorized_fib(n-1) + memorized_fib(n-2);
		}
		return F[n];
	}
}

Ở đây có thể thấy số phép cộng phải thực hiện để tính F_n chính bằng số phép cộng phải thực hiện để cập nhật mảng F[1,2,\ldots,n]. Mỗi lần cập nhật một phần tử của mảng sử dụng 1 phép cộng. Như vậy số phép cộng của thuật toán là O(n) (nhanh hơn gấp lũy thừa lần thuật toán đệ quy!!!!).

Cải tiến 2: quy hoạch động. Như vậy ý tưởng chính của cải tiến 1 là lưu lại những giá trị đã tính vào một mảng và thời gian tính được quy về thời gian cần thiết để cập nhật mảng F[1,2,\ldots,n]. Một câu hỏi ngay lập tức sẽ là liệu có cần thiết phải dùng đệ quy để cập nhật mảng hay không? Câu trả lời là không, ta có thể cập nhật mảng bằng cách lặp. Đó cũng là tư tưởng chính của quy hoạch động. Thay vì dùng đệ quy có nhớ, dùng vòng lặp để cập nhật lời giải các bài toán con và lưu vào bộ nhớ (một mảng). Giải thuật quy hoạch động tính F_n có giả mã như sau:

DynamicFib(n):
    F[0] \leftarrow 0; F[1] \leftarrow 1
    for i \leftarrow 2 to n
        F[i] \leftarrow F[i-1] + F[i-2]
    return F[n]

 
Dễ thấy thuật toán thực hiện O(n) phép cộng để tính F_n.

Nhưng dường nhừ từ quy hoạch động (dynamic programming) không nói lên bản chất của thuật toán và thực tế là như vậy. Lịch sử của từ dynamic programming bắt đầu từ Richard Bellman. Bellman phát triển nền tảng toán học (của quy hoạch động) nhưng ông muốn chọn một thuật ngữ cho nền tảng đó không liên quan gì đến toán vì cấp trên của ông không thích những gì liên quan đến toán. Do đó ông chọn thuật ngữ dynamic programming. Từ programming không có nghĩa là lập trình, mà mang nghĩa hơi liên quan đến đặt kết hoạch hay lập lịch bằng cách điền vào bảng. Còn từ dynamic muốn nhấn mạnh việc bảng đó được điền qua thời gian chứ không phải điền một lần. Bản thân mình thích thuật ngữ khử đệ quy có nhớ hơn.

Cải tiến 3: tiết kiệm bộ nhớ. Nhìn vào định nghĩa ta thấy F_n chỉ phụ thuộc vào F_{n-1}F_{n-2}, chính vì thế ở mỗi bước lặp, chúng ta chỉ cần lưu lại hai giá trị này là đủ. Giả mã như sau:

SaveMemFib(n):
    prev \leftarrow 0
    curr \leftarrow 1
    for i \leftarrow 2 to n
        next \leftarrow prev + curr
        prev \leftarrow curr
        curr \leftarrow next
    return curr

 
Code thực hiện bằng C:

int save_mem_fib(int n){
	int prev = 0;
	int curr = 1;
	int next;
	int i = 0;
	for(i = 2; i <= n ; i++){
		next = prev + curr;
		prev = curr;
		curr = next;
	}
	return next;
}

Dễ thấy số phép cộng cần thiết để thực hiện tính F_nO(n).

Một câu hỏi đặt ra là liệu thuật toán còn có thể cải tiến nhanh hơn được không? Ở trên khi phân tích thuật toán, mình chỉ nhắc đến số phép cộng cần thiết để tìm F_n. Thực tế khi thực hiện phép cộng hai số của dãy Fibonacci, thời gian không phải là hằng số (như thường giả sử trong phân tích thuật toán). Nguyên nhân là vì số Fibonacci thứ n có độ lớn xấp xỉ \phi^n (\phi \simeq 1.6....), và do đó số lượng bit cần thiết để biểu diễn F_n là cỡ n\log \phi. Do đó cộng hai số Fibonacci mất thời gian cỡ O(n) và thuật toán quy hoạch động ở trê có thời gian chạy cỡ O(n^2), không phải O(n). Bạn đọc có thể xem thêm chi tiết cách ta định nghĩa độ phức tạp thuật toán tại đây.

Cải tiến 4: fast integer multiplication. Cải tiến này dựa trên công thức sau:

\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} \times \left[ \begin{array}{c} x \\ y \end{array} \right] = \left[ \begin{array}{c} y \\ x+y \end{array} \right]

Như vậy nhân một vector với ma trận

\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}

tương đương với một vòng lặp trong thủ tục SaveMemFib. Bằng quy nạp, không khó để chứng minh rằng:

\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^{n-1} \times \left[ \begin{array}{c} 0 \\ 1 \end{array} \right] = \left[ \begin{array}{c} F_{n-1} \\ F_n \end{array} \right]

Ta có thể tính nhanh ma trận:

\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}^n

sử dụng O(\log n) phép cộng và nhân bằng thuật toán ở đây, và sử dụng thuật toán nhân 2 số nguyên n bít nhanh ở đây với thời gian O(n^{1.585}). Như vậy có thể giảm thời gian thuật toán xuống còn O(n^{1.585}\log n). Nếu sử dụng thuật toán nhân hai số nguyên n bit nhanh nhất, (có nói đến ở đây), ta có thể giảm được thời gian hơn nữa (cỡ O(n\log^3 n)).
Code: Fibonacci

Tham khảo

Bài viết chủ yếu dựa trên notes của Jef Erickson. Note này khá tốt để tham khảo. Các bạn sẽ học được rất nhiều từ bản gốc hơn là bài viết này.
[1] Jeff Erickson, Dynamic Programming Lecture Notes , UIUC.

Facebook Comments

Tags: ,

  1. Hoan Nguyen’s avatar

    Cảm ơn bài viết bổ ích của bạn. 🙂 Keep it up

    Reply

Reply

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