Tổng quan về Quy hoạch động

Phương pháp quy hoạch động dùng để giải bài toán tối ưu có tính chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy, nguyên lý chia để trị (devide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ: Khi không biết cần phải giải bài những toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn. Đó chính là điểm khác nhau giữa Quy hoạch động và phép đệ quy và cũng là nội dung Phương pháp quy hoạch động.

+Phép đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán con nhỏ hơn và lại đi giải quyết bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
+Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).

Khi sử dụng phương pháp quy hoạch động để giải quyết vấn đề, ta có thể gặp phải hai khó khăn sau:

– Một là, không phải lúc nào sự kết hợp lời giải của bài toán con cũng cho ra lời giải bài toán lớn hơn

– Hai là, số lượng các bài toán con cần giải quyết và lưu trữ đáp án có thể rất lớn, không thể chấp nhận được. Cho đến nay, chưa ai xác định được một cách chính xác những bài nào có thể được giải quyết hiệu quả bằng phương pháp quy hoạch động. Có những vấn đề quá phức tạp và khó khăn mà xem ra không thể ứng dụng quy hoạch động để giải quyết được, trong khi cũng có những bài toán quá đơn giản khiến cho việc sử dụng quy hoạch động để giải quyết lại kém hiệu quả hơn so với dùng các thuạt toán kinh điển.

Các nguyên tắc cơ bản của qui hoạch động
Qui hoạch động là việc qui hoạch từng giai đoạn của quá trình nhiều giai đoạn mà trong đó mỗi giai đoạn ta chỉ tối ưu hóa một bước. Tuy nhiên khi qui hoạch một quá trình nhiều giai đoạn, ở mỗi bước ta phải lựa chọn điều khiển trên cơ sở không phải xuất phát từ lợi ích nhỏ hẹp của chính bước đó mà từ lợi ích chung của toàn bộ quá trình.
1. Nguyên tắc đánh số các giai đoạn từ dưới lên.
Đối với giai đoạn cuối có thể làm cho nó tốt nhất và không lo hậu quả. Khi đó giai đoạn này trở nên ổn định và ta có thể xét giai đoạn ở trước đó và cứ tiếp tục cho tới lúc ta đi được tới giai đoạn đầu của quá trình.
2. Nguyên tắc thông số hóa bài toán
Ở giai đoạn sát giai đoạn cuối cùng, ta chưa biết kết quả nên ta phải đặt giả thiêt cho giai đoạn này rồi ứng với giả thiết đó ta tìm điều khiển tối ưu cho giai đoạn cuối cùng. Ở các bước khác tình hình cũng xảy ra như vậy. Do đó quá trình điều khiển tối ưu sẽ phụ thuộc vào các thông số đặc trưng cho kết quả ở bước trước.
3. Nguyên tắc lồng
Lồng bài toán ban đầu vào một bài toán rộng hơn hay một họ các bài toán và do đó bài toán ban đầu là một trường hợp riêng của họ bài toán này.
Họ bài toán này nhờ có các thông số nên ta giải được. Ta sẽ thử kết quả của bài toán với các thông số khác nhau cho tới một lúc được thông số của bài toán ban đầu thì dừng lại.
4. Nguyên tắc tối ưu (Bellman)
Dáng điệu tối ưu có tính chất là: dù trạng thái ban đầu và điều khiển ban đầu có dạng như thế nào thì điều khiển tiếp theo cũng là tối ưu đối với trạng thái thu được trong kết quả tác động những điều khiển ban đầu.