Bài 8 - Giải thuật quy hoạch động trong cấu trúc dữ liệu & giải thuật

Giải thuật quy hoạch động

Giải thuật Quy hoạch động (Dynamic Programming) giống như giải thuật chia để trị (Divide and Conquer) trong việc chia nhỏ bài toán thành các bài toán con nhỏ hơn và sau đó thành các bài toán con nhỏ hơn nữa có thể. Nhưng không giống chia để trị, các bài toán con này không được giải một cách độc lập. Thay vào đó, kết quả của các bài toán con này được lưu lại và được sử dụng cho các bài toán con tương tự hoặc các bài toán con gối nhau (Overlapping Sub-problems).

Chúng ta sử dụng Quy hoạch động khi chúng ta có các bài toán mà có thể được chia thành các bài toán con tương tự nhau, để mà các kết quả của chúng có thể được tái sử dụng. Thường thì các giải thuật này được sử dụng cho tối ưu hóa. Trước khi giải bài toán con, giải thuật Quy hoạch động sẽ cố gắng kiểm tra kết quả của các bài toán con đã được giải trước đó. Các lời giải của các bài toán con sẽ được kết hợp lại để thu được lời giải tối ưu.

• Bài toán ban đầu nên có thể được phân chia thành các bài toán con gối nhau nhỏ hơn.
• Lời giải tối ưu của bài toán có thể thu được bởi sử dụng lời giải tối ưu của các bài toán con.
• Giải thuật Quy hoạch động sử dụng phương pháp lưu trữ

So sánh

Trái ngược với các thuật toán tham lam, nơi giải quyết tối ưu hóa cục bộ, các thuật toán động được thúc đẩy để tối ưu hóa các bài toán con gối nhau.

Ngược lại với thuật toán chia để trị là kết hợp lời giải của các bài toán con để tìm ra lời giải của bài toán ban đầu. Giải thuật Quy hoạch động sử dụng kết quả của bài toán con và sau đó cố gắng tối ưu bài toán lớn hơn. Giải thuật Quy hoạch động sử dụng phương pháp lưu trữ để ghi nhớ kết quả của các bài toán con đã được giải.

Thí dụ

Các vấn đề máy tính sau đây có thể được giải quyết bằng phương pháp lập trình động

• Chuỗi số Fibonacci
• Vấn đề về chiếc ba lô
• Tháp Hà Nội
• Tất cả các cặp đường ngắn nhất của Floyd-Warshall
• Con đường ngắn nhất của Dijkstra
• Lập kế hoạch dự án

- Hiếu Kiều -