Phân Tích Thuật Toán Quy Hoạch động - Một Thuật Toán Thần Thánh

Trong bài viết này, Topdev sẽ giới thiệu với các bạn một thuật toán thần thánh: thuật toán quy hoạch động. Nếu bạn tham gia các cuộc thi code, bạn nhất định phải biết thuật toán này.

Gần một nửa các bài thi trong các cuộc thi code cần đến quy hoạch động. Tất nhiên, có những cách khác để giải bài toán đó. Nhưng vì các cuộc thi code đều có giới hạn về thời gian, cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, quy hoạch động là một trong những thuật toán xuất hiện nhiều nhất.

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

Quy hoạch động (dynamic programming) là một phương pháp được sử dụng trong toán học và khoa học máy tính để giải quyết các vấn đề phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Bằng cách giải mỗi bài toán con chỉ một lần và lưu trữ kết quả, nó tránh được các phép tính dư thừa, dẫn đến giải pháp hiệu quả hơn cho nhiều bài toán.

Quy hoạch động (DP) hoạt động như thế nào?

Nguyên lý hoạt động của Dynamic Programming

1. Chia bài toán thành các bài toán con nhỏ hơn: Bài toán ban đầu được chia thành các bài toán con mà mỗi bài toán con là một phần của bài toán lớn hơn. Các bài toán con này thường có tính chất lặp lại.
2. Lưu trữ kết quả của các bài toán con: Để tránh việc tính toán lặp lại các bài toán con nhiều lần, kết quả của chúng được lưu trữ trong một bảng (thường là mảng hoặc ma trận).
3. Sử dụng lại kết quả đã lưu: Khi cần kết quả của một bài toán con nào đó, chương trình sẽ kiểm tra bảng lưu trữ để xem kết quả đã được tính toán trước đó chưa. Nếu đã có, nó sẽ sử dụng lại kết quả đó thay vì tính toán lại từ đầu.

Các bước thực hiện

1. Xác định cấu trúc của bài toán con tối ưu: Hiểu rõ cách mà bài toán lớn được chia thành các bài toán con và cách mà kết quả của các bài toán con này kết hợp lại để giải quyết bài toán lớn.
2. Định nghĩa hàm hồi quy: Xác định công thức hoặc hàm hồi quy để giải quyết bài toán dựa trên các bài toán con. Đây là bước quan trọng để hiểu cách các bài toán con liên kết với nhau.
3. Tính giá trị của bài toán con theo thứ tự từ nhỏ đến lớn: Bắt đầu từ những bài toán con nhỏ nhất và sử dụng công thức hồi quy để tính giá trị của các bài toán con lớn hơn dựa trên các bài toán con nhỏ hơn đã được tính toán trước đó.
4. Lưu trữ kết quả của các bài toán con: Kết quả của mỗi bài toán con được lưu trữ trong bảng để sử dụng lại sau này.
5. Giải quyết bài toán lớn nhất: Sau khi đã tính toán và lưu trữ kết quả của tất cả các bài toán con, sử dụng chúng để giải quyết bài toán ban đầu.

Khi nào thì dùng thuật toán quy hoạch động

Khi nào thì chúng ta cần đến quy hoạch động? Đó là một câu hỏi rất khó trả lời. Không có một công thức nào cho các bài toán như vậy.

Tuy nhiên, có một số tính chất của bài toán mà bạn có thể nghĩ đến quy hoạch động. Dưới đây là hai tính chất nổi bật nhất trong số chúng:

• Bài toán có các bài toán con gối nhau.
• Bài toán có cấu trúc con tối ưu.

Thường thì một bài toán có đủ cả hai tính chất này, chúng ta có thể dùng quy hoạch động được. Một câu hỏi rất thú vị là không dùng quy hoạch động có được không? Câu trả lời là có, nhưng nếu bạn đi thi code, bạn trượt là cái chắc. Để hiểu rõ hơn, chúng ta sẽ tìm hiểu từng tính chất một trong những phần dưới đây

Bài toán con gối nhau

Tương tự như thuật toán chia để trị, quy hoạch động cũng chia bài toán lớn thành các bài toán con nhỏ hơn. Quy hoạch động được sử dụng khi các bài toán con này được gọi đi gọi lại. 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.

Quy hoạch động sẽ không thể áp dụng được (hoặc nói đúng hơn là áp dụng cũng không có tác dụng gì) khi các bài toán con không gối nhau. Ví dụ với thuật toán tìm kiếm nhị phân, quy hoạch động cũng không thể tối ưu được gì cả, bởi vì mỗi khi chia nhỏ bài toán lớn thành các bài toán con, mỗi bài toán cũng chỉ cần giải một lần mà không bao giờ được gọi lại.

Một ví dụ rất điển hình của bài toán con gối nhau là bài toán tính số Fibonacci. Bài toán quá nổi tiếng rồi, chúng ta có thể tính toán số Fibonacci theo đúng công thức như sau:

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

Nếu tính toán như trê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).

Và quy hoạch động chính là một trong số những phương pháp có thể giúp chúng ta tối ưu hóa quá trình tính toán này. Mỗi bài toán con (số fib) 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.

Một ví dụ quy hoạch động với bài toán này như sau:

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]

Qua ví dụ trên, bạn đã thấy được sức mạnh vượt trội của quy hoạch động chưa? Đó cũng chính là lý do mà nó rất được ưa chuộng trong các cuộc thi lập trình, khi mà thời gian và bộ nhớ đều là hữu hạn (và thường khá nhỏ).

TÌM VIỆC LÀM NGÀNH LẬP TRÌNH

Cấu trúc con tối ưu

Cấu trúc con tối ưu là một tính chất là lời giải của bài toán lớn sẽ là tập hợp lời giải từ các bài toán nhỏ hơn.

Mình lấy một ví dụ cho dễ hiểu:

Trong bài toán tìm đường đi ngắn nhất trong đồ thị, nếu một node x nằm trên đường đi ngắn nhất giữa hai node u, v thì đường đi ngắn nhất từ u đến v sẽ là tổng hợp của đường đi ngắn nhất từ u đến x và đường đi ngắn nhất từ x đến v. Môt số thuật toán tìm đường trên đồ thị (nổi tiếng nhất có lẽ là Dijkstra) đều dựa trên tính chất này, và nó cũng áp dụng quy hoạch động.

Tính chất cấu trúc con tối ưu rất quan trọng. Nó cho phép chúng ta giải bài toán lớn dựa vào các bài toán con đã giải được. Nếu không có tính chất này, chúng ta không thể áp dụng quy hoạch động được.

Không phải bài toán nào cũng có tính chất cấu trúc con tối ưu này. Ví dụ với đồ thị sau:

Đường đi dài nhất từ q -> t sẽ là q -> r -> t hoặc q -> s -> t. Nhưng không giống như bài toán tìm đường đi ngắn nhất, đường đi dài nhất không phải là tổ hợp của những đường đi thành phần, do đó, bài toán này không có cấu trúc con tối ưu.

Ví dụ, đường q -> r -> t không phải là tổ hợp của đường đi dài nhất từ q -> r và đường đi dài nhất từ r -> t. Bởi vì, đường đi dài nhất q -> rphải là q -> s -> t -> r và đường đi dài nhất từ r -> t phải là r -> q -> s -> t.

Ưu và nhược điểm của Quy hoạch động

Ưu điểm của Dynamic Programming (DP)

Dynamic Programming có nhiều ưu điểm, bao gồm:

• Giảm thời gian tính toán: Quy hoạch động lưu trữ kết quả của các bài toán con đã được tính toán trước đó, giúp giảm thiểu đáng kể số lượng phép tính cần thực hiện. Điều này đặc biệt hiệu quả trong các bài toán có tính chất lặp lại, như dãy Fibonacci hoặc bài toán tối ưu hóa.
• Giải quyết được các bài toán phức tạp: DP cho phép giải quyết nhiều bài toán tối ưu hóa và lập lịch phức tạp mà các phương pháp khác không thể làm được hiệu quả, chẳng hạn như bài toán balo, chuỗi con chung dài nhất (LCS), và nhiều bài toán đồ thị.
• Tránh được các tính toán lặp lại không cần thiết: Bằng cách lưu trữ kết quả của các bài toán con, DP tránh được việc tính toán lặp lại những phần đã giải quyết, giúp tiết kiệm tài nguyên và tăng hiệu suất.
• Độ chính xác cao: Kỹ thuật DP đảm bảo tìm ra giải pháp tối ưu cho bài toán bằng cách xây dựng các giải pháp từ các bài toán con tối ưu.

