Trong bài viết này, chúng ta sẽ khám phá một thuật toán thần thánh đã được áp dụng rộng rãi trong lĩnh vực lập trình - Đó là thuật toán quy hoạch động. Nếu bạn tham gia các cuộc thi lập trình, việc biết và nắm vững thuật toán này sẽ cực kỳ quan trọng và hữu ích.
Khi nào thì dùng thuật toán quy hoạch động?
Trong lĩnh vực lập trình, không có công thức chung để áp dụng thuật toán quy hoạch động cho mọi bài toán. Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nhận biết và áp dụng thuật toán này. Hai tính chất nổi bật nhất là:
- Bài toán có các bài toán con gối nhau.
- Bài toán có cấu trúc con tối ưu.
Thường thì một bài toán thỏa cả hai tính chất trên sẽ có thể áp dụng quy hoạch động. Tuy nhiên, dù không thỏa cả hai tính chất này, ta vẫn có thể giải bài toán nhưng kết quả chưa chắc chắn và không hiệu quả. Trong các cuộc thi lập trình, việc sử dụng quy hoạch động là cực kỳ cần thiết để đạt được kết quả tốt trong thời gian ngắn và với bộ nhớ hạn chế.
Bài toán có các bài toán con gối nhau
Giống với thuật toán chia để trị, quy hoạch động cũng chia bài toán lớn thành các bài toán con nhỏ hơn. Tuy nhiên, quy hoạch động chỉ áp dụng khi các bài toán con được gọi đi gọi lại. Phương pháp này lưu kết quả của từng bài toán con và khi cần, sẽ không tính toán lại mà tái sử dụng kết quả đã có, giúp tiết kiệm thời gian.
Tuy nhiên, quy hoạch động không thể áp dụng hoặc không có tác dụng nếu các bài toán con không gối nhau. Ví dụ, trong thuật toán tìm kiếm nhị phân, mỗi bài toán con chỉ cần giải một lần và không bao giờ được gọi lại, nên quy hoạch động không có tác dụng tối ưu.
Một ví dụ điển hình của bài toán con gối nhau là bài toán tính số Fibonacci. Nếu tính số Fibonacci theo công thức thông thường, ta sẽ phải tính lại rất nhiều bài toán con, điển hình là tính số fib(0) và fib(1). Tuy nhiên, với quy hoạch động, chúng ta chỉ cần tính từng bài toán con một lần và lưu kết quả lại, giúp tiết kiệm đáng kể thời gian tính toán.
Cấu trúc con tối ưu
Tính chất cấu trúc con tối ưu là một yếu tố quan trọng trong quy hoạch động. Nó cho phép ta giải bài toán lớn dựa vào các bài toán con đã giải được. Nếu không có tính chất này, quy hoạch động không thể áp dụng.
Một ví dụ thực tế của tính chất cấu trúc con tối ưu là bài toán tìm đường đi ngắn nhất trong đồ thị. Nếu một node x nằm trên đường đi ngắn nhất giữa hai node u, v thì đường đi ngắn nhất từ u đến v sẽ là tổng hợp của đường đi ngắn nhất từ u đến x và đường đi ngắn nhất từ x đến v. Các thuật toán tìm đường trên đồ thị như Dijkstra cũng dựa trên tính chất này và áp dụng quy hoạch động.
Không phải tất cả các bài toán đều có tính chất cấu trúc con tối ưu này. Ví dụ, trong đồ thị, đường đi dài nhất không phải là tổ hợp của các đường đi thành phần, do đó, bài toán này không có cấu trúc con tối ưu.
Một số bài toán quy hoạch động
Trong phần này, chúng ta sẽ làm quen với quy hoạch động thông qua một số ví dụ cụ thể. Chúng ta sẽ tìm hiểu cách áp dụng quy hoạch động vào các bài toán cụ thể và hiểu rõ hơn về các tính chất đã được trình bày ở phần trước.
Ví dụ 1: Bài toán với đồng xu
Giả sử chúng ta có n đồng xu với trọng lượng lần lượt là W1, W2, ..., Wn và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng trọng lượng của chúng là giá trị S. Số lượng đồng xu là không giới hạn.
Đối với bài toán này, chúng ta có thể xây dựng và giải các bài toán con gối nhau. Với ví dụ của chúng ta, mỗi bài toán con dp(P) với P <= S là bài toán tìm số đồng xu nhỏ nhất để tổng trọng lượng của chúng là P, được ký hiệu là dp(P) = k.
Ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán con dp(0) và tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ được xây dựng lần lượt cho đến khi chúng ta đạt được bài toán lớn dp(S), đó chính là kết quả của bài toán.
Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ của chúng ta, mảng dp[0..S] sẽ lưu kết quả cho từng bài toán con. Cụ thể, dp[P] = k có nghĩa là cần ít nhất k đồng xu để có tổng trọng lượng là P. Toàn bộ mảng này sẽ được tính bằng vòng lặp. Dưới đây là đoạn mã mô tả toàn bộ quá trình này:
n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [0] * (S + 1)
dp[0] = 0
for P in range(1, S + 1):
dp[P] = min(dp[P - x] for x in w if x <= P) + 1
print(dp)
print(dp[S])Ví dụ, n = 3, S = 11, w = [1, 3, 5]. Kết quả của bài toán con sẽ được lưu trong mảng dp và kết quả cuối cùng là dp[S] = 3.
Ví dụ 2: Xâu con chung dài nhất (LCS)
Thêm một ví dụ nữa, cũng là một bài toán rất nổi tiếng. Bài toán đặt ra là tìm độ dài xâu con chung dài nhất giữa hai xâu ký tự. Ví dụ với hai xâu "quetzalcoatl" và "tezcatlipoca", xâu con chung dài nhất sẽ là "ezaloa" với độ dài là 6.
Để giải quyết bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:
- Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu con chung dài nhất giữa hai xâu con đã lấy ra đó. Lời giải của từng bài toán con này sẽ phụ thuộc vào i và j, ký hiệu là dp(i, j).
- Bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con theo đúng thứ tự từ dp(0, 0) đến dp(i, j) với i và j tăng dần.
Các trường hợp cần xem xét trong quá trình giải các bài toán con bao gồm:
- Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, ta có thể bỏ qua ký tự này mà không ảnh hưởng đến kết quả. Công thức được áp dụng là dp(i, j) = dp(i - 1, j).
- Tương tự, nếu ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả, ta có dp(i, j) = dp(i, j - 1).
- Trong trường hợp hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất và chúng giống nhau (x1 == x2), ta có công thức dp(i, j) = dp(i - 1, j - 1) + 1.
Trong cả ba trường hợp trên, chúng ta phải đưa ra sự lựa chọn tốt nhất để đạt được kết quả là xâu con chung dài nhất (chỉ cần tính độ dài).
Về mặt cài đặt, quy hoạch động thường sử dụng một mảng hai chiều để lưu kết quả. Kết quả của mảng này sẽ được tính thông qua một vòng lặp hai lớp. Quan trọng là chúng ta phải thực hiện vòng lặp theo đúng thứ tự từ bài toán con nhỏ đến lớn, vì mỗi bài toán con dp(i, j) phụ thuộc vào các bài toán con trước đó dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1).
Dưới đây là một đoạn mã giải quyết bài toán xâu con chung dài nhất:
def longest_common_substring(x, y):
m = len(x)
n = len(y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if x[i - 1] == y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
x = "quetzalcoatl"
y = "tezcatlipoca"
result = longest_common_substring(x, y)
print(result) # Kết quả là 6Như vậy, chúng ta đã đạt được kết quả là xâu con chung dài nhất giữa hai xâu "quetzalcoatl" và "tezcatlipoca" là "ezaloa" với độ dài là 6.
Trên đây là một số ví dụ về ứng dụng thực tế của thuật toán quy hoạch động. Qua những ví dụ này, chúng ta có thể hiểu rõ hơn về cách sử dụng và áp dụng quy hoạch động vào các bài toán cụ thể.
