TAILIEUCHUNG - vận trù học 9

Tham khảo tài liệu 'vận trù học 9', tài chính - ngân hàng, kế toán - kiểm toán phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | ứng dụng trong các bài toán xác định chi phí tối thiểu nhiều dạng khác. Trong ví dụ trên tập No qua các bước lặp được phát triển như sau 1 1 3 1 3 4 7 1 3 4 7 5 1 4 3 7 5 1 4 3 7 5 6 1 4 3 7 5 6 2 . . Bài toán tìm đường đi ngắn nhất và quy hoạch động Bài toán tìm đường đi ngắn nhất Trong bài toán tìm đường đi ngắn nhất chúng ta muốn xác định hành trình ngắn nhất từ một địa điểm xuất phát điểm gốc để đi tới điểm cần đến điểm đích trên một mạng liên thông. Để cho dễ hiểu chúng ta xem xét ví dụ sau đây. Ví dụ 2 Bài toán người đi du lịch. Có một người đi du lịch xuất phát từ nút 1 và kết thúc hành trình ở nút 10 theo hành trình trên hình III. 13. Hình III. 12. Sơ đồ hành trình đường đi Người du lịch xuất phát từ nút 1. Trong giai đoạn đầu anh ta chỉ được quyền và bắt buộc chọn một trong ba nút thành phố 2 3 4 để vào thăm quan. Giai đoạn tiếp theo anh ta chỉ được chọn một trong ba nút 5 6 7 để du lịch. Trong giai đoạn tiếp nối anh ta có quyền vào một trong hai nút 8 hoặc 9 trước khi kết thúc hành trình tại nút 10. Như vậy trong mỗi giai đoạn người đi du lịch chỉ được quyền đi vào một thành phố mỗi thành phố được coi là một trạng thái của giai đoạn đó . Hãy tìm cách xác định đường đi ngắn nhất từ nút 1 tới nút 10 thoả mãn các điều kiện đặt ra của bài toán. Nguyên tắc tối ưu Bellman trong quy hoạch động Sử dụng nguyên tắc tối ưu Bellman trong quy hoạch động để giải bài toán người du lịch chúng ta chia bài toán thành nhiều giai đoạn tức là thành nhiều bài toán nhỏ. Tại mỗi giai đoạn ta cần tìm phương án tối ưu là các phương án tốt nhất của tình trạng hiện có xét trong mối quan hệ với các phương án tối ưu đã tìm được của các giai đoạn trước. Trường Đại học Nông nghiệp Hà Nội - Giáo trình Vận trù học 80 Ta có thể giải quyết bài toán dần theo từng giai đoạn theo cách tính toán tiến hoặc tính toán lùi. Để giải bài toán này ta áp dụng cách tính toán lùi backward computing với các kí kiệu và dữ kiện cho trong bảng . Bảng . Các giai đoạn của bài toán quy hoạch động

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.