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.
Nguyên lý hoạt động của Dynamic Programming
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.
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).
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
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.
Đị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.
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 đó.
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.
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.
