Hiểu rõ hơn về Thuật toán quy hoạch động

NỘI DUNG

Trong các cuộc thi học sinh giỏi cũng như trong rất nhiều ứng dụng lập trình. Thuật toán quy hoạch động thường là một thuật toán tối ưu để xử lý các bài toán phức tạp, các bài toán kinh điển. Trong bài viết này chúng ta sẽ cùng tìm hiểu rõ hơn về thuật toán quy hoạch động nhé.

Thuật toán quy hoạch động là gì?

Thuật toán quy hoạch động (Dynamic Programming) là một kỹ thuật giải quyết các bài toán tối ưu trong đó bài toán gốc được phân rã thành các bài toán con nhỏ hơn, lặp lại giải quyết các bài toán con này và sử dụng các giá trị được tính toán để giải quyết bài toán gốc.

Kỹ thuật này thường được sử dụng để giải quyết các bài toán tối ưu trong đó ta cần tìm một giải pháp tốt nhất trong tập các giải pháp có thể có. Quy hoạch động làm việc bằng cách lưu trữ các kết quả của các bài toán con đã được giải quyết và sử dụng chúng để giải quyết các bài toán con lớn hơn. Kỹ thuật này còn giúp giảm thiểu thời gian tính toán, đặc biệt là trong các bài toán mà phải tính toán nhiều lần các giá trị giống nhau.

Thuật toán quy hoạch động thường được áp dụng trong nhiều lĩnh vực như khoa học máy tính, kinh tế học, kỹ thuật, vật lý, hóa học, sinh học, và nhiều lĩnh vực khác.

Lịch sử thuật toán quy hoạch động

Thuật toán quy hoạch động được phát triển vào những năm 1940-1950 bởi nhà toán học Richard Bellman trong nỗ lực giải quyết các bài toán tối ưu liên quan đến công nghiệp và quân sự của Mỹ trong thời kỳ Chiến tranh thế giới thứ II.

Trong quá trình nghiên cứu, Bellman đã phát hiện ra một mẫu chung trong các bài toán tối ưu: các bài toán tối ưu thường có cấu trúc phân tách và tái sử dụng. Ông đã đặt ra một câu hỏi: liệu có cách nào tận dụng những gì đã biết về bài toán để giảm thiểu thời gian tính toán? Để giải quyết vấn đề này, Bellman đã đề xuất kỹ thuật quy hoạch động, nơi các bài toán tối ưu được phân tách thành các bài toán con nhỏ hơn, được giải quyết độc lập và được lưu trữ để sử dụng lại.

Sau đó, kỹ thuật quy hoạch động đã được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, bao gồm khoa học máy tính, kinh tế, kỹ thuật, khoa học và nhiều lĩnh vực khác. Hiện nay, nó là một trong những kỹ thuật quan trọng nhất trong lĩnh vực giải quyết bài toán tối ưu và được áp dụng rộng rãi trong các lĩnh vực công nghiệp và nghiên cứu.

Các phương pháp của thuật toán quy hoạch động

Phương pháp bottom-up (còn được gọi là phương pháp lập bảng)

Phương pháp này bắt đầu từ việc giải quyết các bài toán con nhỏ nhất và sau đó dần dần giải quyết các bài toán lớn hơn bằng cách sử dụng kết quả đã tính toán trước đó.
Các kết quả tính toán được lưu trữ trong một bảng hoặc mảng hai chiều.
Khi tìm kiếm lời giải cho một bài toán lớn hơn, ta chỉ cần truy xuất giá trị trong bảng hoặc mảng đã tính toán trước đó, giúp giảm thiểu thời gian tính toán.

Phương pháp top-down (còn được gọi là phương pháp đệ quy)

Phương pháp này bắt đầu từ giải quyết bài toán lớn nhất, sau đó dần dần chia nhỏ bài toán thành các bài toán con nhỏ hơn để giải quyết.
Trong phương pháp này, các giá trị tính toán được lưu trữ trong một bộ nhớ đệ quy.
Phương pháp này thường được sử dụng khi ta chỉ quan tâm đến một phần của bài toán lớn hơn, hoặc khi ta không thể tính toán tất cả các giá trị nhỏ trong bảng hoặc mảng.

