Bài giảng cung cấp cho người học các kiến thức: Phương pháp thiết kế thuật toán − quy hoạch động, bài toán tối ưu, nguyên lý tối ưu của Bellman,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − QUY HOẠCH ĐỘNG − Chương 8 2 Nội dung Giới thiệu Quy hoạch động và Chia để trị Quy hoạch động và Bài toán tối ưu Nguyên lý tối ưu của Bellman Sơ đồ cài đặt Các ví dụ 3 Hình ảnh 4 Giới thiệu Quy hoạch động – Dynamic Programming do nhà toán học người Mĩ Richard Bellman (1920 – 1984) phát minh vào năm 1957 Quy hoạch động – Dynamic Programming là phương pháp để giải quyết một lớp lớn các bài toán tối ưu thỏa theo nguyên lý tối ưu Bellman 5 Giới thiệu Dựa trên phương pháp Quy hoạch động, nhiều thuật toán nổi tiếng đã ra đời: Một số thuật toán nổi tiếng dựa trên phương pháp Quy hoạch động Thuật toán Dijkstra Thuật toán Ford – Bellman Thuật toán Floyd Thuật toán Viterbi Thuật toán huấn luyện Adaptive Critic Thuật toán Cocke – Younger – Kasami 6 Quy hoạch động và Chia để trị Bài toán con trùng lắp (Overlapping subproblems) 7 Phương pháp Phương pháp Quy hoạch động gần giống với phương pháp Chia để trị. Cả hai phương pháp dùng để giải quyết bài toán bằng cách kết hợp các lời giải của các bài toán con. 8 Phương pháp Phương pháp Chia để trị: Là phương pháp từ trên xuống dưới (top – down) với ý tưởng: [Divide] Chia bài toán lớn thành những bài toán nhỏ hơn và độc lập nhau [Solve] Giải quyết các bài toán nhỏ [Combine] Kết hợp các lời giải bài toán nhỏ để hình thành lời giải bài toán lớn 9 Phương pháp Hạn chế của phương pháp Chia để trị: Khi dùng phương pháp chia để trị để chia 1 bài toán lớn thành các bài toán con, các bài toán con lại chia nhỏ thành nhiều bài toán con nhỏ hơn nữa, Đôi khi một bài toán con được yêu cầu giải nhiều lần Chương trình chạy chậm 10 Phương pháp Phương pháp Quy hoạch động: Là phương pháp giải quyết bài toán bằng cách: [Solve & Restore] Giải quyết các bài toán nhỏ nhất, rồi lưu kết quả lại [Combine & Restore] Kết hợp các lời giải | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − QUY HOẠCH ĐỘNG − Chương 8 2 Nội dung Giới thiệu Quy hoạch động và Chia để trị Quy hoạch động và Bài toán tối ưu Nguyên lý tối ưu của Bellman Sơ đồ cài đặt Các ví dụ 3 Hình ảnh 4 Giới thiệu Quy hoạch động – Dynamic Programming do nhà toán học người Mĩ Richard Bellman (1920 – 1984) phát minh vào năm 1957 Quy hoạch động – Dynamic Programming là phương pháp để giải quyết một lớp lớn các bài toán tối ưu thỏa theo nguyên lý tối ưu Bellman 5 Giới thiệu Dựa trên phương pháp Quy hoạch động, nhiều thuật toán nổi tiếng đã ra đời: Một số thuật toán nổi tiếng dựa trên phương pháp Quy hoạch động Thuật toán Dijkstra Thuật toán Ford – Bellman Thuật toán Floyd Thuật toán Viterbi Thuật toán huấn luyện Adaptive Critic Thuật toán Cocke – Younger – Kasami 6 Quy hoạch động và Chia để trị .
