Giải thuật qui hoạch động (Dynamic Programming)

Giải thuật Qui hoạch động (Dynamic Programming) là gì ?

Giải thuật Qui 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 Qui hoạch động (Dynamic Programming) 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 Qui 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.

Do đó, chúng ta có thể nói rằng:

So sánh

Giải thuật tham lam và giải thuật qui hoạch động

Giải thuật chia để trị và giải thuật Qui hoạch động:

Ví dụ giải thuật Qui hoạch động

Dưới đây là một số bài toán có thể được giải bởi sử dụng giải thuật Qui hoạch động:

Giải thuật Qui hoạch động có thể được sử dụng trong cả hai phương pháp Phân tích (Top-down) và Qui nạp (Bottom-up). Và tất nhiên là nếu dựa vào vòng đời làm việc của CPU thì việc tham chiếu tới kết quả của lời giải trước đó là ít tốn kém hơn việc giải lại bài toán.