intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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

83
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ủ đề:
Lưu

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

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

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
3=>0