Thuật toán tham lam (Greedy algorithm) là gì?

 

Thuật toán tham lam (Greedy algorithm) là một trong những chiến lược thiết kế thuật toán cơ bản và mạnh mẽ trong khoa học máy tính và toán học tổ hợp.

---

🎯 Định nghĩa ngắn gọn

Thuật toán tham lam (Greedy) là chiến lược giải quyết bài toán bằng cách:

👉 Ở mỗi bước, luôn chọn phương án tốt nhất tại thời điểm đó (tối ưu cục bộ)
👉 Hy vọng rằng các lựa chọn tối ưu cục bộ sẽ dẫn đến lời giải tối ưu toàn cục

---

📌 Cốt lõi của thuật toán tham lam

• Không quay lui (backtracking)

• Không xét tất cả khả năng (như quy hoạch động)

• Chọn ngay cái “tốt nhất lúc đó”

---

🧠 Cấu trúc của một thuật toán Greedy:

1. Khởi tạo: Bắt đầu từ trạng thái ban đầu (thường là rỗng hoặc toàn bộ)

2. Lặp lại:

   • Xét các lựa chọn khả dĩ hiện tại

   • Chọn phương án tốt nhất theo một tiêu chí (giá trị lớn nhất, chi phí nhỏ nhất, v.v.)

   • Cập nhật lời giải từng bước

3. Kết thúc khi đủ điều kiện (thường là hết phần tử)

---

✅ Điều kiện để Greedy cho lời giải đúng

Không phải bài nào cũng áp dụng được Greedy! Để Greedy hoạt động hiệu quả, bài toán thường phải thỏa 2 tính chất sau:

1. Tính chất con tối ưu (Optimal substructure):
   → Lời giải tối ưu toàn cục bao gồm các lời giải tối ưu của các bài toán con.

2. Tính chất chọn lựa tham lam (Greedy choice property):
   → Có thể chọn phương án tốt nhất trước mà không làm ảnh hưởng đến lời giải sau.

---

🔍 Ví dụ điển hình về thuật toán Greedy

1. Đổi tiền (coin change)

Cho các mệnh giá: 1k, 2k, 5k, 10k,… và tổng tiền cần đổi là 23k.
Hỏi cần ít tờ tiền nhất để đổi?

📌 Greedy: Luôn chọn tờ lớn nhất ≤ số tiền còn lại
→ 10+10+2+1=23 với 4 tờ

✅ Đúng nếu mệnh giá "đẹp" (chia hết)
❌ Sai nếu mệnh giá không chuẩn (vd: 1, 3, 4)

---

2. Balo phân số (Fractional Knapsack)

Có các vật phẩm có trọng lượng và giá trị. Chọn sao cho tổng trọng lượng không quá W, mà giá trị là lớn nhất.

📌 Greedy: Chọn theo giá trị trên đơn vị trọng lượng (v/l) cao nhất trước
→ Có thể lấy một phần vật (phân số)

✅ Greedy cho kết quả đúng 100%

---

3. Hoạt động không giao nhau (Interval Scheduling)

Cho danh sách các hoạt động với thời gian bắt đầu–kết thúc. Chọn nhiều hoạt động nhất sao cho không bị trùng giờ.

📌 Greedy: Sắp xếp theo thời gian kết thúc sớm nhất
→ Duyệt và chọn lần lượt các hoạt động

✅ Đúng hoàn toàn – classic problem

---

📚 Ứng dụng thực tế của thuật toán Greedy

• Lập lịch hoạt động (sân bay, hội nghị,…)

• Nén dữ liệu (thuật toán Huffman)

• Bài toán đường đi ngắn nhất (Dijkstra)

• Bài toán cây khung nhỏ nhất (Prim, Kruskal)

• Chứng minh toán học tổ hợp (với phản chứng + cực trị)

---

📝 Tóm tắt ngắn gọn để nhớ: