tailieunhanh - Bài giảng Phân tích thiết kế giải thuật: The Greedy algorithms - GV. Hà Đại Dương

Bài giảng trình bày về các tối ưu thuật toán bằng phương pháp tham lam và các bài tập minh họa: bài toán cái túi, bài toán người du lịch, đường đi ngắn nhất,. Để tìm hiểu rõ hơn về nội dung chi tiết của bài giảng, . | 2/2/2017 Analysis and Design of Algorithms Lecture 6,7 The Greedy algorithms 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 cái túi Bài toán người du lịch Đường đi ngắn nhất Cây bao trùm nhỏ nhất Bài toán tô màu Bài toán các khoảng không giao nhau 2/2/2017 2 Nội dung 1. 2. 3. 4. 5. 6. 7. Lược đồ chung Bài toán cái túi Bài toán người du lịch Đường đi ngắn nhất Cây bao trùm nhỏ nhất Bài toán tô màu Bài toán các khoảng không giao nhau 2/2/2017 3 1 2/2/2017 Bài toán tối ưu • PP Tham lam thường dùng cho các bài toán tối ưu tổ hợp (tối ưu rời rạc) • Bài toán tối ưu tổ hợp có dạng chung min{f(x):x D} Trong đó D tập hữu hạn các điểm rời rạc nào đó thuộc không gian Rn 2/2/2017 4 Ví dụ Máy ATM có 4 (m) loại tiền: , , , ; một người muốn rút số tiền là n (n chia hết cho ). Hãy tìm phương án trả tiền sao cho số tờ tiền phải trả là ít nhất. Gọi x=(x1,x2,x3,x4) là một phương án trả tiền; x1, x2, x3, x4 là số tờ tiền phải trả tương ứng với các mệnh giá , , . Theo bài ra ta cần giải: min(f=x1+x2+x3+x4) Với: điều kiện - = n - xi>=0 (i=14) 2/2/2017 5 Giải quyết • Với bài toán tối ưu tổ hợp min{f(x):x D} • Để tìm phương án tối ưu của bài toán trên người ta có thể so sánh lần lượt giá trị của f tại tất cả các phương án thuộc D; cách này gọi là “duyệt vét cạn”. • Khi số phần tử của D lớn (dù là hữu hạn) thì việc duyệt vét cạn vẫn gặp nhiều khó khăn. 2/2/2017 6 2 2/2/2017 PP Tham lam • PP tham lam đưa ra quyết định dựa ngay vào thông tin đang có, và trong tương lai sẽ không xem xét lại tác động của các quyết định trong quá khứ. • Chính vì thế các thuật toán dạng này rất dễ đề xuất, và thông thường chúng không đòi hỏi nhiều thời gian tính. • Tuy nhiên, các thuật toán dạng này thường không cho kết quả tối ưu. 2/2/2017 7 Ý tưởng • Xuất phát từ lời giải rỗng, thuật toán xây dựng lời giải của bài toán

• Kỹ thuật lập trình
• Phân tích thiết kế giải thuật
• Thuật toán tham lam
• Bài toán cái túi
• Bài toán người du lịch
• Bài toán đường đi ngắn nhất
• Bài toán cây bao trùm nhỏ nhất
• Bài toán tô màu
• Bài toán các khoảng không giao nhau
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Phân tích thiết kế thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Cắt tỉa Alpha Beta
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Thuật toán sắp xếp
• Phân tích thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phân tích thuật toán tìm kiếm
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phân tích giải thuật
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật giải
• Thiết kế thuật giải
• Chiến lược thiết kế thuật giải
• Quy hoạch động
• Biểu diễn thuật giải
• Phân tích thiết kế thuật toán
• Kỹ thuật tối ưu hóa chương trình
• Mức thiết kế một chương trình
• Kỹ thuật tinh chế mã
• Kỹ thuật tối ưu hóa rẽ nhánh
• Phương pháp thiết kế thuật toán
• Tối ưu thuật toán
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Giải thuật sắp xếp
• Chương trình sắp xếp
• Cấu trúc dữ liệu
• Giải thuật lưu trữ ngoài
• Giải thuật nâng cao
• Kỹ thuật phân tích giải thuật
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• Giải thuật đệ quy
• Thiết kế giải thuật đệ quy
• Đệ quy tuyến tính
• Đệ quy nhị phân