Thuật toán quy hoạch động

Khái niệm thuật toán

Quy hoạch động (Dynamic Programming) là một phương pháp giải quyết bài toán tối ưu, dựa trên cách chia bài toán thành những bài toán nhỏ hơn và lưu trữ lại kết quả giải quyết của chúng. Thuật toán Quy hoạch động thường được sử dụng để giải quyết các bài toán tối ưu có cấu trúc lặp đi lặp lại.

Một số thuật toán quy hoạch động phổ biến

Dưới đây là một số thuật toán quy hoạch động phổ biến:

1. Thuật toán Fibonacci: đây là một trong những ví dụ đầu tiên về thuật toán quy hoạch động. Thuật toán này giải quyết bài toán tìm số Fibonacci thứ n bằng cách sử dụng các giá trị Fibonacci nhỏ hơn.
2. Thuật toán Bellman-Ford: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất trong đồ thị có trọng số âm.
3. Thuật toán Dijkstra: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất trong đồ thị có trọng số không âm.
4. Thuật toán Floyd-Warshall: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh trong đồ thị có trọng số.
5. Thuật toán Knapsack: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm cách đựng các vật phẩm vào một túi sao cho giá trị của các vật phẩm đó là lớn nhất và tổng khối lượng không vượt quá giới hạn.
6. Thuật toán Longest Common Subsequence: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm dãy con chung dài nhất của hai chuỗi.
7. Thuật toán Maximum Subarray: đây là thuật toán quy hoạch động được sử dụng để giải quyết bài toán tìm dãy con liên tiếp có tổng lớn nhất trong một mảng số nguyên.

Thuật toán

1. Xác định bài toán con: Chia bài toán ban đầu thành các bài toán con nhỏ hơn, cùng cấu trúc với bài toán ban đầu.
2. Thiết lập công thức truy hồi: Định nghĩa công thức để tính giá trị của bài toán con dựa trên giá trị của các bài toán con nhỏ hơn.
3. Tính toán giá trị tối ưu: Sử dụng công thức truy hồi để tính toán giá trị tối ưu của bài toán ban đầu.
4. Lưu trữ kết quả: Lưu trữ kết quả của các bài toán con để tránh tính toán lại khi cần thiết.

Ví dụ về thuật toán

Bài toán Tìm dãy con tăng dài nhất (Longest Increasing Subsequence Problem)

Cho một dãy số nguyên, tìm một dãy con tăng dài nhất. Ví dụ với dãy số {3, 4, -1, 0, 6, 2, 3} thì dãy con tăng dài nhất là {3, 4, 6} với độ dài là 3.

Bước 1: Xác định bài toán con

• Cho dãy con từ phần tử đầu đến phần tử thứ i, ta tìm được dãy con tăng dài nhất có chứa phần tử thứ i.

Bước 2: Thiết lập công thức truy hồi

• Giả sử L(i) là độ dài dãy con tăng dài nhất chứa phần tử thứ i.
• L(i) = 1 + max(L(j)) với 0 <= j < i và a[j] < a[i], nếu không có j nào thỏa mãn thì L(i) = 1.

Bước 3: Tính toán giá trị tối ưu

• Ta tính giá trị L(i) cho tất cả các phần tử i từ đầu đến cuối dãy.
• Kết quả của bài toán ban đầu là giá trị lớn nhất của L(i).

Bước 4: Lưu trữ kết quả. Lưu trữ giá trị của L(i) cho tất cả các phần tử i từ đầu đến cuối dãy trong một mảng L.

Cài đặt thuật toán dãy con chung dài nhất

Đây là một cách giải bài toán tìm dãy con tăng dài nhất bằng Python:

def longest_increasing_subsequence(arr):
    n = len(arr)
    # Khởi tạo mảng dp với tất cả các phần tử đều là 1
    dp = [1] * n

    # Tính toán dãy con tăng dài nhất bắt đầu từ mỗi vị trí
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # Tìm giá trị lớn nhất trong mảng dp
    max_length = max(dp)

    # Tìm các phần tử của dãy con tăng dài nhất
    result = []
    for i in range(n - 1, -1, -1):
        if dp[i] == max_length:
            result.append(arr[i])
            max_length -= 1
        if max_length == 0:
            break

    # Đảo ngược kết quả để có được dãy con tăng dài nhất
    result.reverse()

    return result

Cách thức hoạt động:

• Sử dụng một mảng dp để lưu trữ độ dài của dãy con tăng dài nhất bắt đầu từ mỗi vị trí của mảng đầu vào arr.
• Ban đầu, tất cả các giá trị trong mảng dp đều được khởi tạo là 1, vì một phần tử đơn lẻ sẽ tạo thành một dãy con tăng dài nhất độ dài 1.
• Tiếp theo, duyệt qua từng cặp phần tử của arr và cập nhật giá trị trong mảng dp. Nếu phần tử thứ i lớn hơn phần tử thứ j, thì ta có thể thêm phần tử thứ i vào dãy con tăng dài nhất bắt đầu từ j, từ đó có thể cập nhật giá trị trong dp.
• Sau khi tính toán xong, tìm giá trị lớn nhất trong mảng dp để biết độ dài của dãy con tăng dài nhất. Từ đó, ta có thể tìm được các phần tử của dãy con tăng dài nhất bằng cách duyệt lại mảng dp và lưu trữ các phần tử có giá trị bằng với độ dài của dãy con tăng dài nhất.
• Cuối cùng, đảo ngược kết quả để có được dãy con tăng dài nhất.