Table of contents
Open Table of contents
1. Yêu cầu
Để có thể giải bằng thuật toán greedy thì phải đảm bảo 2 tính chất sau:
- Optimal Substructure
- Greedy choice Property
Minh họa: Bài toán chọn số hoạt đồng nhiều nhất
2. Mã giả
- Cần sắp xếp tập các lựa chọn P dựa trên các tiêu chí greedy
- Duyệt qua tập P và nếu thỏa mãn ràng buộc thì lựa chọn, không thì bỏ qua và đến lựa chọn kế tiếp
3. Bài toán kinh điển
3.1. TSP
Yêu cầu: Hãy tưởng tượng một người bán hàng cần đi qua mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát, sao cho tổng quãng đường đi là ngắn nhất. Input: tập hợp thành phố và ma trận khoảng cách giữa các cặp thành phố. Ràng buộc: mỗi thành phố được thăm một và chỉ một lần, trừ điểm xuất phát được quay lại đúng một lần ở cuối. Output: tập hợp thành phố sao cho tổng khoảng cách là nhỏ nhất
Theo chiến lược greedy: Ta sẽ lựa chọn thành phố gần nhất với thành phố hiện tại ở từng bước