tailieunhanh - Bài giảng Thuật toán ứng dụng: Quy hoạch động - Trương Xuân Nam

Bài giảng Thuật toán ứng dụng: Quy hoạch động cung cấp cho người học những kiến thức như: Ý tưởng quy hoạch động; Bài toán đoạn con lớn nhất; Bài toán dãy con chung dài nhất; Bài toán đếm số dãy con có tổng cho trước; Bài toán xếp ba lô; Phân tích về quy hoạch động; Bài tập. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Quy hoạch động Nội dung 1. Ý tưởng quy hoạch động 2. Bài toán đoạn con lớn nhất 3. Bài toán dãy con chung dài nhất 4. Bài toán đếm số dãy con có tổng cho trước 5. Bài toán xếp ba lô 6. Phân tích về quy hoạch động 7. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Ý tưởng quy hoạch động TRƯƠNG XUÂN NAM 3 Top-down vs Bottom-up TRƯƠNG XUÂN NAM 4 Top-down Fibo 5 Fibo 4 Fibo 3 Fibo 3 Fibo 2 Fibo 2 Fibo 1 Fibo 2 Fibo 1 Fibo 1 Fibo 0 Fibo 1 Fibo 0 Fibo 1 Fibo 0 TRƯƠNG XUÂN NAM 5 Bottom-up Fibo 1 Fibo 0 Fibo 2 Fibo 1 Fibo 1 Fibo 0 Fibo 1 Fibo 0 Fibo 3 Fibo 2 Fibo 2 Fibo 1 Fibo 4 Fibo 3 Fibo 5 TRƯƠNG XUÂN NAM 6 Top-down vs Bottom-up Top-down Nhìn theo hướng từ trên xuống dưới Chia bài toán lớn thành các bài toán nhỏ Tiếp cận chia để trị Bottom-up Nhìn theo hướng từ dưới lên trên Giải bài toán nhỏ trước Tổ hợp các lời giải nhỏ thành lời giải của bài toán lớn Quy hoạch động Dynamic programming Richard Bellman 1953 Thường dùng cho các bài toán tối ưu Nguyên tắc lời giải tối ưu của bài toán lớn sử dụng kết quả tối ưu của bài toán con TRƯƠNG XUÂN NAM 7 Phần 2 Bài toán đoạn con lớn nhất TRƯƠNG XUÂN NAM 8 Bài toán đoạn con lớn nhất Đã giới thiệu từ ngay buổi học đầu tiên Cho dãy A a1 a2 . an-1 an tìm đoạn con dãy con liên tiếp trong A có tổng các phần tử là lớn nhất Giải Đặt Si là tổng lớn nhất của đoạn con kết thúc tại ai Kết quả cần tìm max S1 S2 . Sn-1 Sn Tính Sk 1 1 ế 1 0 ቊ 1 ế 1 gt 0 Quy hoạch động tính giá trị Sk sử dụng kết quả tính Sk-1 Cài đặt dễ TRƯƠNG XUÂN NAM 9 Phần 3 Bài toán dãy con chung dài nhất TRƯƠNG XUÂN NAM 10 Bài toán dãy con chung dài nhất Longest common subsequence LCS Cho 2 dãy A a1 a2 . am-1 am và B b1 b2 . bn-1 bn Dãy con dãy được lập ra từ dãy cha bằng cách chọn lấy một số phần tử giữ nguyên thứ tự Không nhất thiết phải liên tiếp Có thể không chứa phần tử nào Dãy con chung của A và B là dãy con của cả A và B Cần tìm dãy con có nhiều phần tử nhất dài nhất Ví dụ A 3 1 2 0 4 3 B 1 2 3 4 3 2 1 KQ 1 2 4 3 TRƯƠNG XUÂN NAM 11 Bài toán dãy con chung dài .