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.
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 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.
Cách hiệu quả nhất để tìm hiểu một thuật toán là xem xét những ví dụ cụ thể. Trong bài viết này, tôi sẽ giới thiệu vài ví dụ trong phần sau. Có thể nó chưa đầy đủ, bạn có thể đọc thêm ở các bài viết khác. Giới thiệu với các 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 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 tsẽ làq -> r -> thoặcq -> 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ụ, đườngq -> r -> tkhông phải là tổ hợp của đường đi dài nhất từq -> rvà đường đi dài nhất từr -> t. Bởi vì, đường đi dài nhấtq -> rphải làq -> s -> t -> rvà đường đi dài nhất từr -> tphải làr -> q -> s -> t.
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 condp[P]vớiP = 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.
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] = 0là bài toán với hai xâu rỗng
- Với mỗi bài toándp[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:
- Lấy thêm một ký tự từ xâu thứ nhất => Kết quả không thay đổi.
- Lấy thêm một ký tự từ xâu thứ hai => Kết quả cũng không thay đổi.
- 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 += '\0x00' s2 += '\0x00' # Đ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.
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 việc làm ngành ittại TopDev
Tác giả: Trần Ngọc Anh TopDev via manhhomienbienthuy.bitbucket.io