CÙNG CHAT GPT TÌM HIỂU THUẬT TOÁN QUY HOẠCH ĐỘNG

THUẬT TOÁN QUY HOẠCH ĐỘNG

    Thuật toán quy hoạch động là một phương pháp giải quyết bài toán tối ưu bằng cách tìm kiếm và lưu trữ các giải pháp tối ưu cho các phần con của bài toán, sau đó sử dụng các giải pháp đã lưu trữ này để tính toán giải pháp tối ưu cho toàn bộ bài toán.

    Phương pháp quy hoạch động thường được sử dụng cho các bài toán tối ưu động, tức là bài toán có cấu trúc tương tự nhau nhưng kích thước khác nhau. Một số ví dụ bài toán có thể giải quyết bằng thuật toán quy hoạch động bao gồm: tìm kiếm đường đi ngắn nhất trong một đồ thị, phân tích cú pháp và biên dịch, tối ưu hóa quy trình sản xuất,…

    Thuật toán quy hoạch động có hai bước chính:

    – Bước tối ưu hoá con: Giải quyết các bài toán con tối ưu cho từng phần tử của bài toán lớn hơn, lưu trữ kết quả vào một bảng lưu trữ để sử dụng sau này.

    – Bước xây dựng giải pháp tối ưu: Sử dụng kết quả tối ưu của các bài toán con đã giải quyết để tìm giải pháp tối ưu cho toàn bộ bài toán.

    Trong quá trình thực hiện, thuật toán quy hoạch động thường sử dụng một bảng lưu trữ kết quả đã tính toán, được gọi là bảng quy hoạch động (dynamic programming table), để lưu trữ các kết quả tối ưu và giúp tăng tốc độ tính toán. Khi có yêu cầu tính toán giải pháp tối ưu cho một phần tử trong bài toán, thuật toán truy xuất đến bảng quy hoạch động để xem nếu kết quả đã được tính toán trước đó, nếu có, nó sẽ sử dụng kết quả đó, ngược lại nó sẽ tính toán giải pháp tối ưu cho phần tử đó và lưu kết quả vào bảng quy hoạch động để sử dụng cho các tính toán tiếp theo.

    Một số ví dụ điển hình về bài toán sử dụng thuật toán quy hoạch động:

    Tìm đường đi ngắn nhất trong một đồ thị: Đây là một ví dụ phổ biến về việc sử dụng quy hoạch động. Ví dụ, bài toán tìm đường đi ngắn nhất từ một đỉnh đến một đỉnh khác trong một đồ thị được giải quyết bằng cách lưu trữ các giải pháp tối ưu cho các đỉnh nhỏ hơn và sử dụng chúng để tính toán giải pháp tối ưu cho đỉnh lớn hơn.

    Bài toán túi lớn (knapsack problem): Đây là một bài toán tối ưu hóa, trong đó bạn cần đưa ra quyết định về việc chọn các món hàng để đặt vào một túi với một khối lượng tối đa. Thuật toán quy hoạch động có thể được sử dụng để tìm kiếm giải pháp tối ưu cho bài toán này bằng cách tính toán giá trị tối ưu cho các phần tử con của bài toán.

    Bài toán dãy con tăng dài nhất (longest increasing subsequence problem): Bài toán này yêu cầu tìm dãy con tăng dài nhất trong một dãy số cho trước. Thuật toán quy hoạch động có thể được sử dụng để giải quyết bài toán này bằng cách tính toán chiều dài của dãy con tăng dài nhất kết thúc tại mỗi phần tử của dãy số.

BÀI TOÁN CỤ THỂ VÀ HƯỚNG DẪN GIẢI

Bài toán tính số Fibonacci thứ n

Với bài toán này, chúng ta cần tính giá trị của số Fibonacci thứ n bằng cách cộng hai số Fibonacci trước đó (F(n-1) và F(n-2)). Ví dụ, F(0) = 0, F(1) = 1, F(2) = F(1) + F(0) = 1, F(3) = F(2) + F(1) = 2, F(4) = F(3) + F(2) = 3, và cứ tiếp tục như vậy.

Chúng ta có thể giải bài toán này bằng cách sử dụng thuật toán quy hoạch động như sau:

• Khởi tạo hai biến f0 và f1 với giá trị lần lượt là 0 và 1.
• Sử dụng vòng lặp để tính toán số Fibonacci thứ n bằng cách cộng hai số trước đó và cập nhật f0 và f1 tương ứng.
• Sau khi vòng lặp kết thúc, giá trị của f1 sẽ là số Fibonacci thứ n.

CODE Python

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    f0 = 0
    f1 = 1
    for i in range(2, n+1):
        fn = f0 + f1
        f0 = f1
        f1 = fn
    return f1

Ví dụ, nếu chúng ta muốn tính số Fibonacci thứ 6, chúng ta có thể gọi hàm fibonacci(6) và sẽ nhận được kết quả là 8.

