DAA - Phương pháp tham lam
Trong số tất cả các phương pháp tiếp cận theo thuật toán, cách tiếp cận đơn giản và dễ hiểu nhất là phương pháp Tham lam. Theo cách tiếp cận này, quyết định được đưa ra dựa trên thông tin hiện có sẵn mà không cần lo lắng về ảnh hưởng của quyết định hiện tại trong tương lai.
Các thuật toán tham lam xây dựng một giải pháp từng phần một, chọn phần tiếp theo theo cách sao cho nó mang lại lợi ích ngay lập tức. Cách tiếp cận này không bao giờ xem xét lại các lựa chọn đã thực hiện trước đó. Cách tiếp cận này chủ yếu được sử dụng để giải quyết các vấn đề tối ưu hóa. Phương pháp tham lam rất dễ thực hiện và khá hiệu quả trong hầu hết các trường hợp. Do đó, chúng ta có thể nói rằng thuật toán Tham lam là một mô hình thuật toán dựa trên heuristic tuân theo lựa chọn tối ưu cục bộ ở mỗi bước với hy vọng tìm ra giải pháp tối ưu toàn cục.
Trong nhiều bài toán, nó không tạo ra một giải pháp tối ưu mặc dù nó đưa ra một giải pháp gần đúng (gần tối ưu) trong một thời gian hợp lý.
Các thành phần của thuật toán tham lam
Thuật toán tham lam có năm thành phần sau:
A candidate set - Một giải pháp được tạo ra từ bộ này.
A selection function - Được sử dụng để chọn ứng viên tốt nhất được thêm vào giải pháp.
A feasibility function - Được sử dụng để xác định liệu một ứng viên có thể được sử dụng để đóng góp vào giải pháp hay không.
An objective function - Dùng để gán giá trị cho một giải pháp hoặc một giải pháp từng phần.
A solution function - Được sử dụng để cho biết liệu đã đạt được một giải pháp hoàn chỉnh hay chưa.
Lĩnh vực ứng dụng
Cách tiếp cận tham lam được sử dụng để giải quyết nhiều vấn đề, chẳng hạn như
Tìm đường đi ngắn nhất giữa hai đỉnh bằng thuật toán Dijkstra.
Tìm cây bao trùm tối thiểu trong biểu đồ bằng thuật toán của Prim / Kruskal, v.v.
Khi Phương pháp Tiếp cận Tham lam thất bại
Trong nhiều vấn đề, thuật toán Greedy không tìm được giải pháp tối ưu, hơn nữa nó có thể tạo ra giải pháp tồi tệ nhất. Các vấn đề như Người bán hàng đi du lịch và Knapsack không thể được giải quyết bằng cách sử dụng phương pháp này.