Quy hoạch động là gì? Giải thích Memoization & Tabulation

Quy hoạch động là một cách giải bài toán bằng cách lưu lại đáp án của các bài toán con nhỏ hơn và tái sử dụng chúng về sau. Nó hữu ích khi cùng một bài toán con xuất hiện lặp lại và đáp án đầy đủ có thể được xây dựng từ những đáp án nhỏ hơn đó.

Hai cách triển khai chính là memoization và tabulation. Memoization lưu đáp án trong quá trình giải bằng đệ quy. Tabulation điền đáp án theo thứ tự từ dưới lên, thường dùng mảng hoặc bảng.

Khi nào quy hoạch động hiệu quả

Quy hoạch động hữu ích khi có hai điều kiện được thỏa mãn.

Thứ nhất, các bài toán con bị chồng lặp. Điều đó có nghĩa là cùng một kết quả trung gian cần được dùng nhiều hơn một lần. Thứ hai, đáp án lớn hơn có thể được xây dựng từ các đáp án nhỏ hơn theo một cách nhất quán.

Nếu các điều kiện đó không đúng, việc lưu kết quả cũ có thể chỉ làm tăng chi phí bộ nhớ mà không giúp ích nhiều.

Memoization và tabulation

Memoization: lưu từ trên xuống

Memoization bắt đầu từ ý tưởng đệ quy. Khi thuật toán giải một bài toán con lần đầu tiên, nó lưu kết quả lại. Những lần gọi sau sẽ dùng lại giá trị đã lưu thay vì tính lại từ đầu.

Cách này thường dễ dùng hơn khi công thức truy hồi đã rõ, nhưng thứ tự của tất cả các trạng thái cần thiết thì chưa rõ.

Tabulation: xây dựng từ dưới lên

Tabulation bắt đầu từ các trường hợp cơ sở và điền các trạng thái theo một thứ tự sao cho những phụ thuộc cần thiết luôn có sẵn khi cần.

Cách này thường dễ dùng hơn khi bạn đã biết một thứ tự lặp rõ ràng và muốn kiểm soát trực tiếp bảng giá trị.

Ví dụ về quy hoạch động: Fibonacci

Dãy Fibonacci được định nghĩa bởi

$$F(0) = 0, \quad F(1) = 1$$

và, với $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Một lời giải đệ quy thông thường sẽ lặp lại công việc. Ví dụ, để tính $F(5)$ cần $F(4)$ và $F(3)$, rồi khi tính $F(4)$ lại cần $F(3)$ thêm một lần nữa. Lời gọi $F(3)$ bị lặp đó chính là kiểu lãng phí mà quy hoạch động loại bỏ.

Memoization với Fibonacci

Với memoization, công thức truy hồi vẫn giữ nguyên, nhưng mỗi giá trị sẽ được lưu lại sau lần đầu tiên được tính.

Với $F(5)$, trình tự hữu ích là:

• tính và lưu $F(0)=0$
• tính và lưu $F(1)=1$
• tính và lưu $F(2)=1$
• tính và lưu $F(3)=2$
• tính và lưu $F(4)=3$
• tính và lưu $F(5)=5$

Điểm mấu chốt là mỗi trạng thái chỉ được tính một lần. Những lần cần sau chỉ việc đọc giá trị đã lưu.

Tabulation với Fibonacci

Với tabulation, bạn xây dựng từ các trường hợp cơ sở đi lên:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Phiên bản này cho thấy rõ thứ tự phụ thuộc: mỗi giá trị mới đều dùng những giá trị đã biết trước đó.

Vì sao quy hoạch động có thể nhanh hơn

Nếu một bài toán chỉ có $k$ trạng thái phân biệt thực sự quan trọng, quy hoạch động cố gắng giải mỗi trạng thái trong số $k$ trạng thái đó đúng một lần. Điều đó có thể biến một cây đệ quy lớn thành một phép tính nhỏ hơn rất nhiều.

Mức tăng tốc cụ thể phụ thuộc vào từng bài toán. Quy hoạch động không tự động nhanh trong mọi trường hợp. Nó phát huy tác dụng khi việc tính lặp thực sự là một phần đáng kể của lời giải ban đầu.

Những lỗi thường gặp trong quy hoạch động

Dùng khi các bài toán con không chồng lặp

Không phải bài toán đệ quy nào cũng là bài toán quy hoạch động. Nếu gần như mọi bài toán con đều khác nhau, việc lưu kết quả có thể không tiết kiệm đủ công sức để tạo ra khác biệt đáng kể.

Xác định sai trạng thái

Trạng thái phải chứa đủ mọi thông tin cần cho bước tiếp theo. Nếu thiếu thông tin quan trọng, công thức truy hồi có thể trông đúng nhưng lại cho ra đáp án sai.

Xác định sai trường hợp cơ sở

Các trường hợp cơ sở là nền móng của toàn bộ phương pháp. Nếu các giá trị khởi đầu sai, mọi trạng thái về sau được xây từ chúng cũng sẽ sai.

Điền bảng sai thứ tự

Tabulation chỉ hoạt động khi mỗi trạng thái được điền sau các trạng thái mà nó phụ thuộc vào. Một công thức truy hồi đúng vẫn có thể thất bại nếu thứ tự điền sai.

Cho rằng quy hoạch động lúc nào cũng là tối ưu hóa

Nhiều ví dụ nổi tiếng là bài toán cực đại hoặc cực tiểu, nhưng quy hoạch động cũng được dùng cho các bài toán đếm và bài toán quyết định. Dấu hiệu thật sự là các bài toán con có thể tái sử dụng, không phải từ “tốt nhất”.

Quy hoạch động được dùng ở đâu

Quy hoạch động xuất hiện trong các bài toán như khoảng cách chỉnh sửa, dãy con chung dài nhất, đếm số đường đi, tối ưu hóa kiểu ba lô, và một số bài toán đường đi ngắn nhất.

Khi bạn đang cân nhắc có nên dùng nó hay không, hãy tự hỏi hai câu:

• các bài toán con nhỏ hơn có lặp lại không?
• đáp án lớn hơn có thể được xây từ những đáp án nhỏ hơn đó không?

Nếu cả hai câu trả lời đều là có, quy hoạch động là một ứng viên rất mạnh.

Thử một bài toán tương tự

Hãy thử phiên bản của riêng bạn với bài toán đếm số cách leo $n$ bậc thang nếu mỗi bước đi là $1$ bậc hoặc $2$ bậc. Công thức truy hồi rất đơn giản, các bài toán con lặp lại cũng dễ nhận ra, và đây là ví dụ tiếp theo rất phù hợp sau Fibonacci.