Dynamic programming là gì? Tìm hiểu về thuật toán quy hoạch động (DP)

Nhiều bài toán đệ quy trở nên chậm vì liên tục tính lại cùng một kết quả. Thuật toán quy hoạch động khắc phục hạn chế này bằng cách lưu các trạng thái đã xử lý để tái sử dụng, qua đó rút ngắn thời gian thực thi. Cùng Viettel IDC tìm hiểu Dynamic Programming là gì, cách hoạt động và cách áp dụng qua ví dụ cụ thể.

Dynamic programming là gì?

Dynamic Programming (Quy hoạch động) là một phương pháp giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con nhỏ hơn, giải quyết các bài toán con đó một lần duy nhất và lưu trữ kết quả để tránh tính toán lại nhiều lần. Cách tiếp cận này giúp hạn chế các phép tính lặp lại, từ đó cải thiện đáng kể thời gian xử lý so với đệ quy thông thường.

Cơ chế hoạt động của quy hoạch động

Quy hoạch động hoạt động bằng cách xác định các bài toán con bị lặp lại trong quá trình giải, tính kết quả của từng bài toán con một lần rồi lưu lại để tái sử dụng. Khi cần xử lý một trạng thái đã xuất hiện, thuật toán lấy trực tiếp kết quả đã lưu thay vì thực hiện lại toàn bộ phép tính.

Dynamic programming thường trải qua các bước cơ bản sau:

- Chia nhỏ bài toán: Phân tích bài toán lớn thành các bài toán con nhỏ hơn có cùng bản chất.

- Xây dựng công thức truy hồi: Thiết lập mối liên hệ toán học giữa bài toán lớn và các bài toán con (ví dụ: F(n) = F(n-1) + F(n-2)).

- Lưu trữ kết quả (Memoization/Tabulation): Tạo một bảng (mảng) để lưu lại kết quả của các bài toán con đã giải.

- Giải từ dưới lên (hoặc từ trên xuống): Giải quyết các bài toán nhỏ nhất (trường hợp cơ sở), lưu kết quả, sau đó dùng chúng để giải các bài toán lớn hơn.

Các thuộc tính của quy hoạch động

Không phải bài toán nào cũng phù hợp để giải bằng thuật toán Dynamic Programming. Phương pháp này phát huy hiệu quả khi bài toán có thể chia thành các bài toán con liên quan và kết quả của chúng được tái sử dụng trong quá trình tính toán.

Cấu trúc con tối ưu

Cấu trúc con tối ưu là thuộc tính cho thấy lời giải tốt nhất của bài toán lớn có thể được xây dựng từ lời giải tốt nhất của các bài toán con. Nói cách khác, nếu một phần trong lời giải tổng thể chưa tối ưu thì kết quả cuối cùng cũng khó đạt mức tối ưu.

Ví dụ, cần tìm đường đi ngắn nhất từ A đến C và bắt buộc đi qua B. Khi đó, đường đi tối ưu từ A đến C sẽ được tạo từ đường đi ngắn nhất từ A đến B kết hợp với đường đi ngắn nhất từ B đến C. Nếu một trong hai đoạn đường này chưa phải ngắn nhất, toàn bộ hành trình cũng không thể là phương án tối ưu.

Các bài toán con chồng lặp

Các bài toán con chồng lặp xuất hiện khi cùng một bài toán nhỏ được giải nhiều lần trong quá trình xử lý bài toán lớn. Thay vì tính lại từ đầu, quy hoạch động lưu kết quả của mỗi bài toán con và sử dụng lại khi gặp trạng thái tương tự.

Ví dụ, khi tính F(5) theo dãy Fibonacci, thuật toán cần tính F(4) và F(3). Trong quá trình tính F(4), giá trị F(3) tiếp tục xuất hiện, còn F(2) có thể được sử dụng nhiều lần ở các nhánh khác nhau. Quy hoạch động lưu sẵn các giá trị F(2), F(3) và F(4), nhờ đó tránh thực hiện lại cùng một phép tính.

Ưu điểm và nhược điểm của Dynamic programming là gì

Dynamic Programming giúp tối ưu các bài toán có nhiều trạng thái lặp lại và cấu trúc con tối ưu. Tuy nhiên, phương pháp này cũng đòi hỏi cách xây dựng trạng thái hợp lý và có thể tiêu tốn nhiều bộ nhớ.

Ưu điểm của Dynamic Programming

- Giảm phép tính lặp bằng cách lưu và tái sử dụng kết quả của các bài toán con.

- Cải thiện đáng kể thời gian thực thi so với đệ quy thông thường trong nhiều trường hợp.

- Phù hợp với các bài toán tối ưu như tìm đường đi ngắn nhất, ba lô, chuỗi con chung dài nhất hoặc phân bổ tài nguyên.

- Có thể triển khai linh hoạt theo hướng từ trên xuống bằng memoization hoặc từ dưới lên bằng tabulation.

- Đảm bảo tìm được lời giải tối ưu khi bài toán đáp ứng đúng các điều kiện của quy hoạch động.

Nhược điểm của Dynamic Programming

- Tiêu tốn thêm bộ nhớ để lưu trạng thái và kết quả trung gian.