PHÂN TÍCH VÀ GIẢI BÀI TOÁN TÚI LỚN

Bài toán túi lớn (Knapsack problem) là một bài toán tối ưu hóa trong lĩnh vực tối ưu hóa tổ hợp. Bài toán này được phát biểu như sau:

Cho một túi có khối lượng tối đa là W và một tập hợp gồm n vật phẩm. Mỗi vật phẩm có khối lượng w[i] và giá trị v[i]. Nhiệm vụ của chúng ta là chọn một số vật phẩm để đặt vào túi sao cho tổng khối lượng của các vật phẩm trong túi không vượt quá W và tổng giá trị của các vật phẩm được chọn là lớn nhất.

Có hai phiên bản của bài toán túi lớn:

1. Bài toán túi lớn 0/1 (0/1 knapsack problem): Mỗi vật phẩm có thể được chọn hoặc không được chọn. Điều này có nghĩa là chúng ta không thể lấy một phần của một vật phẩm.

2. Bài toán túi lớn không giới hạn (unbounded knapsack problem): Mỗi vật phẩm có thể được chọn bất kỳ số lần nào. Điều này có nghĩa là chúng ta có thể lấy một phần của một vật phẩm.

    Để giải bài toán túi lớn 0/1, chúng ta có thể sử dụng thuật toán quy hoạch động. Bước giải quyết bài toán sẽ như sau:

    – Khởi tạo ma trận K có kích thước (n+1) x (W+1) với tất cả giá trị bằng 0. Ma trận này sẽ được sử dụng để lưu trữ giá trị tối ưu của bài toán con.

    – Sử dụng hai vòng lặp để điền vào ma trận K. Với mỗi vật phẩm i và trọng lượng tối đa w, giá trị của K[i][w] được tính bằng cách chọn giữa hai trường hợp: (a) Không lấy vật phẩm i, tức là giá trị của K[i-1][w], hoặc (b) Lấy vật phẩm i, tức là giá trị của K[i-1][w-w[i]] cộng với giá trị của vật phẩm i. Chúng ta chọn giá trị lớn hơn trong hai trường hợp này và lưu giá trị đó vào K[i][w].

    – Giá trị tối ưu của bài toán sẽ nằm ở K[n][W]. Các vật phẩm được chọn có thể được tìm thấy bằng cách quay lại ma trận K và xem xét các giá trị K[i][w] đã biết.

GIẢI THÍCH THUẬT TOÁN QUY HOẠCH ĐỘNG ĐỂ GIẢI BÀI TOÁN TÚI LỚN 0/1 CỤ THỂ HƠN.

    – Bước 1: Khởi tạo ma trận K

    Đầu tiên, chúng ta cần khởi tạo một ma trận K có kích thước (n+1) x (W+1) với tất cả các giá trị bằng 0. Ma trận này sẽ được sử dụng để lưu trữ giá trị tối ưu của bài toán con. Các hàng trong ma trận K tương ứng với các vật phẩm (bao gồm vật phẩm 0, tức là không có vật phẩm nào được chọn), và các cột tương ứng với các trọng lượng từ 0 đến W.

    – Bước 2: Tính giá trị tối ưu của bài toán con

    Sau khi khởi tạo ma trận K, chúng ta sử dụng hai vòng lặp để điền vào ma trận K. Với mỗi vật phẩm i và trọng lượng tối đa w, giá trị của K[i][w] được tính bằng cách chọn giữa hai trường hợp:

    (a) Không lấy vật phẩm i: tức là giá trị của K[i-1][w]

    (b) Lấy vật phẩm i: tức là giá trị của K[i-1][w-w[i]] cộng với giá trị của vật phẩm i

    Chúng ta chọn giá trị lớn hơn trong hai trường hợp này và lưu giá trị đó vào K[i][w].

    Đây là công thức truy hồi để tính K[i][w]:

        K[i][w] = max(K[i-1][w], K[i-1][w-w[i]] + v[i])

    – Bước 3: Tìm giá trị tối ưu của bài toán

    Giá trị tối ưu của bài toán là K[n][W]. Các vật phẩm được chọn có thể được tìm thấy bằng cách quay lại ma trận K và xem xét các giá trị K[i][w] đã được tính toán.

    Một cách cụ thể để tìm các vật phẩm được chọn là duyệt ma trận K theo thứ tự ngược từ K[n][W] đến K[0][0]. Khi tìm thấy một giá trị K[i][w] khác với K[i-1][w], tức là chúng ta đã lấy vật phẩm i. Sau đó, giảm trọng lượng w đi w[i] và tiếp tục tìm kiếm trong K[i-1][w-w[i]].

    Đây là code Python để giải bài toán túi lớn 0/1 bằng thuật toán quy hoạch động:

