Timtailieu.net 
Phân tích tư tưởng của nhân dân qua đoạn thơ: Những người vợ nhớ chồng… Những cuộc đời đã hóa sông núi ta trong Đất nước của Nguyễn Khoa Điềm
3403
1
0
9 trang
Bài giảng Chiến lược tham lam nhằm trình bày các nội dung chính: khái niệm chiến lược tham lam, khái niệm về bài toán lựa chọn công việc, cấu trúc tối ưu và lời giải đệ quy...Bài giảng được trình bày khoa học, súc tích giúp các bạn sinh viên tiếp thu bài học nhanh.
Nội dung trích xuất từ tài liệu:
Bài giảng Chiến lược tham lam - Phạm Văn CườngChiến lược tham lam(Greedy algorithms) Phạm Văn Cườnghttp://newcastle.academia.edu/CuongPham/Chiến lược tham lam• Tìm kiếm lời giải tối ưu cục bộ (local optimization) ở mỗi bước đi, với hy vọng lời giải này sẽ dẫn tới lời giải tối ưu toàn cục.• So với qui hoạch động: duyệt tất cả các lời giải của bài toán con tại mỗi bước số phương án phải duyệt của giải thuật tham lam ít hơn.• Hạn chế: không phải lời giải tối ưu cục bộ nào cũng là lời giải tối ưu toàn cục.Bài toán lựa chọn công việcS={a1,a2,..,an} tập n công việc.Mỗi công việc ai có thời điểm khởi đầu si và thời điểm kết thúc fi. 0fi)Bài toán lựa chọn công việcBài toán lựa chọn công việcCấu trúc tối ưu• Sij={ak : fiLời giải đệ quiThuật toán tham lam đệ quiThuật toán tham lam lặpVí dụ