- Khó xác định trạng thái, công thức truy hồi và trường hợp cơ sở đối với bài toán phức tạp.

- Mã nguồn có thể khó đọc và khó bảo trì nếu số lượng trạng thái quá lớn.

- Không phù hợp với bài toán không có cấu trúc con tối ưu hoặc bài toán con chồng lặp.

- Hiệu suất có thể giảm khi không gian trạng thái quá rộng hoặc lưu nhiều kết quả không cần thiết.

Phân biệt Memoization và Tabulation trong Dynamic Programming

Memoization và Tabulation đều là hai cách triển khai phổ biến của Dynamic Programming. Điểm chung của chúng là lưu lại kết quả của các bài toán con để tránh tính toán lặp lại, nhưng khác nhau về thứ tự xử lý và cách tổ chức thuật toán.

Memoization là gì?

Memoization là cách triển khai quy hoạch động theo hướng từ trên xuống. Thuật toán bắt đầu từ bài toán cần giải, sau đó tiếp tục gọi đệ quy để xử lý các bài toán con.

Khi một trạng thái được tính lần đầu, kết quả sẽ được lưu vào bộ nhớ đệm. Nếu trạng thái đó xuất hiện lại, thuật toán lấy trực tiếp kết quả đã lưu thay vì tính lại.

Ví dụ tính số cách leo cầu thang bằng Memoization:

Trong đoạn mã trên, dictionary memo lưu số cách leo đến từng bậc. Mỗi trạng thái chỉ được tính khi cần và được tái sử dụng trong các lần gọi tiếp theo.

Tabulation là gì?

Tabulation là cách triển khai quy hoạch động theo hướng từ dưới lên. Thuật toán bắt đầu từ các trường hợp cơ sở, sau đó sử dụng kết quả đã có để lần lượt tính các trạng thái lớn hơn. Phương pháp này thường sử dụng vòng lặp thay cho đệ quy, nhờ đó hạn chế chi phí gọi hàm và tránh nguy cơ tràn ngăn xếp.

Ví dụ tính số cách leo cầu thang bằng Tabulation:

Trong trường hợp này, thuật toán tính lần lượt từ dp[0] đến dp[n]. Mỗi giá trị được xây dựng từ hai trạng thái đứng trước.

Trường hợp nào nên sử dụng Dynamic programming?

Dynamic Programming thường được lựa chọn khi bài toán có nhiều hướng xử lý nhưng các trạng thái trung gian lại lặp lại. Dựa vào những dấu hiệu dưới đây, bạn có thể xác định liệu quy hoạch động có phải là phương pháp phù hợp hay không.

Ví dụ cụ thể về bài toán quy hoạch động

Một ví dụ phổ biến của quy hoạch động là bài toán đếm số cách leo cầu thang. Giả sử có một cầu thang gồm n bậc, mỗi lần người leo có thể bước 1 hoặc 2 bậc. Yêu cầu là tính tổng số cách khác nhau để đi từ mặt đất lên bậc thứ n.

Phân tích bài toán

Để đến bậc thứ n, người leo chỉ có thể đi từ bậc n - 1 bằng một bước hoặc từ bậc n - 2 bằng hai bước. Vì vậy, số cách đến bậc thứ n được tính theo công thức:

dp[n] = dp[n - 1] + dp[n - 2]

Trong đó, dp[n] là số cách leo đến bậc thứ n. Hai trường hợp cơ sở gồm:

- dp[0] = 1: Có một cách đứng tại vị trí ban đầu.

- dp[1] = 1: Chỉ có một cách bước lên bậc thứ nhất.

Tính số cách leo cầu thang với n = 5

Từ hai giá trị cơ sở, thuật toán tính lần lượt:

- dp[2] = dp[1] + dp[0] = 2

- dp[3] = dp[2] + dp[1] = 3

- dp[4] = dp[3] + dp[2] = 5

- dp[5] = dp[4] + dp[3] = 8

Như vậy, có 8 cách để leo lên cầu thang gồm 5 bậc:

- 1 + 1 + 1 + 1 + 1

- 1 + 1 + 1 + 2

- 1 + 1 + 2 + 1

- 1 + 2 + 1 + 1

- 2 + 1 + 1 + 1

- 1 + 2 + 2

- 2 + 1 + 2

- 2 + 2 + 1

Cách triển khai bằng quy hoạch động

Với phương pháp tabulation, thuật toán tính từ trạng thái nhỏ đến trạng thái lớn và lưu kết quả trong mảng:

Bài toán này phù hợp với quy hoạch động vì có cấu trúc con tối ưu và các bài toán con chồng lặp. So với đệ quy thông thường có thể mất O(2^n), quy hoạch động giảm thời gian xử lý xuống còn O(n).

Kết luận

Qua những nội dung trên, Dynamic Programming là gì có thể được nhìn nhận như một phương pháp tối ưu thuật toán bằng cách lưu và tái sử dụng kết quả của các bài toán con. Cách tiếp cận này đặc biệt phù hợp với những bài toán có trạng thái lặp và cần tìm lời giải tối ưu trong thời gian ngắn hơn.