Nhược điểm của Quy hoạch động

• Tốn bộ nhớ: DP yêu cầu lưu trữ kết quả của tất cả các bài toán con, điều này có thể tốn rất nhiều bộ nhớ, đặc biệt đối với các bài toán có không gian trạng thái lớn. Điều này có thể gây ra vấn đề khi áp dụng DP cho các bài toán có quy mô lớn.
• Phức tạp trong việc triển khai: Hiểu và triển khai một giải pháp DP đòi hỏi người lập trình phải hiểu rõ cấu trúc của bài toán và cách chia nhỏ nó thành các bài toán con. Điều này có thể phức tạp và tốn nhiều thời gian để thiết kế và debug.
• Không phải lúc nào cũng khả thi: Không phải bài toán nào cũng có thể áp dụng được DP. Các bài toán cần có tính chất con tối ưu (optimal substructure) và tính chất lặp lại của bài toán con (overlapping subproblems). Nếu bài toán không có các tính chất này, DP sẽ không hiệu quả.
• Tiêu tốn thời gian cho việc lưu trữ và truy xuất: Mặc dù giảm thời gian tính toán, việc lưu trữ và truy xuất kết quả từ bộ nhớ cũng tiêu tốn thời gian, đặc biệt khi kích thước của bảng lưu trữ lớn.

Một số bài toán quy hoạch động

Trong phần này, chúng ta sẽ làm quen với quy hoạch động thông qua một số ví dụ cụ thể. Chúng ta sẽ xem xét cách quy hoạch động được áp dụng vào các bài toán cụ thể như thế nào, đồng thời qua đó, chúng ta sẽ hiểu hơn về các tính chất ở phần trước.

Ví dụ 1: Bài toán kinh điển với đồng xu

Đây là một ví dụ rất kinh điển khi học về quy hoạch động. Có thể có nhiều cách phát biểu khác nhau nhưng về cơ bản, nội dung của nó sẽ tương tự như sau.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là không giới hạn.

Giả sử chúng ta có n đồng xu nặng lần lượt là W1, W2, ..., Wn, và bài toán đặt ra là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng là một giá trị S. Tất nhiên, số lượng đồng xu là 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 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à PToà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

Ví dụ 2: Xâu con chung dài nhất (LCS)

Thêm một ví dụ nữa cho dễ, cũng là một bài toán rất nổi tiếng.

Cho hai xâu ký tự. Tìm độ dài xâu con chung nhỏ nhất giữa chúng. Ví dụ với 2 xâu “quetzalcoatl” và “tezcatlipoca” thì xâu con chung dài nhất sẽ là “ezaloa” với độ dài 6.

Với bài toán này, chúng ta sẽ lần lượt giải các bài toán con như sau:

Lấy i ký tự đầu tiên từ xâu thứ nhất và j ký tự đầu tiên từ xâu thứ hai và tìm độ dài xâu chung dài nhất giữa 2 xâu con được lấy ra đó. Dễ dàng thấy được rằng, lời giải của mỗi bài toán con sẽ phụ thuộc vào i và j, dp(i, j). Và bài toán lớn sẽ được giải bằng cách lần lượt giải các bài toán con lần lượt từ dp(0, 0) và tăng dần độ dài xâu được lấy ra cho đến khi chúng ta lấy ra toàn bộ xâu của đề bài.

Chúng ta hãy bắt đầu lần lượt các bài toán con. Đương nhiên, nếu một trong hai xâu là rỗng thì xâu con chung của chúng cũng rỗng. Vậy dp(0, j) = dp(i, 0) = 0. Nếu cả i và j đều dương, chúng ta cần suy xét một vài trường hợp.

