Bài giảng Thuật toán nâng cao - Chương 7: Thuật toán tham lam - Nguyễn Thanh Bình

Thuật toán tham lam (greedy algorithms)

 Vấn đề tìm kiếm giải pháp tối ưu

1 Chia bài toán thành nhiều bài toán Con 1 Giải quyết các bài toán con 1 Giải pháp của các bài toán con sẽ là giải pháp cho bài toán đặt

 Thuật toán chia để trị hoặc thuật toán đơn giản

1 Giải quyết tất cả các bài toán con | 1 Độ phức tạp cao (thường hàm mũ)

1 D. thiết kế, dễ cài đặt u Thuật toán quy hoạch động 1 Ghi nhớ lại giải pháp của các bài toán con (khi các bài

toán con không hoàn toàn độc lập) để tránh các xử lý trùng lặp 1 Độ phức tạp thấp hơn (thường hám đa thức) 1 Tuy nhiên, khó thiết kế và cài đặt giải pháp