Hỏi đáp

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ẽ Chia sẻ với chúng ta 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 số 1 đị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ó các 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ả nhất là cực kỳ cần thiết. Và trong các trường hợp như vậy, quy hoạch động chính là một trong các thuật toán xuất hiện nhiều nhất.

Bạn đang xem: Dynamic programming chính là gì

Thuật toán quy hoạch động được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng , và bạn phải suy nghĩ rất nhiều nhiều mới tìm ra đã được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, bạn bắt buộc phải cực kỳ thuần thục thuật toán này nếu muốn có kết quả tốt trong các cuộc thi.

Bạn đang đọc: Thuật toán Quy hoạch động – Một thuật toán thần thánh

Cách tốt nhất số 1 để tìm hiểu một thuật toán chính là xem xét các thí dụ cụ thể. Trong bài viết này, tôi cũng sẽ giới thiệu vài thí dụ trong phần sau. Có thể nó không đầy đủ, bạn có thể đọc thêm ở các bài viết khác. Giới thiệu với Bạn một tài liệu rất hay: Dynamic Programming: From novice to advanced

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 nhiều 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 vài 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 số 1 trong số chúng:

Tìm hiểu thêm: Chi tiết bài viết

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, mọi người 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 chính là có, nhưng nếu bạn đi thi code, bạn trượt chính là cái chắc. Để hiểu rõ hơn, chúng ta cũng sẽ tìm hiểu từng tính chất một trong các 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 cũng sẽ lưu kết quả của bài toán con này, , khi đã được gọi, nó sẽ chưa cần phải tính lại, do đó làm giảm thời gian tính toán.

Quy hoạch động cũng sẽ không thể áp dụng được (hoặc nói đúng hơn chính là áp dụng cũng không có tác dụng gì) khi các bài toán con chưa gối nhau. thí 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à chưa bao giờ đã được gọi lại.

Một thí dụ rất nhiều đ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, mọi người 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, mọi người rất nhiều nhiều bài toán con cũng sẽ đã được tính đi tính lại, điển hình là các số fib(0) , fib(1).

Và quy hoạch động là một trong số các 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 các 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 thí 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]

Tham khảo thêm: Hipster là gì – Đâu là phong cách của một Hipster thực thụ?

Qua thí 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 là nguyên do mà nó rất đã được ưa chuộng trong các cuộc thi lập trình, khi mà thời gian , bộ nhớ đều là hữu hạn (và thường khá nhỏ).

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

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

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

Trong bài toán tìm đường đi ngắn số 1 trong đồ thị, nếu một node x nằm ở trên đường đi ngắn số 1 giữa hai node u, v thì đường đi ngắn số 1 đến từ u đến v cũng sẽ chính là tổng hợp của đường đi ngắn số 1 từ u đến x , và đường đi ngắn số 1 đến từ x đến v. Môt số thuật toán tìm đường trên đồ thị (nổi tiếng số 1 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 chưa có tính chất này, mọi người 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. thí dụ với đồ thị sau:

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

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

thí dụ, đường q -> r -> t chưa phải là tổ hợp của đường đi dài số 1 đến từ q -> r , đường đi dài số 1 đến từ r -> t. Bởi vì, đường đi dài nhất q -> rphải chính là q -> s -> t -> r và đường đi dài nhất đến từ r -> t phải chính là r -> q -> s -> t.

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

Trong phần này, mọi người sẽ làm quen với quy hoạch động thông qua một vài thí 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 cũng sẽ hiểu hơn về các tính chất ở phần trước.

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

Đây là một thí dụ rất nhiều 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ử mọi người có n đồng xu nặng lần lượt chính 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 chính 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 chính là W1, W2, …, Wn, , bài toán đặt ra chính là tìm số lượng đồng xu nhỏ nhất để tổng khối lượng của chúng chính là một giá trị S. Tất nhiên, số lượng đồng xu chính là chưa giới hạn.

Tham khảo thêm: Nên mua Smart Tivi hay là Internet Tivi

Với bài toán này, mọi người cần xây dựng , giải các bài toán con gối nhau. Với thí 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 chính là P. và dp(P) = k là số lượng đồng xu nhỏ nhất đó.

Chúng ta cũng sẽ áp dụng phương pháp quy hoạch động chỉ bằng cách bắt đầu đến 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 cũng sẽ được xây dựng lần lượt cho đến mọi người 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 chú ý với kỹ thuật này là bài toán con tiếp theo sẽ chưa thể giải được nếu chúng ta không giải bài toán con trước đó.

Cuối cùng chính 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, thực hiện thế nào để từ các 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 các bài toán phức tạp hơn, mọi người cần suy nghĩ , 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, mọi người 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 mọi người cũng 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 mọi người có thể cần đến nhiều bài toán con trước đó, , và dp(p) chính là giá trị nhỏ nhất sau khi tổng hợp các bài toán con đó.

thí 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) = 0Với bài toán con 1, có 1 đồng xu (nặng 1) có thể thêm vào đến 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 đến từ 1 đồng xu. Vậy dp(2) = dp(1) + 1 = 2.Với bài toán con 3, mọi người 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 chính 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 thí dụ của chúng ta, mảng dp[0..S] cũng 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 chính là PToàn bộ mảng này sẽ đã được tính chỉ bằng vòng lặp. Đoạn code sau mô tả toàn bộ quy 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

thí dụ 2: Xâu con chung dài số 1 (LCS)

Thêm một thí 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ỏ số 1 giữa chúng. thí dụ với 2 xâu “quetzalcoatl” , “tezcatlipoca” thì xâu con chung dài số 1 sẽ chính 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 đế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 số 1 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 cũng sẽ phụ thuộc vào i , j, dp(i, j). Và bài toán lớn cũng 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 đến từ dp(0, 0) , tăng dần độ dài xâu đã được lấy ra cho đến khi mọi người 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 chính 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, mọi người cần suy xét một vài trường hợp.

Nếu ký tự cuối cùng của xâu thứ số 1 chưa có mặt trong xâu con chung dài nhất, nó có thể bị bỏ qua mà không tác động gì đến kết quả. Công thức ở đây sẽ chính là dp(i, j) = dp(i – 1, j).Tương tự như trường hợp trên, ký tự cuối cùng của xâu thứ hai chưa ảnh hưởng đến kết quả thì dp(i, j) = dp(i, j – 1).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 số 1 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, mọi người phải chọn ra trường hợp nào cho kết quả là xâu con chung dài số 1 (với bài toán này thì chỉ cần đưa ra độ dài đó chính 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 cũng sẽ được tính toán thông qua vòng lặp hai lớp. Chú ý rằng, chúng ta cần thực hiện vòng lặp sao cho chúng ta cũng 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).

Tham khảo thêm: Trợ cấp thôi việc: Điều kiện, mức hưởng và thủ tục nhận

Bạn thấy bài viết thế nào?

Tìm hiểu thêm: SALE là gì vậy? Ý nghĩa mở rộng của SALE