def knapsack_01(W, wt, v, n):
    # Khởi tạo ma trận K
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    # Tính giá trị tối ưu của bài toán con
    for i in range(n+1):
        for w in range(W+1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(v[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    # Tìm giá trị tối ưu của bài toán
    max_value = K[n][W]
    # Tìm các vật phẩm được chọn
    items = []
    w = W
    for i in range(n, 0, -1):
        if max_value <= 0:
            break
        if max_value == K[i-1][w]:
            continue
        else:
            items.append(i-1)
            max_value -= v[i-1]
            w -= wt[i-1]
    # Trả về giá trị tối ưu và danh sách các vật phẩm được chọn
    return K[n][W], items

    Hàm knapsack_01 nhận vào bốn đối số:

        W: trọng lượng tối đa của túi

        wt: một mảng chứa trọng lượng của các vật phẩm

        v: một mảng chứa giá trị của các vật phẩm

        n: số lượng các vật phẩm

    Hàm trả về một tuple gồm hai phần tử:

        Giá trị tối ưu của bài toán

        Danh sách các vật phẩm được chọn

Để giải quyết bài toán túi lớn 0/1, chỉ cần gọi hàm knapsack_01 và truyền vào các đối số tương ứng. Ví dụ:

W = 50
wt = [10, 20, 30]
v = [60, 100, 120]
n = len(v)
max_value, items = knapsack_01(W, wt, v, n)
print("Giá trị tối ưu của bài toán:", max_value)
print("Danh sách các vật phẩm được chọn:", items)

    Kết quả sẽ là:

Giá trị tối ưu của bài toán: 220
Danh sách các vật phẩm được chọn: [1, 2]

    Điều này có nghĩa là để đạt được giá trị tối ưu là 220, chúng ta cần lấy hai vật phẩm, có trọng lượng lần lượt là 20 và 30.

GIẢI BÀI TOÁN TÚI LỚN KHÔNG GIỚI HẠN (UNBOUNDED KNAPSACK PROBLEM)

    Bài toán túi lớn không giới hạn là một bài toán tối ưu hóa trong đó ta cần chọn một tập hợp các đồ vật có giá trị và khối lượng khác nhau để bỏ vào một cái túi có sức chứa không giới hạn sao cho giá trị tổng của các đồ vật được chọn là lớn nhất.

    Để giải quyết bài toán này, ta sử dụng phương pháp quy hoạch động (dynamic programming). Đầu tiên, ta khởi tạo một bảng 2 chiều dp với số hàng tương ứng với số lượng đồ vật có thể chọn, số cột tương ứng với tổng khối lượng từ 0 đến khối lượng tối đa mà túi có thể chứa. Mỗi ô dp[i][j] trên bảng chứa giá trị tối đa có thể đạt được bằng cách chọn các đồ vật từ đầu đến vị trí i và sử dụng túi có sức chứa j.

    Giả sử weights là mảng chứa khối lượng của các đồ vật, values là mảng chứa giá trị của các đồ vật, và capacity là khối lượng tối đa mà túi có thể chứa. Ta sẽ điền giá trị cho các ô trên bảng dp bằng cách sử dụng công thức sau:

                dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1])

    Trong đó, i là chỉ số của đồ vật hiện tại, j là khối lượng tối đa có thể sử dụng, weights[i-1] là khối lượng của đồ vật hiện tại và values[i-1] là giá trị của đồ vật hiện tại.

    Giá trị lớn nhất trên bảng dp sẽ tương ứng với giá trị lớn nhất có thể đạt được bằng cách chọn một tập hợp các đồ vật có khối lượng khác nhau để bỏ vào túi.

    Dưới đây là mã giả của thuật toán quy hoạch động để giải bài toán túi lớn không giới hạn:

def unboundedKnapsack(capacity, weights, values):
  n = len(weights)
  dp = [[0 for j in range(capacity+1)] for i in range(n+1)]
  for i in range(1, n+1):
    for j in range(1, capacity+1):
      if weights[i-1] <= j:
        dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1])
      else:
        dp[i][j] = dp[i-1][j]
  return dp[n][capacity]

    Trong hàm unboundedKnapsack(), vòng lặp đầu tiên khởi tạo bảng dp với tất cả giá trị bằng 0. Vòng lặp sau đó điền giá trị cho các ô trên bảng dp sử dụng công thức đã đề cập ở trên.

    Cuối cùng, hàm trả về giá trị lớn nhất có thể đạt được.

    Ví dụ, giả sử ta có 4 đồ vật với khối lượng và giá trị lần lượt là (1, 10), (3, 40), (4, 50), và (5, 70), và túi có thể chứa bất kỳ khối lượng nào. Ta gọi hàm unboundedKnapsack(8, [1, 3, 4, 5], [10, 40, 50, 70]) sẽ trả về giá trị lớn nhất có thể đạt được là 110. Điều này có nghĩa là ta có thể chọn đồ vật thứ 1, 2 và 4 để đạt được giá trị lớn nhất là 110.

Bài viết được tổng hợp từ Chat GPT