Cả hai phương pháp đều có thể được sử dụng để giải quyết các bài toán tối ưu, tuy nhiên, phương pháp bottom-up thường nhanh hơn và chiếm ưu thế trong hầu hết các trường hợp.

Các bước thực hiện thuật toán quy hoạch động

Thuật toán quy hoạch động có thể được thực hiện bằng các bước sau:

Bước 1. Xác định phương trình truy hồi (recurrence equation) của bài toán: Đây là bước quan trọng nhất trong thuật toán quy hoạch động. Phương trình truy hồi là công thức tính toán giá trị của bài toán lớn dựa trên các bài toán con nhỏ hơn. Ví dụ, trong bài toán tìm dãy con tăng dài nhất, phương trình truy hồi có thể là “L(i) = max(1 + L(j)) với j<i và arr[j]<arr[i]”, trong đó “L(i)” là độ dài dãy con tăng dài nhất kết thúc bằng phần tử thứ i của dãy số.

Bước 2. Xác định điểm khởi đầu (base case): Điểm khởi đầu là giá trị cần tính toán trước khi áp dụng phương trình truy hồi. Ví dụ, trong bài toán tìm dãy con tăng dài nhất, điểm khởi đầu có thể là “L(i) = 1” với mọi i.

Bước 3. Thiết lập bảng phương án (memoization table) để lưu trữ kết quả tính toán cho các bài toán con. Bảng phương án có thể là một ma trận hoặc một mảng một chiều.

Bước 4. Thi hành phương trình truy hồi từ điểm khởi đầu đến điểm kết thúc (nếu có): Áp dụng phương trình truy hồi để tính toán giá trị của bài toán lớn dựa trên các bài toán con nhỏ hơn, và lưu trữ kết quả tính toán vào bảng phương án.

Bước 5. Trích xuất kết quả từ bảng phương án (nếu có): Sau khi tính toán các giá trị của bài toán lớn, trích xuất kết quả cuối cùng từ bảng phương án.

Bước 6. Tối ưu hóa (nếu cần): Nếu thuật toán quy hoạch động trả về giá trị tối ưu cho bài toán, có thể áp dụng các phương pháp tối ưu hóa để cải thiện hiệu suất của thuật toán.

Tóm lại, các bước chính trong thuật toán quy hoạch động bao gồm xác định phương trình truy hồi, xác định điểm khởi đầu, thiết lập bảng phương án, thi hành phương trình truy hồi, trích xuất kết quả và tối ưu hóa nếu cần thiết. Sau khi hoàn thành các bước này, ta sẽ có được giá trị tối ưu cho bài toán lớn dựa trên các bài toán con nhỏ hơn, và có thể trả về kết quả cuối cùng cho người dùng.

Ví dụ về thuật toán quy hoạch động

Để rõ hơn, chúng ta có thể thấy cách thực hiện thuật toán quy hoạch động thông qua ví dụ sau:

Bài toán: Tìm giá trị lớn nhất của dãy con không liên tiếp trong một mảng.

Bước 1. Xác định phương trình truy hồi: Gọi “f(i)” là giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i trong mảng. Nếu không lấy phần tử tại vị trí i, giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i sẽ bằng giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i-1: f(i) = f(i-1). Nếu lấy phần tử tại vị trí i, giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i sẽ bằng giá trị tại vị trí i cộng với giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i-2: f(i) = arr(i) + f(i-2). Phương trình truy hồi sẽ là: f(i) = max(f(i-1), arr(i) + f(i-2)).

Bước 2. Xác định điểm khởi đầu: f(0) = 0 (không có phần tử nào trong dãy con).

