Thuật toán Tham lam (Greedy)
Tư duy chọn lựa chọn tốt nhất tại mỗi bước, khi nào Greedy cho kết quả tối ưu toàn cục, và ứng dụng thực tế (interval scheduling, Huffman coding).
Greedy là chiến lược đơn giản và hiệu quả nhất khi áp dụng đúng chỗ — nhưng cũng là chiến lược dễ áp dụng sai nhất, vì "chọn tốt nhất ngay bây giờ" không phải lúc nào cũng dẫn đến kết quả tốt nhất tổng thể. Biết khi nào tin tưởng Greedy là kỹ năng phán đoán quan trọng.
🎯 Mục tiêu học tập
- Hiểu nguyên lý của thuật toán Greedy: chọn lựa chọn tốt nhất cục bộ tại mỗi bước
- Nhận diện điều kiện (Greedy Choice Property) để Greedy cho kết quả tối ưu toàn cục
- Giải bài toán Interval Scheduling kinh điển bằng Greedy
- Hiểu ứng dụng Huffman Coding trong nén dữ liệu
Nguyên lý Greedy & Khi nào KHÔNG hoạt động
Thuật toán Greedy đưa ra quyết định tốt nhất tại thời điểm hiện tại, không bao giờ quay lại xem xét lại quyết định đã đưa ra — đơn giản và nhanh (thường O(n log n) nhờ bước sắp xếp), nhưng không phải lúc nào cũng cho kết quả tối ưu toàn cục. Ví dụ kinh điển về Greedy thất bại: bài toán đổi tiền với hệ mệnh giá {1, 3, 4} để đổi 6 đồng — Greedy chọn 4 trước (lớn nhất ≤ 6), còn lại 2, cần thêm 2 đồng mệnh giá 1 → tổng 3 đồng; nhưng đáp án tối ưu thực sự là 3+3 → chỉ 2 đồng. Greedy chọn sai vì quyết định "tham lam nhất" ban đầu (chọn 4) không dẫn đến lời giải tối ưu toàn cục.
Chỉ dùng Greedy khi bài toán có Greedy Choice Property (chứng minh được: luôn tồn tại lời giải tối ưu bắt đầu bằng lựa chọn tham lam) VÀ Optimal Substructure (lời giải tối ưu của bài toán lớn chứa lời giải tối ưu của bài toán con) — nếu không chắc chắn, Dynamic Programming (Module 8) là lựa chọn an toàn hơn dù chậm hơn.
Interval Scheduling — bài toán Greedy kinh điển
Bài toán: cho N khoảng thời gian (mỗi khoảng có giờ bắt đầu/kết thúc), chọn được nhiều khoảng không chồng lấn nhau nhất (ví dụ: lịch họp phòng, đặt lịch tài nguyên). Chiến lược Greedy đúng: luôn sắp xếp theo thời gian kết thúc sớm nhất, chọn khoảng kết thúc sớm nhất còn hợp lệ trước — bài toán này chứng minh được có Greedy Choice Property (chọn khoảng kết thúc sớm luôn để lại nhiều "chỗ trống" nhất cho các lựa chọn tiếp theo):
def max_khoang_khong_chong_lan(intervals: list[tuple[int, int]]) -> int:
intervals.sort(key=lambda x: x[1]) # sắp xếp theo giờ kết thúc
count, end_time = 0, float("-inf")
for start, end in intervals:
if start >= end_time: # không chồng lấn với khoảng đã chọn gần nhất
count += 1
end_time = end
return count
Ứng dụng thực tế: đặt lịch phòng họp, lập lịch CPU (chọn tối đa số tiến trình hoàn thành trước deadline), và cân nhắc trực tiếp cho các bài toán resource scheduling trong hệ thống backend.
Huffman Coding — Greedy trong nén dữ liệu
Huffman Coding xây mã nhị phân có độ dài thay đổi cho từng ký tự, sao cho ký tự xuất hiện càng thường xuyên thì mã càng ngắn — dùng Greedy: liên tục gộp 2 node có tần suất thấp nhất (dùng Min-Heap — Module 5!) thành 1 node cha, lặp lại cho đến khi chỉ còn 1 cây, tạo ra mã có tổng độ dài kỳ vọng tối ưu. Đây là nền tảng cho nhiều thuật toán nén dữ liệu (một phần của ZIP, JPEG, MP3) — ví dụ sống động cho thấy Greedy + cấu trúc dữ liệu đã học (Heap) kết hợp giải quyết bài toán thực tế quan trọng.
🏋️ Bài tập thực hành
Triển khai hàm giải bài toán Interval Scheduling ở trên. Thử nghiệm với 1 chiến lược Greedy SAI (ví dụ sắp xếp theo thời gian bắt đầu thay vì kết thúc) trên cùng 1 tập dữ liệu — tìm 1 ví dụ cụ thể mà chiến lược sai cho kết quả kém hơn chiến lược đúng, viết giải thích tại sao.
📚 Tài nguyên học tập
-
GeeksforGeeks — Greedy AlgorithmsTổng hợp các bài toán Greedy kinh điển kèm lời giảiBài viết
-
VisuAlgo — Huffman CodingTrực quan hoá Huffman Coding và các bài toán Greedy khácTool
✅ Tự đánh giá hoàn thành
- Giải thích được nguyên lý Greedy và ví dụ cụ thể khi nó thất bại
- Giải thích được Greedy Choice Property và Optimal Substructure
- Giải đúng bài toán Interval Scheduling bằng chiến lược Greedy đúng
- Hiểu được ứng dụng Huffman Coding trong nén dữ liệu thực tế