Buzz
Thuật toán tham lam (tiếng Anh: Greedy algorithm) là một phương pháp giải quyết bài toán theo kiểu metaheuristic, tập trung vào việc chọn lựa giải pháp tối ưu nhất tại mỗi bước với hi vọng đạt được giải pháp tốt nhất toàn cục. Ví dụ, với bài toán người bán hàng, giải thuật tham lam có thể được mô tả là: 'Tại mỗi bước, chọn thành phố gần nhất với thành phố hiện tại.'
Nói chung, thuật toán tham lam bao gồm năm yếu tố chính:
- 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, dùng để chọn ứng viên tốt nhất để thêm vào lời giải
- Một hàm khả thi (feasibility
), dùng để kiểm tra nếu một ứng viên có thể được sử dụng để xây dựng lời giải
- Một hàm mục tiêu, xác định giá trị của lời giải hoặc giá trị của một lời giải chưa hoàn chỉnh
- Một hàm đánh giá, cho biết khi nào một lời giải hoàn chỉnh đã được tìm thấy.
Có hai yếu tố chính ảnh hưởng đến quyết định tham lam:
- Đặc điểm của lựa chọn tham lam
Ta có thể chọn giải pháp tối ưu nhất tại thời điểm hiện tại và tiếp tục giải quyết bài toán con phát sinh từ quyết định đó. Quyết định của thuật toán tham lam có thể bị ảnh hưởng bởi các lựa chọn trước đó, nhưng không phụ thuộc vào các lựa chọn trong tương lai hay các bài toán con. Thuật toán này hoạt động theo cách lặp đi lặp lại các quyết định, đồng thời thu nhỏ bài toán gốc thành các bài toán con nhỏ hơn. Đây là điểm khác biệt chính giữa thuật toán tham lam và quy hoạch động. Trong khi quy hoạch động luôn duyệt qua tất cả các khả năng và đảm bảo tìm ra lời giải tốt nhất, thuật toán tham lam quyết định sớm và không xem xét lại các quyết định trước đó. Đối với một số bài toán, phương pháp này có thể không đạt được kết quả chính xác.
- Cấu trúc tối ưu của bài toán con
Một bài toán được gọi là có 'cấu trúc tối ưu' nếu lời giải tốt nhất của bài toán con là một phần của lời giải tốt nhất của bài toán gốc.
Ứng dụng
Trong nhiều trường hợp, thuật toán tham lam thường không đạt được lời giải tối ưu toàn cục (dù không phải lúc nào cũng vậy), vì chúng không xem xét tất cả các khả năng. Thuật toán có thể chọn lựa quá sớm một số lựa chọn nhất định, dẫn đến việc không thể tìm ra giải pháp toàn cục tốt nhất ở giai đoạn sau. Ví dụ, với bài toán tô màu đồ thị và các bài toán NP-đầy đủ khác, không có thuật toán tham lam nào được biết đến đảm bảo tìm ra lời giải tối ưu. Tuy nhiên, những thuật toán này vẫn có giá trị vì chúng dễ thiết kế và cung cấp ước lượng tốt về giải pháp tối ưu.
Khi có thể chứng minh rằng một thuật toán tham lam luôn cung cấp kết quả tối ưu toàn cục cho một loại bài toán cụ thể, thuật toán đó thường được ưa chuộng vì tốc độ thực thi nhanh hơn so với các phương pháp tối ưu hóa khác như quy hoạch động. Một số ví dụ bao gồm thuật toán Kruskal và thuật toán Prim cho bài toán cây bao trùm nhỏ nhất, thuật toán Dijkstra cho bài toán đường đi ngắn nhất từ nguồn đơn, và thuật toán xây dựng cây Huffman tối ưu.
- Giới thiệu về Thuật toán (Cormen, Leiserson, và Rivest) 1990, Chương 16 'Thuật toán Tham lam' trang 329