Bước 3. Thiết lập bảng phương án: Tạo một mảng “dp” với độ dài bằng độ dài của mảng ban đầu, để lưu trữ giá trị của f(i).

Để giải quyết bài toán tìm giá trị lớn nhất của dãy con không liên tiếp trong một mảng, chúng ta có thể sử dụng thuật toán quy hoạch động. Bảng phương án cho bài toán này có thể được lập như sau:

Ví dụ cho mảng arr = [1, 2, 3, 1, 5]:

i 0 1 2 3 4
arr 1 2 3 1 5
dp 1 2 3 3 8

Trong đó:

– Vị trí i tương ứng với chỉ số trong mảng arr.
– Giá trị arr[i] là giá trị của phần tử ở vị trí i trong mảng arr.
– Giá trị dp[i] là giá trị lớn nhất của dãy con không liên tiếp kết thúc tại vị trí i.

Để tính giá trị dp[i], chúng ta có thể sử dụng công thức sau:

– Nếu i = 0, thì dp[i] = arr[0].
– Nếu i = 1, thì dp[i] = max(arr[0], arr[1]).
– Nếu i > 1, thì dp[i] = max(dp[i-1], arr[i] + dp[i-2]).

Khi đã tính được giá trị của dp[n-1], trong đó n là độ dài của mảng arr, giá trị đó sẽ là giá trị lớn nhất của dãy con không liên tiếp trong mảng arr.

Chú ý rằng, trong ví dụ trên, dãy con không liên tiếp lớn nhất là [1, 3, 5], với tổng bằng 9.

Bước 4. Thi hành phương trình truy hồi: Duyệt qua từng phần tử trong mảng, tính toán giá trị f(i) bằng cách áp dụng phương trình truy hồi và lưu trữ giá trị này vào mảng “dp”.

Bước 5. Trích xuất kết quả: Kết quả là giá trị lớn nhất của các giá trị f(i) tính được.

Bước 6. Tối ưu hóa: Không cần thiết trong trường hợp này.

Với các bước trên, chúng ta có thể giải quyết bài toán tìm giá trị lớn nhất của dãy con không liên tiếp trong một mảng bằng thuật toán quy hoạch động.

Dưới đây là một đoạn mã Python để giải quyết bài toán tìm giá trị lớn nhất của dãy con không liên tiếp trong một mảng sử dụng thuật toán quy hoạch động:

def find_max_sum(arr):
    n = len(arr)
    if n == 0:
        return 0
    if n == 1:
        return arr[0]
    dp = [0] * n
    dp[0] = arr[0]
    dp[1] = max(arr[0], arr[1])
    for i in range(2, n):
        dp[i] = max(dp[i-1], arr[i] + dp[i-2])
    return dp[n-1]
# Kiểm tra test thử:
arr = [1, 2, 3, 1, 5]
print(find_max_sum(arr))

Hàm “find_max_sum” này nhận một mảng “arr” và trả về giá trị lớn nhất của dãy con không liên tiếp trong mảng đó. Trong đó, biến “n” là độ dài của mảng “arr”, biến “dp” là mảng lưu trữ giá trị f(i), và hàm “max” được sử dụng để so sánh giá trị lớn nhất.

Test thử: Kết quả sẽ là 9, tương ứng với giá trị lớn nhất của dãy con không liên tiếp trong mảng arr là [1, 3, 5].

Dưới đây là một đoạn mã C++ để giải quyết bài toán tìm giá trị lớn nhất của dãy con không liên tiếp trong một mảng sử dụng thuật toán quy hoạch động:

#include <bits/stdc++.h> 
using namespace std; 

int find_max_sum(int arr[], int n) 
{ 
    int dp[n]; 
    dp[0] = arr[0]; 
    dp[1] = max(arr[0], arr[1]); 
    for (int i = 2; i < n; i++) 
        dp[i] = max(dp[i-1], arr[i]+dp[i-2]); 
    return dp[n-1]; 
} 

