Bài giảng Chiến lược tham lam - Phạm Văn Cường

Chia sẻ: Sdfcdxgvf Sdfcdxgvf | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

82
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Chiến lược tham lam - Phạm Văn Cường

Chiến lược tham lam (Greedy algorithms) Phạm Văn Cường http://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ệc S={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ệc
Bài toán lựa chọn công việc
Cấu trúc tối ưu • Sij={ak : fi
Lời giải đệ qui
Thuật toán tham lam đệ qui
Thuật toán tham lam lặp
Ví dụ