Giải thuật Qui hoạch động (Dynamic Programming)
Qui hoạch động (Dynamic Programming – DP) là một kỹ thuật thiết kế thuật toán rất mạnh, được sử dụng để giải quyết các bài toán tối ưu hóa bằng cách chia chúng thành các bài toán con chồng lấn, sau đó giải quyết từng bài toán con một lần và lưu trữ kết quả để sử dụng lại khi cần thiết.
Mục lục
Ý tưởng chính của qui hoạch động:
- Chia bài toán thành các bài toán con nhỏ hơn: Bài toán gốc được chia thành các bài toán con đơn giản hơn.
- Ghi nhớ lời giải của các bài toán con (Memoization): Kết quả của mỗi bài toán con được lưu trữ (thường sử dụng mảng hoặc bảng) để tránh việc phải tính lại những bài toán con giống nhau trong tương lai.
- Sử dụng lại lời giải: Khi gặp lại bài toán con đã giải, thuật toán sẽ sử dụng lại kết quả đã lưu thay vì tính lại, giúp tăng hiệu suất.
Điểm khác biệt quan trọng giữa qui hoạch động và phương pháp chia để trị là qui hoạch động lưu trữ kết quả của các bài toán con để tránh tính toán lặp lại, trong khi chia để trị không lưu trữ kết quả, do đó có thể dẫn đến việc giải lại nhiều lần cùng một bài toán con.
Các bước để giải quyết bài toán bằng qui hoạch động:
- Xác định trạng thái (state): Tìm cách biểu diễn bài toán dưới dạng các trạng thái.
- Xác định công thức truy hồi (recurrence relation): Thiết lập mối liên hệ giữa các trạng thái để có thể tính toán trạng thái lớn hơn từ các trạng thái nhỏ hơn.
- Xác định các trường hợp cơ sở (base cases): Xác định giá trị khởi đầu của bài toán.
- Tính toán và lưu trữ kết quả: Áp dụng công thức truy hồi và lưu trữ kết quả vào bảng (table) để tránh tính toán lại.
Ví dụ bài toán sử dụng qui hoạch động:
1. Bài toán Fibonacci
Bài toán tính số Fibonacci thứ n là một ví dụ kinh điển để minh họa qui hoạch động.
Công thức đệ quy Fibonacci:
- F(n) = F(n-1) + F(n-2)
- Với điều kiện cơ sở:
- F(0) = 0
- F(1) = 1
Cách giải bằng qui hoạch động:
public class FibonacciDP {
// Hàm tính Fibonacci bằng qui hoạch động
public static int fibonacci(int n) {
// Tạo một mảng để lưu kết quả của các số Fibonacci
int[] fib = new int[n + 1];
// Điều kiện cơ sở
fib[0] = 0;
fib[1] = 1;
// Tính các giá trị Fibonacci từ 2 đến n
for (int i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
// Trả về Fibonacci của n
return fib[n];
}
public static void main(String[] args) {
int n = 10;
System.out.println("Fibonacci of " + n + " is " + fibonacci(n));
}
}Giải thích:
- Xác định trạng thái: Ở đây, trạng thái là
F(n)– giá trị của số Fibonacci thứn. - Công thức truy hồi: F(n) = F(n-1) + F(n-2).
- Điều kiện cơ sở: F(0) = 0 và F(1) = 1.
- Tính toán và lưu trữ: Sử dụng mảng
fib[]để lưu trữ kết quả của các số Fibonacci đã tính được và sử dụng lại khi cần.
Độ phức tạp:
- Thời gian: O(n) vì chúng ta chỉ tính mỗi số Fibonacci một lần.
- Không gian: O(n) vì cần lưu trữ kết quả của tất cả các số Fibonacci từ 0 đến n.
2. Bài toán balô (Knapsack Problem)
Bài toán balô 0-1 là một ví dụ phổ biến khác của qui hoạch động. Cho một balô có sức chứa nhất định và một danh sách các vật phẩm, mỗi vật phẩm có một giá trị và một trọng lượng, nhiệm vụ là tìm cách chọn một số vật phẩm sao cho tổng giá trị là lớn nhất mà không vượt quá sức chứa của balô.
Cách giải bài toán balô 0-1 bằng qui hoạch động:
public class KnapsackDP {
// Hàm tính giá trị lớn nhất có thể đưa vào balô
public static int knapsack(int W, int[] weights, int[] values, int n) {
int[][] K = new int[n + 1][W + 1];
// Duyệt qua tất cả các vật phẩm
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (weights[i - 1] <= w) {
K[i][w] = Math.max(values[i - 1] + K[i - 1][w - weights[i - 1]], K[i - 1][w]);
} else {
K[i][w] = K[i - 1][w];
}
}
}
return K[n][W];
}
public static void main(String[] args) {
int[] values = {60, 100, 120};
int[] weights = {10, 20, 30};
int W = 50;
int n = values.length;
System.out.println("Maximum value in Knapsack = " + knapsack(W, weights, values, n));
}
}Giải thích:
- Xác định trạng thái: Trạng thái ở đây là
K[i][w]– giá trị tối đa có thể đạt được vớiivật phẩm và sức chứa balôw. - Công thức truy hồi: Nếu vật phẩm thứ
icó thể cho vào balô, giá trị tối đa là:
K[i][w] = max(values[i-1] + K[i-1][w-weights[i-1]], K[i-1][w]) - Điều kiện cơ sở: Khi không có vật phẩm nào hoặc balô có sức chứa bằng 0, giá trị tối đa là 0.
- Tính toán và lưu trữ: Kết quả của mỗi trạng thái được lưu trong bảng
K.
Độ phức tạp:
- Thời gian: O(n * W), trong đó
nlà số lượng vật phẩm vàWlà sức chứa của balô. - Không gian: O(n * W), vì cần bảng
Kđể lưu trữ kết quả cho từng cặpivàw.
Các vấn đề qui hoạch động thường gặp:
- Bài toán balô (Knapsack problem).
- Bài toán đường đi ngắn nhất (Shortest Path): Floyd-Warshall, Bellman-Ford.
- Bài toán xâu con chung dài nhất (Longest Common Subsequence – LCS).
- Bài toán phân tích chuỗi (String Parsing): Sử dụng DP để tìm lời giải tối ưu cho các vấn đề liên quan đến xử lý chuỗi, ví dụ như kiểm tra tính đối xứng (Palindrome), chỉnh sửa chuỗi (Edit Distance).
Phân loại qui hoạch động:
- Top-down (Memoization): Sử dụng đệ quy, bắt đầu từ bài toán lớn, chia nhỏ dần và lưu lại kết quả của từng bài toán con trong quá trình quay lui. Khi gặp lại bài toán con đã giải, chỉ cần sử dụng kết quả đã lưu.
- Bottom-up (Tabulation): Bắt đầu giải từ các bài toán con nhỏ nhất, lưu kết quả trong bảng và dùng các kết quả này để tính các bài toán lớn hơn.
Ưu điểm của qui hoạch động:
- Giảm chi phí tính toán: Giải quyết hiệu quả các bài toán có nhiều bài toán con trùng lặp.
- Hiệu suất cao: Giảm thời gian chạy từ đệ quy đơn giản (có thể là O(2^n)) xuống còn O(n) hoặc O(n^2) tùy thuộc vào bài toán.
Qui hoạch động là một phương pháp mạnh mẽ để giải quyết các bài toán tối ưu hóa bằng cách giải quyết các bài toán con chồng lấn một cách hiệu quả. Phương pháp này đặc biệt hữu ích trong các bài toán phức tạp với nhiều bài toán con cần tính toán lặp lại, giúp tối ưu hóa thời gian chạy và không gian bộ nhớ.