1. Nếu ký tự cuối cùng của xâu thứ nhất không có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không ảnh hưởng gì đến kết quả. Công thức ở đây sẽ là dp(i, j) = dp(i - 1, j).
2. Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai không ảnh hưởng đến kết quả thì dp(i, j) = dp(i, j - 1).
3. Trường hợp cuối cùng, nếu hai ký tự cuối cùng của hai xâu x1, x2 đều có mặt trong xâu con chung dài nhất. Dĩ nhiên là hai ký tự này phải là một thì điều này mới xảy ra, tức là x1 == x2. Trong trường hợp này, khi xoá đi bất cứ một ký tự nào trong hai ký tự đó đều khiến xâu con chung dài nhất ngắn đi 1 ký tự. Vậy rõ ràng là dp(i, j) = dp(i - 1, j - 1) + 1.

Trong cả ba trường hợp trên, chúng ta phải chọn ra trường hợp nào cho kết quả là xâu con chung dài nhất (với bài toán này thì chỉ cần đưa ra độ dài đó là đủ).

Về mặt cài đặt, dp sẽ được lưu trong mảng hai chiều. Kết quả của mảng này sẽ được tính toán thông qua vòng lặp hai lớp. Lưu ý rằng, chúng ta cần thực hiện vòng lặp sao cho chúng ta sẽ giải lần lượt từng bài toán con một, theo thứ tự từ nhỏ đến lớn. Bởi vì mỗi bài toán con dp(i, j) đều phụ thuộc vào các bài toán con trước đó dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1).

n1, n2 = map(int, input().split()) s1, s2 = input().split() t = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)] for i, x1 in enumerate(s1, 1): for j, x2 in enumerate(s2, 1): if x1 == x2: t[i][j] = t[i - 1][j - 1] + 1 else: t[i][j] = max(t[i][j - 1], t[i - 1][j]) print(t[-1][-1]) # Kết quả khi giải các bài toán con như bảng sau: # # S| t e z c a t l i p o c a # T ji| 0 1 2 3 4 5 6 7 8 9 10 11 12 # ----+-------------------------------------- # 0 | 0 0 0 0 0 0 0 0 0 0 0 0 0 # q 1 | 0 0 0 0 0 0 0 0 0 0 0 0 0 # u 2 | 0 0 0 0 0 0 0 0 0 0 0 0 0 # e 3 | 0 0 1 1 1 1 1 1 1 1 1 1 1 # t 4 | 0 1 1 1 1 1 2 2 2 2 2 2 2 # z 5 | 0 1 1 2 2 2 2 2 2 2 2 2 2 # a 6 | 0 1 1 2 2 3 3 3 3 3 3 3 3 # l 7 | 0 1 1 2 2 3 3 4 4 4 4 4 4 # c 8 | 0 1 1 2 3 3 3 4 4 4 4 5 5 # o 9 | 0 1 1 2 3 3 3 4 4 4 5 5 5 # a 10| 0 1 1 2 3 4 4 4 4 4 5 5 6 # t 11| 0 1 1 2 3 4 5 5 5 5 5 5 6 # l 12| 0 1 1 2 3 4 5 6 6 6 6 6 6

Quy hoạch động vs Memoization

Có một kỹ thuật khác gọi là “memoization” cũng có cách tiếp cận tương tự với quy hoạch động. Cả quy hoạch động và memoization đều dùng để tối ưu các vòng lặp mà có tính toán tượng tự nhau, trong đó kết quả của phép tính lớn hơn sẽ cần được tính toán dựa vào kết quả của phép tính nhỏ hơn. Memoization thường được sử dụng trong các phép tính đệ quy khi mà một tính toán bị lặp đi lặp lại nhiều lần. Nó sẽ lưu một bảng các giá trị tính được, mỗi khi có tính toán cần thực hiện, chúng ta sẽ tra bảng đó trước. Nếu bảng đã có kết quả rồi, chúng ta chỉ cần lấy ra là xong, nếu chưa, chúng ta sẽ tính toán như thường và tiếp tục lưu vào bảng.

Memoization không phải là một thuật toán theo đúng nghĩa, nó là một kỹ thuật được sử dụng trong lập trình thì đúng hơn. Để hiểu rõ hơn về kỹ thuật này, mình xin lấy ví dụ ngay với bài toán Fibonacci. Chúng ta sẽ sử dụng memoization như sau:

look_up = {0: 1, 1: 1} def fib(n): if look_up.get(n) is None: look_up[n] = fib(n - 1) + fib(n - 2) return look_up[n]

Sự khác biệt chủ yếu là quy hoạch động sẽ thực hiện việc tính toán theo một thứ tự định trước, trong khi memoization duyệt theo chiều sâu. Quy hoạch động không bao giờ tính toán một bài toán con hai lần, tương đối giống với các phép tính đệ quy với memoization. Tuy nhiên memoization thì không bao giờ tính toán những phép tính thừa trong khi quy hoạch động sẽ cần tất cả mọi bài toán con. Đây là một phương pháp khá hay, nó chỉ tính toán những gì cần thiết và lưu kết quả này lại để sau này dùng lại khi nào được gọi mà không cần tính toán nữa.

Dưới đây là một số ưu, nhược điểm của memoization khi so sánh với quy hoạch động:

Ưu điểm

• Dễ code hơn
• Không yêu cầu thứ tự thực hiện tính toán
• Chỉ tính toán những gì cần thiết

Nhược điểm

• Chỉ có một kiểu duyệt duy nhất
• Thường chậm hơn quy hoạch động.

Các dạng toán quy hoạch động

Phần lớn các bài toán quy hoạch động có thể chia làm hai loại: bài toán cần quy hoạch động để tối ưu và bài toán quy tổ hợp. Trong những phần dưới đây, chúng ta sẽ xem xét từng loại bài toán này.

Bài toán tối ưu

Bài toán tối ưu yêu cầu chúng ta phải tìm đáp án tốt nhất từ mục tiêu của bài toán. Cả hai ví dụ mình đưa ra ở trên đều thuộc loại bài toán này (một bài tìm số đồng xu ít nhất, một bài tìm xâu con dài nhất). Mối liên hệ của các bài toán con thuộc dạng này có công thức chúng là dp[s] = min(F1(dp[i], dp[j], ..., dp[k]), F2(dp[u], dp[v], ..., dp[w]), ..., Fl(dp[q], dp[p], ..., dp[z])), trong đó dp mảng lưu kết quả của các bài toán con đó.

Mỗi bài toán được giải dựa trên bài toán đã được giải trước đó. Đây chính là tính chất cấu trúc con tối ưu của mỗi bài toán. Với bài toán đồng xu, mỗi bài toán mới đều được giải bằng cách thêm đúng 1 đồng xu vào kết quả từ trước đó. Kết quả cuối cùng là kết quả tốt nhất thu được từ nhiều cách thêm đồng xu với khối lượng khác nhau.

Trước khi tính toán, mảng chứa kết quả có thể được điền đầy một giá trị trung tính nào đó. Giá trị trung tính có nghĩa là giá trị đó sẽ không bao giờ là đáp án cho bất kỳ bài toán con nào. Ví dụ khi cần tìm ra số đồng xu nhỏ nhất, chúng ta có thể điền mảng này bằng số dương lớn nhất, mọi tính toán tiếp theo sẽ cho ra một kết quả nhỏ hơn nhiều. Nếu không ra kết quả nào khác, chúng ta có thể coi như là không có một đáp án nào cho bài toán con đó.

Bài toán tổ hợp

Bài toán tổ hợp thường yêu cầu chúng ta tìm ra số cách khác nhau để thực hiện một việc gì đó. Nhiều bài thi code thường có kết quả rất lớn và họ yêu cầu chúng ta đưa đáp án dạng modulo của 10000007. Trong dạng bài toán này, công thức khi xây dựng các bài toán con sẽ là R[s] = F1(R[i], R[j], ..., R[k]) + F2(R[u], R[v], ..., R[w]) + ... + Fl(R[q], R[p], ..., R[z]). Sự khác biệt cơ bản của dạng bài toán này với dạng bài toán tối ưu là ở chỗ chúng ta cần tính tổng thay vì tìm số lớn nhất hoặc nhỏ nhất.

