Qui hoạch động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Để biết rõ hơn về phương pháp qui hoạch động, bài giảng. | 2/2/2017 Analysis and Design of Algorithms Lecture 9,10 Dynamic Programming Lecturer: Ha Dai Duong duonghd@ 2/2/2017 1 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán tính số Fibonaci Bài toán cái túi Bài toán dãy con có tổng lớn nhất Bài toán tìm xâu con chung dài nhất Đường đi ngắn nhất - TT Floyd Cây nhị phân tìm kiếm tối ưu 2/2/2017 2 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán tính số Fibonaci Bài toán cái túi Bài toán dãy con có tổng lớn nhất Bài toán tìm xâu con chung dài nhất Đường đi ngắn nhất - TT Floyd Cây nhị phân tìm kiếm tối ưu 2/2/2017 3 1 2/2/2017 Chia để trị • Khi chia bài toán thành các bài toán con, trong nhiều trường hợp, các bài toán con khác nhau lại chứa các bài toán con hoàn toàn giống nhau. • Ví dụ: Tính số Fibonaci thứ n, F(n): • F(0)=0, F(1)=1 • F(n)=F(n-2)+F(n-1) với n>1 • F(2)=1, F(3)= 2, F(4) = 3 , F(5)=5, F(6)=8 2/2/2017 4 Chia để trị • Fib(n): Tiếp cận theo hướng chia để trị F(n) = F(n-1) + F(n-2) Function Fib(n) { If n<2 then return n; else return Fib(n-1) + Fib(n-2); } 2/2/2017 5 Chia để trị • Fib(5) F5 F4 F3 F1 F2 F2 F0 F1 F0 F3 F1 F1 F2 F0 Tính lại các bài toán con nhiều lần 2/2/2017 Khắc phục? F1 Quy hoạch động 6 2 2/2/2017 Qui hoạch động • • Là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Khác với chia để trị, quy hoạc động, thay vì gọi đệ quy, sẽ tính trước lời giải của các bài toán con và lưu vào bộ nhớ (thường là một mảng), và sau đó lấy lời giải của bài toán con ở trong mảng đã tính trước để giải bài toán lớn 2/2/2017 7 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (TopDown) F5 F4 F3 F1 F2 F2 F0 F0 F1 F3 F1 F1 F2 F0 F1 2/2/2017 8 Qui hoặc động vs Chia để trị • Chia để trị: Tiếp cận từ trên xuống (TopDown) F5 F4 F3 F1 F2 F2 F0 F1 F0 F3 F1 F1 F2 F0 2/2/2017 F1 9 3 2/2/2017 Qui hoặc động .
