tailieunhanh - Bài giảng Lập trình động

"Bài giảng Lập trình động" tìm hiểu về quy hoạch động; đặc điểm của phương pháp chia để trị; một chiến lược tối ưu có đặc trưng; chuỗi con đơn điệu dài nhất. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết nội dung kiến thức. | Dynamic Programming Introduction Quy hoạch động Thường dùng để giải các bài toán tối ưu Phân rã bài toán thành các bài toán con hình thành lời giải từ các bài toán con Lưu trữ lời giải các bài toán con trong một bảng dữ liệu thay cho giải lại các bài toán con đệ quy . Đặc điểm của phương pháp chia để trị Thường phát sinh các bài toán con mới Lời giải các bài toán con thường được sử dụng nhiều lần phủ chồng . 2013-09-22 Dao Thanh Tinh 2 Introduction 2 Ví dụ 1 Tính số Fibonacci thứ n Đệ quy với f0 0 và f1 1 long f int m if n 0 return 0 Theo công thức else if n 1 return 1 n n 1 5 1 5 else return f n-1 f n 2 2 fn Ví dụ để tính f n phải tính f 2 n-1 lần 5 Tiết kiệm bộ nhớ Dùng mảng f0 0 f1 1 f 0 0 f 1 1 for i 2 i n i for i 2 i n i tg f1 f0 f i f i-1 f i-2 f0 f1 output f n f1 tg output f1 2013-09-22 Dao Thanh Tinh 3 Introduction 3 Số Fibonacci thứ n n 50 F n 12 586 269 025 Phương pháp đệ quy 650 800s Các phương pháp khác 1s 2013-09-22 Dao Thanh Tinh 4 Introduction 4 Tiếp cận theo hướng bottom-up 1. Xuất phát từ những bài toán cơ sở có lời giải cách giải đơn giản hoặc có sẵn 2. Từ tập lời giải các bài toán con tìm lời giải của bài toán lớn hơn. 2013-09-22 Dao Thanh Tinh 5 Introduction 5 PRINCIPLE OF OPTIMALITY An optimal policy has the property that whatever the initial state and initial decisions are the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions. Richard Bellman The Theory of Dynamic Programming Bulletin of the American Mathematical Society Vol. 60 No. 6 1954 503-515 . 2013-09-22 Dao Thanh Tinh 6 Introduction 6 Một chiến lược tối ưu có đặc trưng với mọi trạng thái khởi tạo và quyết định ban đầu các quyết định tiếp theo phải thiết lập được chiến lược tối ưu đối với trạng thái được hình thành từ các quyết định trước đó. Chiến lược tối ưu có thể trong một số bước đầu tiên lựa chọn dường như không tốt nhưng tổng hợp cả quá trình phải tốt nhất. 2013-09-22 Dao Thanh Tinh 7 Introduction 7 Kỹ thuật giải bài