Áp dụng DP trong các bài toán thực tế

7.1 Tối ưu hóa thuật toán động.

Tối ưu hóa thuật toán động nhằm cải thiện hiệu quả về thời gian và không gian của chúng. Có nhiều phương pháp tối ưu hóa khác nhau, bao gồm sử dụng memoization, giảm bộ nhớ sử dụng và tối ưu hóa đệ quy.

1. Memoization:

Memoization là một kỹ thuật lưu trữ kết quả tính toán để tránh việc tính toán lại cùng một bài toán con.

Ví dụ:

Trong bài toán đổi tiền xu, nếu sử dụng cách tiếp cận đệ quy, có thể lưu trữ kết quả cho các tổng đã tính để tránh tính toán lại.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

2. Giải pháp dùng bảng (Bottom-Up):

Giải pháp dùng bảng (bottom-up) xây dựng bảng giải pháp cho tất cả các bài toán con có thể từ trường hợp cơ bản đến bài toán mục tiêu. Cách này giúp tránh chi phí từ các lời gọi đệ quy.

Ví dụ:

Trong bài toán ba lô, xây dựng bảng các lượng tối thiểu của đồng xu cho mỗi tổng từ 0 đến S.

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

3. Giảm bộ nhớ sử dụng:

Trong một số bài toán, có thể tối ưu hóa việc sử dụng bộ nhớ bằng cách giảm kích thước bảng hoặc mảng được sử dụng để lưu trữ các kết quả trung gian.

Ví dụ:

Trong bài toán ba lô, có thể sử dụng mảng một chiều thay vì bảng hai chiều nếu chỉ lưu trữ hàng hiện tại và hàng trước đó.

def knapsack_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

4. Đệ quy đuôi:

Đệ quy đuôi là một lời gọi đệ quy được thực hiện cuối cùng của hàm. Điều này cho phép trình biên dịch hoặc thông dịch tối ưu hóa stack các lời gọi.

Ví dụ:

Trong bài toán tính số Fibonacci, có thể sử dụng đệ quy đuôi với accumulator của kết quả.

7.2 Áp dụng lập trình động trong các bài toán thực tế.

Lập trình độ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ế, sinh học thông tin và nghiên cứu hoạt động. Dưới đây là một số ví dụ về sử dụng của nó trong các bài toán thực tế:

1. Tối ưu hóa hành trình và hậu cần:

Trong các bài toán hậu cần và hệ thống vận tải, lập trình động được sử dụng để tìm các hành trình tối ưu và giảm thiểu chi phí.

Ví dụ:

Bài toán người bán hàng (Travelling Salesman Problem, TSP) — tìm đường ngắn nhất đi qua tất cả các thành phố.

def tsp(graph, start):
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]

    def visit(city, visited):
        if visited == (1 << n) - 1:
            return graph[city][start]
        if dp[city][visited] is not None:
            return dp[city][visited]
        result = float('inf')
        for next_city in range(n):
            if visited & (1 << next_city) == 0:
                result = min(result, graph[city][next_city] + visit(next_city, visited | (1 << next_city)))
        dp[city][visited] = result
        return result

    return visit(start, 1 << start)

2. Căn chỉnh chuỗi trong sinh học thông tin:

Trong sinh học thông tin, lập trình động được sử dụng cho việc căn chỉnh các chuỗi DNA, RNA và protein.

Ví dụ:

Thuật toán Needleman-Wunsch cho căn chỉnh toàn cục các chuỗi và thuật toán Smith-Waterman cho căn chỉnh cục bộ.

def lcs(X, Y):
    m, n = len(X), 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]

3. Các tính toán tài chính và lập kế hoạch kinh tế:

Lập trình động được áp dụng để tối ưu hóa các danh mục đầu tư, quản lý rủi ro và lập kế hoạch sản xuất.

Ví dụ:

Bài toán về đổi tiền xu và bài toán ba lô được sử dụng để quản lý tài sản và phân bổ tài nguyên tối ưu nhất.

4. Quản lý kho hàng và sản xuất:

Trong sản xuất và quản lý kho hàng, lập trình động giúp tối ưu hóa các quy trình và giảm thiểu chi phí.

Ví dụ:

Mô hình quản lý kho hàng (Inventory Management Model) để giảm thiểu chi phí lưu trữ và đặt hàng sản phẩm.

5. Học máy và trí tuệ nhân tạo:

Trong học máy, lập trình động được sử dụng để tối ưu hóa các thuật toán và tìm kiếm các cực trị toàn cầu.

Ví dụ:

Các thuật toán học tập dựa trên lập trình động, chẳng hạn như phương pháp lan truyền ngược trong mạng nơ-ron.