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 - 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

ra | 0 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ũ)

I Dễ thiết kế, dễ cài đặt | 0 Thuật toán quy hoạch động

- 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 - Độ phức tạp thấp hơn (thường hàm đa thức) . Tuy nhiên, khó thiết kế và cài đặt giải pháp