Thuật toán THAM LAM 💎(Greedy Algorithm)
Bản chất của Giải thuật Tham lam (Greedy Algorithm) có thể được gói gọn trong một câu: "Lựa chọn tối ưu ở hiện tại với hy vọng sẽ dẫn đến kết quả tối ưu toàn cục."
Để hiểu sâu hơn, chúng ta hãy phân tích bản chất của nó qua các khía cạnh sau:
1. Nguyên tắc "Ăn ngay" (Short-sightedness)
Giải thuật tham lam không nhìn xa trông rộng. Khi đứng trước nhiều sự lựa chọn, nó không tính toán xem lựa chọn này sẽ ảnh hưởng thế nào đến tương lai. Nó chỉ đơn giản là:
Xem xét tất cả các phương án khả thi tại bước hiện tại.
Chọn phương án tốt nhất ngay lúc đó (ví dụ: số tiền lớn nhất, quãng đường ngắn nhất, giá trị cao nhất).
Sau khi chọn xong, nó không bao giờ thay đổi quyết định (không quay lui như thuật toán Backtracking).
2. Các thành phần cốt lõi của bản chất tham lam
Để một giải thuật được gọi là tham lam, nó phải tuân thủ các đặc điểm:
Tập hợp ứng viên (Candidate set): Một danh sách các đối tượng để tạo ra lời giải (ví dụ: các mệnh giá tiền).
Hàm lựa chọn (Selection function): Quy tắc để chọn ứng viên tốt nhất (ví dụ: chọn tờ tiền to nhất).
Hàm kiểm tra tính khả thi (Feasibility function): Kiểm tra xem ứng viên được chọn có vi phạm ràng buộc không (ví dụ: chọn tờ tiền đó có làm tổng tiền vượt quá yêu cầu không).
Hàm mục tiêu (Objective function): Gán giá trị cho lời giải (ví dụ: số lượng tờ tiền phải là ít nhất).
3. Khi nào bản chất "Tham lam" đem lại kết quả đúng?
Không phải lúc nào tham lam cũng cho ra kết quả đúng nhất (tối ưu toàn cục). Bản chất tham lam chỉ thực sự hiệu quả khi bài toán thỏa mãn hai điều kiện:
Cấu trúc con tối ưu (Optimal Substructure): Lời giải tối ưu của bài toán lớn chứa đựng lời giải tối ưu của các bài toán nhỏ hơn.
Đặc điểm lựa chọn tham lam (Greedy Choice Property): Một lựa chọn tối ưu địa phương có thể dẫn đến lời giải tối ưu toàn cục mà không cần xem xét lại các lựa chọn cũ.
Ví dụ:
Bài toán đổi tiền VND: Tham lam luôn đúng vì các mệnh giá (500k, 200k, 100k...) được thiết kế để tờ lớn bao quát được các tờ nhỏ.
Bài toán đổi tiền với mệnh giá bất kỳ (ví dụ: 1, 3, 4): Nếu cần đổi 6 đồng. Tham lam sẽ chọn 4 + 1 + 1 (3 tờ). Nhưng đáp án đúng phải là 3 + 3 (2 tờ). Trong trường hợp này, bản chất tham lam đã thất bại.
4. So sánh với các giải thuật khác
So với Quay lui (Backtracking): Quay lui thử mọi trường hợp, thấy sai thì sửa (tốn thời gian nhưng luôn đúng). Tham lam chỉ đi một đường duy nhất, không quay lại (nhanh nhưng có thể sai).
So với Quy hoạch động (Dynamic Programming): Quy hoạch động tính toán mọi bài toán con và lưu lại để phối hợp (tối ưu tuyệt đối). Tham lam chỉ chọn cái tốt nhất trước mắt.
Tóm lại:
Bản chất của tham lam là sự đánh đổi. Bạn đánh đổi sự chính xác tuyệt đối trong mọi tình huống để lấy tốc độ cực nhanh và sự đơn giản trong lập trình. Trong thực tế, thuật toán tham lam thường được dùng để giải các bài toán xấp xỉ khi mà việc tìm ra đáp án chính xác 100% tốn quá nhiều thời gian.
Bước: 0 / 0
Sẵn sàng minh họa giải thuật Tham lam!