Quy hoạch động và phương trình Bellman

Quy hoạch động tách quyết định hiện tại khỏi phần bài toán còn lại. Hàm giá trị V(s) lưu kết quả tốt nhất từ s, còn phương trình Bellman so sánh chi phí hiện tại cộng với giá trị của trạng thái kế tiếp.

Lĩnh vực: Quy hoạch

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Quy hoạch tuyến tính và quy hoạch độngToán cho AI

Giải thích kỹ thuật

Nguyên lý tối ưu và đủ. Với thời hạn hữu hạn tất định, $V_t(s)=\underset{a}{min}\{c_t(s,a)+V_{t+1}(T_t(s,a))\}$. Nếu phần còn lại của một phương án tối ưu không tối ưu từ trạng thái kế tiếp, thay nó bằng phần tốt hơn sẽ giảm tổng chi phí, tạo mâu thuẫn.

Lập luận phụ thuộc chứa đủ thông tin quyết định các lựa chọn và chi phí tương lai. Với bài ngẫu nhiên, số hạng tương lai thường trở thành có điều kiện. Với có chu trình, không thể tự dùng một lượt tính ngược theo thứ tự DAG. Nguồn: Convex Optimization, §8.7 cho một đường dài nhất và biến thể đường ngắn nhất trong Notes được tự biên soạn.

Ví dụ

Nếu từ A đi thẳng tới đích tốn 5, còn đi $A\to B$ tốn 2 và từ B tới đích tốn 1, thì $V(A)=min(5,2+1)=3$.

Khi nào cần dùng?

Giải chuỗi quyết định, đường đi trên DAG và bài toán điều khiển hữu hạn.

Câu hỏi ôn lại

Vì sao phải chứa đủ thông tin cho tương lai?

Xem đáp án

Vì nếu hai lịch sử có cùng nhãn nhưng cho lựa chọn tương lai khác nhau, một giá trị V chung không còn đúng.

Thuật ngữ liên quan

• Đồ thị
• Trạng thái
• Nghiệm cơ sở của quy hoạch tuyến tính