Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại
Đị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
Phương pháp
Phát biểu bài toán: Giả sử bài toán yêu cầu tìm phương án X=(x1, x2, , xn), trong đó
xi được chọn ra từ tập Di.
f(X) là hàm đánh giá sự tốt nhất của phương án X (f là hàm mục tiêu hay hàm chi phí)
Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại trang 1
Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại trang 2
Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại trang 3
Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại trang 4
Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán. Tham lam - Tôn Quang Toại trang 5
Tải về để xem đầy đủ hơn
File đính kèm:
bai_giang_co_so_lap_trinh_nang_cao_chuong_7_phuong_phap_thie.pptx