Trong mọi bài toán quy hoạch động, tính chất cấu trúc con tối ưu luôn là quan trọng nhất và cũng là tính chất khó đảm bảo nhất. Nếu cấu trúc con không được tối ưu, chúng ta sẽ tính toán theo một phương thức sai lầm và đương nhiên, kết quả thu được cũng không chính xác.

Với phần lớn các bài toán quy hoạch động, việc chia các bài toán con gối nhau khá dễ dàng trong khi đảm bảo cấu trúc con tối ưu thì khó hơn nhiều.

Mình sẽ đưa ra hai ví dụ tương tự nhau cho các bạn hiểu rõ hơn về những khó khăn để đảm bảo tính chất này.

Vẫn với bài toán đồng xu, chúng ta sẽ thay đổi một chút để có bài toán tổ hợp như sau:

Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S.

Các bài toán con sẽ tương tự như trước: dp(P) = k là số cách khác nhau để chọn ra các đồng xu có tổng khối lượng là P. Công thức đệ quy trong trường hợp này sẽ biến đổi theo bài toán như sau:

# Công thức đệ quy cho bài toán quy hoạch động # {dp[0] = 1; # {dp[P] = sum(dp[P-Wi]); (for Wi <= P) # # Với đầu vào như sau: n = 3, S = 11, W = [1, 3, 5] # Mảng kết quả quy hoạch động sẽ là # P = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11 # ------+--+--+--+--+--+--+--+--+--+--+-- # k = 1 |1 |1 |2 |3 |5 |8 |12|19|30|47|74

Bài toán tổ hợp cũng có thể có một giá trị trung tính. Bởi vì bài toán tổ hợp thường tính tổng, giá trị trung tính sẽ là 0. Bài toán tổ hợp yêu cầu tìm số cách khác nhau để làm gì đó, do đó giá trị 0 sẽ không ảnh hưởng gì đến đáp án. Một điểm đặc biệt quan trọng trong bài toán tổ hợp này là mỗi cách chúng ta chỉ tính đúng một lần. Nói thì dễ nhưng nhiều khi trong thực hành chúng ta hay gặp sai sót ở chỗ cực kỳ quan trọng này.

Tiếp tục thay đổi thêm một chút, chúng ta sẽ có bài toán tổ hợp như sau:

Tìm số cách khác nhau để chọn ra các đồng xu sao cho tổng khối lượng của chúng là S. Với điều kiện, các cách lấy đồng xu là hoán vị của nhau không được coi là khác nhau.

Bài toán này khó hơn bài toán trước một chút. Nếu chúng vẫn chia các bài toán con như cũ thì không thể có được cấu trúc con tối ưu. Ví dụ, với các đồng xu 1, 3, 5 thì (1, 3) và (3, 1) đều cho kết quả là 4 nhưng chỉ được coi là 1 cách.

Với bài toán này, chúng ta sẽ chia bài toán lớn thành các bài toán con theo một cách tương đối khác. Chúng ta thấy rằng, kết quả (số cách chọn đồng xu) sẽ là tổng hợp của hai kết quả:

• Số cách lấy đồng xu từ n - 1 đồng xu đầu tiên, tức là chúng ta coi như không có đồng xu nặng nhất
• Số cách lấy đồng xu có chứa đồng xu nặng nhất.

Kết quả sẽ là tổng của hai kết quả trên. Các bạn thấy đó, với cách xây dựng bài toán con như thế này, chúng ta đã xây dựng các bài toán con gối nhau mà vẫn đảm bảo cấu trúc con tối ưu (kết quả bằng tổng của các bài toán con).

Nhân tiện, với cách chia bài toán như vậy, chúng ta có thể thu được lời giải bằng cách đệ quy đơn giản như sau:

n, S = map(int, input().split()) w = list(map(int, input().split())) def count(arr, x): # Có 1 cách (lấy ra 0 đồng xu) cho tổng khối lượng bằng 0 if x == 0: return 1 # Không thể lấy được các đồng xu cho khối lượng âm if x < 0: return 0 # Không thể lấy nếu không có đồng xu nào if not arr and x >= 1: return 0 # Kết quả là tổ hợp các bài toán con return count(arr[:-1], x) + count(arr, x - arr[-1]) print(count(w, S))

