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