CƠ SƠ LẬP TRINH
NÂNG CAO
Biên soạn: Ths.Tôn Quang Toại
TonQuangToai@yahoo.com
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM
KHOA CÔNG NGHỆ THÔNG TIN
PHƯƠNG PHÁP THIẾT KẾ
THUẬT TOÁN
– THAM LAM –
Chương 7
Nội dung
•Giới thiệu
•Phương pháp
•Sơ đồ cài đặt
•Các ví dụ
•Ưu điểm và khuyết điểm
Hình ảnh
1
2
3
4
5
Giới thiệu
•Định nghĩa [Tham lam – Greedy]: Tham
lam là một phương pháp thiết kế thuật
toán để tìm nghiệm của bài toán tối ưu
bằng cách xây dựng nghiệm dần dần
từng bước. Tại mỗi bước:
–Chúng ta luôn luôn chọn giá trị tốt nhất tại
thời điểm đó mà không quan tâm đến tương
lai (tối ưu cục bộ)
–Chúng ta hy vọng việc chọn các tối ưu cục bộ
tại mỗi bước sẽ cho tối ưu toàn cục