Thuật toán tham lam: lựa chọn cục bộ và phản ví dụ

Tham lam chọn tốt nhất ở thời điểm hiện tại

Thuật toán tham lam xây lời giải từng bước, mỗi bước chọn phương án cục bộ theo tiêu chí và không quay lại. Cách làm có thể rất nhanh, nhưng chỉ tối ưu khi bài toán có cấu trúc thích hợp và cần được chứng minh.

Ví dụ đúng: chọn hoạt động

Muốn chọn nhiều khoảng thời gian không chồng lấn nhất, sắp theo thời điểm kết thúc tăng dần và luôn chọn hoạt động kết thúc sớm nhất còn tương thích. Lập luận trao đổi cho thấy có thể thay lựa chọn đầu của một nghiệm tối ưu bằng lựa chọn tham lam mà không giảm số hoạt động.

Ví dụ sai: đổi tiền tùy hệ mệnh giá

Với mệnh giá {1,3,4}, đổi 6 theo đồng lớn nhất cho 4+1+1 (3 đồng), nhưng tối ưu là 3+3 (2 đồng). Tham lam đúng với một số hệ tiền, không đúng với mọi hệ.

Quy trình đánh giá

1. Xác định tiêu chí lựa chọn cục bộ.
2. Kiểm tra tính khả thi sau mỗi bước.
3. Tìm phản ví dụ nhỏ bằng vét cạn.
4. Nếu chưa bị bác bỏ, xây chứng minh trao đổi hoặc bất biến.
5. So độ phức tạp và yêu cầu sắp xếp.

⚠️ Dữ liệu mẫu đạt không phải chứng minh

Test giúp tìm sai, còn tính tối ưu cho mọi đầu vào cần lập luận. Nếu không có cấu trúc tham lam, có thể cần quy hoạch động.

✍️ Luyện tập

Viết chương trình vét cạn cho bộ tiền nhỏ để tự động tìm phản ví dụ của chiến lược lấy đồng lớn nhất trước.