Quy hoạch động là gì?

Quy hoạch động là gì?

Quy hoạch động (Dynamic Programming) là kĩ thuật được được dùng khi có một công thức truy hồi và một (hoặc một vài) trạng thái bắt đầu. Một bài toán được tính bởi các bài toán nhỏ hơn đã tìm ra trước đó, một kĩ thuật giải quyết các bài toán khi có thể giải quyết bài toán đó bằng cách sử dụng lại các bài toán nhỏ hơn đã được giải quyết và lưu lại kết quả.

1. Quy hoạch động là gì?

Theo thầy Lê Minh Hoàng thì

Các thuật toán đệ quy có ưu điểm dễ cài đặt, tuy nhiên do bản chất của quá trình đệ quy, các chương trình này thường kéo theo những đòi hỏi lớn về không gian bộ nhớ và một khối lượng tính toán khổng lồ. Quy hoạch động (Dynamic programming) là một kỹ thuật nhằm đơn giản hóa việc tính toán các công thức truy hồi bằng cách lưu trữ toàn bộ hay một phần kết quả tính toán tại mỗi bước với mục đích sử dụng lại.

Dynamic Programming = Solving Recurrence + Memoization

Hiểu đơn giản, QUY HOẠCH ĐỘNG = GIẢI QUYẾT TRUY HỒI + GHI NHỚ KẾT QUẢ. Quy hoạch động có độ phức tạp đa thức nên sẽ chạy nhanh hơn quay lui và vét cạn.

2. Khi nào thì dùng Quy hoạch động?

Không có một quy tắc chung nào để cho biết một bài toán có giải được bằng quy hoạch động hay không. Tuy nhiên, nếu bài toán có hai tính chất sau thì bạn có thể nghĩ tới quy hoạch động:

  • Có một hệ thức truy hồi. Tức là, bài toán lớn có thể giải quyết dựa vào các bài toán con lồng nhau. Chẳng hạn số Fibonacci f(n) được tính dựa vào hai số thứ f(n-1)f(n-2).
  • Một hoặc nhiều bài toán con đã được giải quyết (biết trạng thái). Ví dụ đối với bài toán tìm số Fibonacci thì số f(0)f(1) là đã biết trước.

bài toán quy hoạch động

Nghe có vẻ giống như đệ quy, một bài toán lớn được chia nhỏ thành các bài toán con lồng nhau. Nhưng, phương pháp quy hoạch động sẽ lưu kết quả của bài toán con này, và khi được gọi, nó sẽ không cần phải tính lại, do đó làm giảm thời gian tính toán.

Ví dụ, đối với bài toán tìm số Fibonacci thứ n, nếu sử dụng đệ quy đơn thuần, chúng ta rất nhiều bài toán con sẽ được tính đi tính lại, điển hình là các số fib(0) và fib(1).

def fib(n):
    if n <= 1:
        return n
    return fib(n -1) + fib(n - 2)

Nếu sử dụng quy hoạch động, mỗi bài toán con fib(i) sẽ được lưu lại trước khi tính những bài toán con lớn hơn. Nhờ đó, mà việc tính toán giảm đi đáng kể, mỗi bài toán con chỉ cần tính đúng một lần.

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

Như vậy, vấn đề mấu chốt ở đây là gì?

Đệ quy chỉ đơn giản là gọi lại chính nó. Quy hoạch động là một cách để giải quyết các vấn đề có cấu trúc cụ thể (cấu trúc con tối ưu) trong đó một vấn đề có thể được chia thành các vấn đề con tương tự như bài toán ban đầu.

Ghi nhớ kết quả là một cách để tối ưu hóa các thuật toán quy hoạch động dựa trên đệ quy. Và, chúng ta không phải giải quyết bài toán con một lần nữa nếu chúng đã được giải quyết.

Rõ ràng người ta có thể gọi đệ quy để giải quyết một bài toán quy hoạch động, nhưng nó không cần thiết. Người ta có thể giải một bài toán quy hoạch động mà không cần đệ quy (chẳng hạn trong bài tính số Fibonacci bằng quy hoạch động ở trên, chúng ta thấy không có lời gọi đệ quy nào cả).

3. Một số ví dụ về Quy hoạch động

Phân tích số nguyên dương

Cho số tự nhiên n 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách. (Bài toán này được viết lại dựa theo sách của thầy Lê Minh Hoàng).

Ví dụ: n = 5 có 7 cách phân tích:

1. 5 = 1 + 1 + 1 + 1 + 1
2. 5 = 1 + 1 + 1 + 2
3. 5 = 1 + 1 + 3
4. 5 = 1 + 2 + 2
5. 5 = 1 + 4
6. 5 = 2 + 3
7. 5 = 5

Lưu ý: n = 0 vẫn coi là có 1 cách phân tích thành tổng các số nguyên dương, là tổng của dãy rỗng.

Để giải bài toán này, chúng ta có thể dùng phương pháp liệt kê tất cả các cách phân tích và đếm số cấu hình. Tuy nhiên, khi số cách phân tích tương đối lớn, phương pháp liệt kê tỏ ra khá chậm. Chẳng hạn với n = 100190569292 cách phân tích.

Nhận xét:

Nếu gọi F[m, v] là số cách phân tích số v thành tổng các số nguyên dương nhỏ hơn hoặc bằng m thì khi đó, các cách phân tích số v thành tổng các số nguyên dương nhỏ hơn hoặc bằng m có thể chia làm hai loại:

  • Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương nhỏ hơn m, tức là số cách phân tích số v thành tổng các số nguyên dương nhỏ hơn hoặc bằng m - 1 và bằng F[m-1, v].
  • Loại 2: Có chứa ít nhất một số m trong phép phân tích. Khi đó nếu trong các cách phân tích loại này ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v - m thành tổng các số nguyên dương nhỏ hơn hoặc bằng m (Lưu ý, điều này chỉ đúng khi không tính lặp lại các hoán vị của một cách). Có nghĩa là về mặt số lượng, số các cách phân tích loại này bằng F[m, v - m].

Trong trường hợp m > v thì rõ ràng chỉ có các cách phân tích loại 1, còn trong trường hợp m ≤ v thì sẽ có cả các cách phân tích loại 1 và loại 2. Vì thế, công thức truy hồi là: $$F[m,v]=\begin{cases} F[m-1,v] &\text{ nếu } m>v\\ F[m-1,v] +F[m,v-m]&\text{ nếu } m \leqslant v \end{cases}$$

Tìm số lượng đồng xu

Cho $N$ đồng xu, giá trị của mỗi đồng là $V_0,V_1,…,V_{N−1}$, và số $S$. Tìm số lượng đồng xu nhỏ nhất để tổng giá trị của chúng bằng $S$ (số lượng đồng xu không giới hạn).

Với bài toán này, chúng ta cần xây dựng và giải các bài toán con lồng (gối) nhau. Với ví dụ của chúng ta, mỗi bài toán con dp(P) với P<= S là bài toán tìm số đồng xu nhỏ nhất để khối lượng của chúng là P. và dp(P) = k chính là số lượng đồng xu nhỏ nhất đó.

Chúng ta sẽ áp dụng phương pháp quy hoạch động bằng cách bắt đầu từ bài toán con dp(0) sau đó tiếp tục với các bài toán con lớn hơn. Lời giải của các bài toán con sẽ được xây dựng lần lượt cho đến chúng ta xây dựng đến bài toán dp(S) và đó chính là kết quả của bài toán lớn. Một điều cần lưu ý với kỹ thuật này là bài toán con tiếp theo sẽ không thể giải được nếu chúng ta chưa giải bài toán con trước đó.

Cuối cùng là phần khó nhất của mọi bài toán quy hoạch động, đó là trả lời câu hỏi: cấu trúc con tối ưu của bài toán này ở đâu. Hay nói một cách khác, làm thế nào để từ những bài toán nhỏ hơn có thể tổ hợp ra lời giải cho bài toán lớn. Với vị dụ kinh điển này, mọi thứ sẽ tương đối đơn giản, nhưng với những bài toán phức tạp hơn, chúng ta cần suy nghĩ và tính toán nhiều hơn.

Quay trở lại với bài toán của chúng ta. Giả sử P là tổng khối lượng của các đồng xu nặng lần lượt là V1, V2, ..., Vj. Để có được khối lượng P, chúng ta cần thêm vài đúng 1 đồng xu nặng U vào khối lượng Q sao cho Q + U = P. Tất nhiên, bài toán con dp(Q) chúng ta đã có lời giải nên chúng ta sẽ biết được cần bao nhiêu đồng xu cho dp(P). Và vì có nhiều đồng xu U (nhiều nhưng hữu hạn) nên chúng ta có thể cần đến nhiều bài toán con trước đó, và dp(p) là giá trị nhỏ nhất sau khi tổng hợp những bài toán con đó.

Ví dụ với n = 3, S = 11, W = [1, 3, 5].

  • Bắt đầu với bài toán con 0 ta có dp(0) = 0
  • Với bài toán con 1, có 1 đồng xu (nặng 1) có thể thêm vào từ 0 đồng xu nào cả. Vậy dp(1) = dp(0) + 1 = 1.
  • Với bài toán con 2, cũng chỉ có 1 đồng xu (nặng 1) có thể thêm vào từ 1 đồng xu. Vậy dp(2) = dp(1) + 1 = 2.
  • Với bài toán con 3, chúng ta có thể thêm 1 đồng xu 3 vào 0 đồng xu hoặc thêm 1 đồng xu 1 vào 2 đồng xu. Rõ ràng là cách đầu tiên cho kết quả nhỏ hơn. Vậy dp(3) = min(dp(2) + 1, dp(0) + 1) = min(3, 1) = 1
  • Cứ tiếp tục như vậy cho đến bài toán S chính là đáp án chúng ta cần tìm.

Về mặt cài đặt, quy hoạch động thường lưu kết quả vào một mảng. Trong ví dụ của chúng ta, mảng dp[0..S] sẽ lưu kết quả cho từng bài toán con. Nói cách khác, dp[P] = k nghĩa là cần ít nhất k đồng xu để có khối lượng là P Toàn bộ mảng này sẽ được tính bằng vòng lặp. Đoạn code sau mô tả toàn bộ quá trình này.

n, S = map(int, input().split())
w = list(map(int, input().split()))
dp = [0] * (S + 1)
dp[0] = 0

for P in range(1, S + 1):
    dp[P] = min(dp[P - x] for x in w if x <= P) + 1

print(dp)
print(dp[S])

# Nếu đầu vào như sau: n = 3, S = 11, w = [1, 3, 5]
# Thì bảng lời giải cho các bài toán con sẽ lần lượt như sau:
# P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11
# ------+--+--+--+--+--+--+--+--+--+--+--
# k = 0 |1 |2 |1 |2 |1 |2 |3 |2 |3 |2 |3

Bạn có thể tham khảo thêm MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG ĐIỂN HÌNH