Tuy nhiên, như mình đã nói ở phần trước, nếu bạn đang thi code, cách làm này sẽ không mang lại bất cứ hy vọng đạt giải nào, do nó cực kỳ mất thời gian và bộ nhớ. Tuy nhiên, chúng ta có thể áp dụng quy hoạch động cho bài toán này rất dễ dàng sau khi có được cấu trúc con tối ưu với các bài toán con gối nhau:

n, S = map(int, input().split()) w = list(map(int, input().split())) dp = [[0 for _ in range(n)] for _ in range(S + 1)] for i in range(n): dp[0][i] = 1 for i in range(1, S + 1): for j in range(n): x = dp[i - w[j]][j] if i - w[j] >= 0 else 0 y = dp[i][j - 1] if j >= 1 else 0 dp[i][j] = x + y print(dp[-][n - 1]) # Kết quả tính toán với n = 3, w = [1, 3, 5] như sau: # S = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11 # ------+--+--+--+--+--+--+--+--+--+--+-- # k = 1 |1 |1 |2 |2 |3 |4 |4 |5 |6 |7 |8

Các bạn thấy đó, xây dựng các bài toán con gối nhau sao cho cấu trúc con vẫn tối ưu nhiều khi không đơn giản chút nào. Và mỗi bài toán quy hoạch động lại có những biến hóa khác nhau mà không theo một khuôn mẫu khô cứng nào. Ngay cả khi bạn có thể giải được rất nhiều bài toán quy hoạch động rồi, không gì có thể đảm bảo bạn có thể giải được các bài khác nữa. Đó cũng là một lý do khiến cho dạng bài này luôn “hot” trong các cuộc thi.

Tuyển dụng IT tại HCM, Hà Nội, Đà Nẵng

Quy hoạch động xuôi và ngược

Tất cả những ví dụ mình đã trình bày ở trên đều sử dụng quy hoạch động kiểu “ngược”. Ngược ở đây không phải là chúng ta duyệt các bài toán con từ lớn ngược về nhỏ. Mà quy trình sẽ như thế này: Duyệt qua tất cả các bài toán con (từ nhỏ đến lớn), với mỗi bài toán đó, chúng ta tính toán kết quả dựa vào bài toán con trước đó. Tất nhiên, bài toán con phía trước đã được giải theo quy trình duyệt, và với mỗi bài toán, chúng ta phải “nhìn ngược lại” bài toán trước đó, nên cách làm này gọi là quy hoạch động kiểu “ngược”.

Phương pháp quy hoạch động ngược này được sử dụng rộng rãi, vì nó khá tương ứng với suy nghĩ tự nhiên của chúng ta. Chúng ta đọc đề bài, suy nghĩ cách giải cho nó. Cách giải đó yêu cầu phải giải những bài toán nhỏ hơn, như kiểu làm toán ngày phải chứng minh các bổ đề vậy. Chúng ta tiếp tục suy nghĩ cho những bài toán con này, rồi tổng hợp để tìm ra lời giải cho bài toán lớn. Quá trình cứ tiếp tục như vậy, và quy hoạch động kiểu “ngược” này đang được xây dựng đúng như vậy.

Ngoài ra, về mặt lập trình, kiểu quy hoạch động này có mối quan hệ tương đối gần gũi với đệ quy. Một bài toán lớn được giải dựa vào các bài toán con tương tự nhau (và tương tự bài toán lớn) thì việc áp dụng đệ quy có thể là một phương pháp dễ dàng để code. Vì vậy, nhiều trường hợp, có thể coi quy hoạch động là một cách để tối ưu phương pháp đệ quy để giải một bài toán.

Ngoài kiểu quy hoạch động ngược này, có một kiểu quy hoạch động “xuôi”. Tuy không phổ biến, kiểu quy hoạch động xuôi cũng khá khó áp dụng, nhưng quy hoạch động “xuôi” mang đến cho chúng ta nhiều tiện lợi. Kiểu xuôi này cũng cần duyệt qua các bài toán con từ nhỏ đến lớn, nhưng với mỗi bài toán con, chúng ta tính toán kết quả và từ đó tìm cách thực hiện một số phép tính để giải bài toán lớn hơn. Nghĩa là, với mỗi bài toán con, chúng ta sẽ nhìn về phía trước để xem phải giải bài toán tiếp theo như thế này từ bài toán hiện tại.

