Bài giảng Cơ sở lập trình nâng cao - Chương 8: Phương pháp thiết kế thuật toán − quy hoạch động

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. Mời các bạn cùng tham khảo chi tiết nội dung bài giảng.
Nội dung trích xuất từ tài liệu:
Bài giảng Cơ sở lập trình nâng cao - Chương 8: Phương pháp thiết kế thuật toán − quy hoạch động TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM KHOA CÔNG NGHỆ THÔNG TIN CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Ths.Tôn Quang Toại TonQuangToai@yahoo.com Chương 8 PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN − QUY HOẠCH ĐỘNG − 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ụ Hình ảnh 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 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 Quy hoạch động và Chia để trị Bài toán con trùng lắp (Overlapping subproblems) 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. 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 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 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ủa bài toán nhỏ để hình thành lời giải của bài toán lớn, rồi lưu kết quả lại 2 Tiếp cận cài đặt Quy hoạch động • Tiếp cận từ Dưới lên (Bottom Up): – Toàn bộ các bài toán con nhỏ nhất cần giải sẽ được giải trước – Sử dụng các kết quả để tìm nghiệm của bài toán lớn hơn – … – Quá trình tiếp tục cho đến khi bài toán cuối được giải 2 Tiếp cận cài đặt Quy hoạch • Sơ đồ cài đặtvoid { động SolveSmallProblems() } void SolveSubProblems() { } void Trace() { } void DynamicProgramming() { SolveSmallProvlems(); SolveSubProblems(); //Trace(); … } 2 Tiếp cận cài đặt Quy hoạch động • Ưu điểm của tiếp cận Bottom – Up – Tốn ít bộ nhớ • Khuyết điểm của tiếp cận Bottom – Up – Cài đặt dài hơn tiếp cận Top – Down – Vì để tiết kiệm bộ nhớ nên bài toán con nào dùng xong mà không dùng nữa thì bỏ đi  Sau khi giải xong sẽ không xem được trình tự quá trình giải (không lưu lại lịch sử) 2 Tiếp cận cài đặt Quy hoạch động • Tiếp cận từ trên xuống (Top Down) – Dùng đệ qui có nhớ (Memoization) – [Divide] Chia bài toán thành các bài toán con – [Solve] • Trước khi giải bài toán con, chúng kiểm tra xem bài toán này đã được giải trước đó chưa. – Nếu đã giải thì lấy lời giải trong bảng ra – Nếu chưa giải thì giải • Sau khi có lời giả thì chúng lưu kết quả lại vào bảng – [Combine] Kết hợp các lời giải của các bài 2 Tiếp cận cài đặt Quy hoạch • Sơ đồ cài đặt động void DynamicProgramming(A, x) { if (A đã giải quyết) x = LoiGiai(A); // Lấy lời giải từ bộ nhớ if (A du nho) LoiGiai(A) = Solve(A); //lưu lời giải bài //toán A vào bộ nhớ else { - Phan chia A thanh A0, A1, …, An-1 - for (i=0; i 2 Tiếp cận cài đặt Quy hoạch động • Ưu điểm của tiếp cận Top – Down – Cài đặt ngắn gọn – Có thể quan sát các bài toán con cần giải • Khuyết điểm của tiếp cận Top – Down – Tốn nhiều bộ nhớ vì phải lưu toàn bộ các bài toán con đã giải vì không biết bài toán con đó còn dùng nữa hay không Ví dụ • Tính số Fibonacci thứ n 1 Nếu n=1 hay n=2 Fn = Fn −1 + Fn − 2 Nếu n >2 § Hai tiếp cận bằng Quy hoạch động • Dùng tiếp cận từ trên xuống • Dùng tiếp cận từ dưới lên Ví dụ cài đặt void QHD_TopDown(int n) { } Ví dụ cài đặt void QHD_BottomUp(int n) { } ...