1
11thanhkhoeo
Chắc suất Đại học top - Giữ chỗ ngay!! ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Quy hoạch động là một phương pháp rất hiệu quả để giải các bài toán tối ưu tổ hợp. ý tưởng cơ bản của phương pháp này là: để có lời giải của bài toán tối ưu kích thước n, ta giải các bài toán tương tự có kích thước nhỏ hơn và phối hợp lời giải của chúng để được lời giải của bài toán ban đầu. Đó chính là tư tưởng chia để trị một cách rất nghiêm ngặt.
Không phải bài toán nào cũng có thể giải bằng quy hoạch động. Để giải được bằng quy hoạch động, bài toán thoả mãn nguyên lý tối ưu Bellman: mọi dãy con của một dãy tối ưu cũng phải là dãy tối ưu.
Thông thường hàm mục tiêu của bài toán được xây dựng từ một hàm có dạng: f(n) = max(f(k)+g(n)), trong đó k là một số giá trị phù hợp nhỏ hơn n.
Hàm f(n) được gọi là hàm quy hoạch động. Việc tính giá trị hàm f được hiện từ dưới lên, tức là các giá trị n nhỏ được tính trước. Tất cả các kết quả được lưu vào bảng để phục vụ cho việc tính hàm quy hoạch động với các giá trị n lớn hơn.
Chúng ta sẽ xem xét một số bài toán quy hoạch động tiêu biểu để minh hoạ cho các tư tưởng trên.
Không phải bài toán nào cũng có thể giải bằng quy hoạch động. Để giải được bằng quy hoạch động, bài toán thoả mãn nguyên lý tối ưu Bellman: mọi dãy con của một dãy tối ưu cũng phải là dãy tối ưu.
Thông thường hàm mục tiêu của bài toán được xây dựng từ một hàm có dạng: f(n) = max(f(k)+g(n)), trong đó k là một số giá trị phù hợp nhỏ hơn n.
Hàm f(n) được gọi là hàm quy hoạch động. Việc tính giá trị hàm f được hiện từ dưới lên, tức là các giá trị n nhỏ được tính trước. Tất cả các kết quả được lưu vào bảng để phục vụ cho việc tính hàm quy hoạch động với các giá trị n lớn hơn.
Chúng ta sẽ xem xét một số bài toán quy hoạch động tiêu biểu để minh hoạ cho các tư tưởng trên.