Phương pháp này khó áp dụng hơn phương pháp ngược kia, và cũng không phải bài toán nào cũng áp dụng được. Với mỗi bài toán, việc xác định bước tiếp theo tương đối khó khăn, thậm chí việc kiểm tra tính đúng sai của phương pháp cũng không hề dễ dàng.

Như chúng ta đã thấy ở những phần trước, thông thường, mỗi bài toán cần phải giải bằng cách tổng hợp kết quả từ một vài bài toán con trước đó. Vì vậy, cách quy hoạch động xuôi này chỉ sử dụng một bài toán con để tính toán trước bài toán tiếp theo sẽ chỉ cho ra một phần của kết quả chứ không phải kết quả cuối cùng. Vì vậy, để thực hiện quy hoạch động xuôi, việc điền sẵn một mảng các giá trị trung tính là điều bắt buộc (sau đó chúng ta sẽ cộng dồn kết quả vào mỗi khi giải được một bài toán con mới).

Mình lấy vị với bài toán xâu con chung dài nhất. Với bài toán này, chúng ta có thể chọn giá trị trung tính là một số âm. Chúng ta sẽ tìm cách quy hoạch động xuôi như sau:

• dp(0,0) = 0 là bài toán với hai xâu rỗng
• Với mỗi bài toán dp(i, j) chúng ta sẽ tìm cách tính toán kết quả cho các bài toán lớn hơn. Lúc này, có 3 hướng phát triển tiếp:
  1. Lấy thêm một ký tự từ xâu thứ nhất => Kết quả không thay đổi.
  2. Lấy thêm một ký tự từ xâu thứ hai => Kết quả cũng không thay đổi.
  3. Nếu ký tự tiếp theo của cả hai xâu giống nhau => Lấy tự từ này và độ dài xâu con chung tăng lên 1.

Dưới đây là code cho bài toán này:

n1, n2 = map(int, input().split()) s1, s2 = input().split() s1 += 'x00' s2 += 'x00' # Điền sẵn giá trị trung tính dp = [[-1] * (n1 + 2) for _ in range(n2 + 2)] dp[0][0] = 0 for i in range(n1 + 1): for j in range(n2 + 1): tres = dp[i][j] # Phát triển theo hướng thứ nhất if dp[i + 1][j] < tres: dp[i + 1][j] = tres # Phát triển theo hướng thứ hai if dp[i][j + 1] < tres: dp[i][j + 1] = tres # Phát triển theo hướng thứ ba if s1[i] == s2[j] and dp[i + 1][j + 1] < tres + 1: dp[i + 1][j + 1] = tres + 1 print(dp[n1][n2])

Kết luận

Hy vọng qua bài viết này, mình đã trình bày được phần nào về thuật toán quy hoạch động. Về cơ bản, với mọi bài toán quy hoạch động, chúng ta có thể xây dựng các bài toán con gối nhau với cấu trúc con tối ưu là 90% công việc đã hoàn thành.

Tuy nhiên, cũng cần hiểu rằng, mặc dù thuật toán quy hoạch động là một thuật toán thần thánh, nó có thể giải được rất nhiều bài toán, nhưng nó không phải là chìa khóa vạn năng. Có một điều rất hiển nhiên: phương pháp tốt nhất để giải quyết mọi bài toán trong tin học là biết sử dụng và phối hợp uyển chuyển nhiều thuật toán, chúng ta không nên phát cuồng một thuật toán và cũng không nên coi thường bất cứ một thuật toán nào.

Tác giả: Trần Ngọc Anh – manhhomienbienthuy.bitbucket.io

Có thể bạn quan tâm:

• Các thuật toán sắp xếp lập trình viên phải biết
• Thuật toán chuỗi Fibonacci △
• Thuật toán sắp xếp nào là nhanh nhất?

Xem thêm IT Jobs for Developer tại TopDev