Chiến lược tham lam (Greedy algorithms)

Chiến lược tham lam (Greedy algorithms) Phạm Văn Cường 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. 0<=si<fi. Nếu được chọn ai, ai cần khoảng thời gian [si,fi) để thực hiện. Hai công việc ai và aj gọi là tương thích (compatible) nếu [si,fi) và [sj,fj) không giao nhau (si>fj or sj>fi) 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<=sk<fk<=sj} là tập công việc con chứa nhiều công việc nhất sau khi ai hoàn thành và trước khi aj bắt đầu • Nếu i>=j thì Sij= • Sij = Sik U{ak} USkj  Lời giải đệ qui Thuật toán tham lam đệ qui Thuật toán tham lam lặp Ví dụ