int main() 
{ 
    int arr[] = {1, 2, 3, 1, 5}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << find_max_sum(arr, n) << endl; 
    return 0; 
}

Hàm “find_max_sum” này nhận một mảng “arr” và số nguyên “n” biểu thị độ dài của mảng. Nó trả về giá trị lớn nhất của dãy con không liên tiếp trong mảng đó. Trong đó, mảng “dp” lưu trữ giá trị f(i), và hàm “max” được sử dụng để so sánh giá trị lớn nhất.

Ưu nhược điểm của Thuật toán quy hoạch động

Ưu điểm

Hiệu quả: Với thuật toán quy hoạch động, chúng ta có thể tìm được nghiệm tối ưu cho nhiều bài toán phức tạp với độ phức tạp tính toán thấp hơn so với các phương pháp giải quyết khác.

Độ chính xác cao: Vì thuật toán quy hoạch động sử dụng phương pháp truy hồi và lưu trữ các giá trị trung gian, do đó kết quả thu được luôn là tối ưu.

Dễ dàng cài đặt: Thuật toán quy hoạch động có cấu trúc rõ ràng và dễ dàng cài đặt, vì vậy nó thường được sử dụng trong các chương trình thực tế.

Nhược điểm

Khả năng lưu trữ lớn: Thuật toán quy hoạch động cần lưu trữ tất cả các giá trị trung gian để tính toán kết quả, do đó cần sử dụng một lượng bộ nhớ lớn hơn so với các phương pháp khác.

Không thể áp dụng cho mọi bài toán: Thuật toán quy hoạch động không phải là giải pháp cho mọi bài toán, chỉ áp dụng cho những bài toán có cấu trúc con tối ưu hóa và có thể phân tích được bằng cách truy hồi.

Tóm lại, thuật toán quy hoạch động là một phương pháp giải quyết bài toán phổ biến và hiệu quả. Tuy nhiên, việc áp dụng thuật toán này cần phân tích kỹ càng bài toán để đảm bảo tính khả thi và hiệu quả của thuật toán.

20 bài toán phổ biến có thể áp dụng thuật toán quy hoạch động

Dưới đây là 20 bài toán phổ biến có thể được giải quyết bằng thuật toán quy hoạch động:

Tìm dãy con tăng dài nhất trong một dãy số.
Tìm dãy con không giảm dài nhất trong một dãy số.
Tìm đường đi ngắn nhất trong đồ thị có trọng số.
Tìm lời giải tối ưu cho bài toán cắt thanh gỗ.
Tìm lời giải tối ưu cho bài toán cái túi.
Tìm lời giải tối ưu cho bài toán xếp ba lô.
Tìm lời giải tối ưu cho bài toán chia tiền.
Tìm lời giải tối ưu cho bài toán dãy con chung dài nhất.
Tìm lời giải tối ưu cho bài toán xâu con chung dài nhất.
Tìm lời giải tối ưu cho bài toán dãy con không giao nhau lớn nhất.
Tìm lời giải tối ưu cho bài toán dãy con liên tiếp có tổng lớn nhất.
Tìm lời giải tối ưu cho bài toán dãy con liên tiếp có tích lớn nhất.
Tìm lời giải tối ưu cho bài toán dãy con liên tiếp có tích bằng một giá trị cố định.
Tìm lời giải tối ưu cho bài toán tìm số Fibonacci thứ n.
Tìm lời giải tối ưu cho bài toán xếp đồng xu.
Tìm lời giải tối ưu cho bài toán tìm đường đi bậc thang trong một ma trận.
Tìm lời giải tối ưu cho bài toán phân chia trò chơi.
Tìm lời giải tối ưu cho bài toán tìm chuỗi con với số lần lặp lại lớn nhất.
Tìm lời giải tối ưu cho bài toán sắp xếp một dãy số.
Tìm lời giải tối ưu cho bài toán sắp xếp một dãy số với một số lần hoán đổi giới hạn.

Chúc các bạn học tốt!

Lập trình C/C++, Lập trình Python