Nói chung, giải thuật tham lam có năm thành phần:
- Một tập hợp các ứng viên (candidate), để từ đó tạo ra lời giải
- Một hàm lựa chọn, để theo đó lựa chọn ứng viên tốt nhất để bổ sung vào lời giải
- Một hàm khả thi (feasibility), dùng để quyết định nếu một ứng viên có thể được dùng để xây dựng lời giải
- Một hàm mục tiêu, ấn định giá trị của lời giải hoặc một lời giải chưa hoàn chỉnh
- Một hàm đánh giá, chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
- Tính chất lựa chọn tham lam
- Cấu trúc con tối ưu
Áp dụng
Đối với nhiều bài toán, giải thuật tham lam hầu như không cho ra lời giải tối ưu toàn cục (nhưng không phải luôn như vậy), vì chúng thường không chạy trên tất cả các trường hợp. Chúng có thể bám chặt lấy một số lựa chọn nhất định một cách quá sớm, điều này dẫn đến hậu quả là trong giai đoạn sau, các thuật toán này không thể tìm ra các lời giải toàn cục tốt nhất. Ví dụ, đối với bài toán tô màu đồ thị và tất cả các bài toán NP-đầy đủ khác, không một thuật toán tham lam đã được biết nào đảm bảo tìm thấy các lời giải tối ưu. Tuy nhiên, các thuật toán này vẫn hữu ích vì chúng dễ thiết kế và cho ra các ước lượng tốt về lời giải tối ưu.Nếu có thể chứng minh rằng một thuật toán tham lam cho ra kết quả tối ưu toàn cục cho một lớp bài toán nào đó, thì thuật toán thường sẽ trở thành phương pháp được chọn lựa, vì nó chạy nhanh hơn các phương pháp tối ưu hóa khác như quy hoạch động. Các ví dụ cho giải thuật loại này là thuật toán Kruskal và thuật toán Prim dành cho bài toán cây bao trùm nhỏ nhất, thuật toán Dijkstra dành cho bài toán đường đi ngắn nhất nguồn đơn, và thuật toán tìm cây Huffman tối ưu.
Tham khảo
- Introduction to Algorithms (Cormen, Leiserson, and Rivest) 1990, Chapter 16 "Greedy Algorithms" p. 329.
No comments:
Post a Comment