Tài liệu : Một số bài toán qui hoạch động

MỘT SỐ BÀI TOÁN QUY HOẠCH ĐỘNG ĐIỂN HÌNH.
Chúng ta đều biết rằng điều khó nhất để giải một bài toán quy hoạch động (QHĐ) là biết rằngnó là một bài toán QHĐ và tìm được công thức QHĐ của nó. Rất khó nếu ta mò mẫm từ đầu,nhưng nếu chúng ta đưa được bài toán cần giải về một bài toán QHĐ kinh điển thì sẽ dễ dànghơn nhiều. Do đó, tìm hiểu mô hình, công thức và cách cài đặt những bài toán QHĐ kinhđiển là một việc rất cần thiết.
Trong chuyên đề này, tôi xin giới thiệu một số bài toán QHĐ kinh điển và những biến thể củachúng.Chủ yếu tập trung vào giới thiệu mô hình, công thức và một số gợi ý trong cài đặt chứkhông đi chi tiết vào việc phát biểu bài toán, mô tả input/output, chứng minh công thức hayviết chương trình cụ thể. Mặc dù rất muốn minh hoạ cho các bài toán bằng các hình vẽ trựcquan nhưng khuôn khổ có hạn nên tôi không thể đưa vào. Hơn nữa phần gợi ý cài đặt chỉ cógợi ý cho phần tính bảng phương án, phần lần vết cần có các cấu trúc dữ liệu và những kĩthuật xử lí phức tạp xin dành lại cho các bạn.

Click để xem tiếp...