<p>
Giải thuật cho những bài toán tối ưu thường đi qua một sốbước, với một tập hợp các
chọn lựa tại mỗi bước. Với nhiều bài toán tối ưu hoá có thểsửdụng phương pháp đơn
giản và hiệu quảhơn phương pháp qui hoạch động. Phương pháp tham lam luôn chọn
phương án tốt nhất vào thời điểm hiện tại. Nó chọn tối ưu cục bộvới hy vọng rằng lựa
chọn này sẽdẫn đến một kết quảtối ưu toàn cục. Trong chương này sẽchỉra những bài
toán tối ưu mà có thể được giải quyết bằng phương pháp tham lam. Trước khi đọc
chương này chúng ta nên đọc kỹvềphần quy hoạch động.
Phương pháp thamlam không phải luôn mang lại các kết quảtối ưu, nhưng có nhiều
bài toán nó có thểgiải quyết được. Trong khuôn khổ đềtài này, nhóm chúng tôi xin đưa
ra các phần nhưsau:
- Phần 1: giới thiệu bài toán chọn hoạt động, đối với vấn đềnày thì phương pháp tham
lam là hiệu quả để đưa ra kết quả. Ta sẽ đi đến một phương pháp tham lam bởi việc
xét đến đầu tiên là một giải pháp quy hoạch động và sau đó chỉra rằng ta có thểluôn
đưa ra những lựa chọn tham lam để đi đến một kết quảtối ưu.
- Phần 2: nhắc lại những yếu tốcơbản của phương pháp tham lam, đưa ra một một
cách tiếp cận trực tiếp hơn đểchứng minh phương pháp
tham lam đúng hơn dựa trên
quy hoạch động đã đềcập ởphần 1.
- Phần 3: giới thiệu một ứng dụng quan trọng của kỹthuật tham lam: một mô hình của
các chuẩn nén dữliệu.
- Phần 4: ta nghiên cứu kỹmột sốlý thuyết tổng hợp cơsở được gọi là "matroids" mà
đối với vấn đềnày phương pháp tham lam luôn đưa ra kết quảtối ưu.
- Phần 5: minh hoạ ứng dụng của việc sửdụng maitroids trong một bài toán lập lịch
làm việc với thời hạn cuối cùng và sốtiền phạt.
</p>
