Trong hướng dẫn này, bạn sẽ tìm hiểu Thuật toán tham lam là gì. Ngoài ra, bạn sẽ tìm thấy một ví dụ về cách tiếp cận tham lam.
Thuật toán tham lam là một cách tiếp cận để giải quyết vấn đề bằng cách chọn phương án tốt nhất hiện có mà không cần lo lắng về kết quả tương lai mà nó sẽ mang lại. Nói cách khác, các lựa chọn tốt nhất tại địa phương nhằm mục đích tạo ra kết quả tốt nhất trên toàn cầu.
Thuật toán này có thể không phải là lựa chọn tốt nhất cho tất cả các vấn đề. Nó có thể tạo ra kết quả sai trong một số trường hợp.
Thuật toán này không bao giờ quay trở lại để đảo ngược quyết định đã đưa ra. Thuật toán này hoạt động theo cách tiếp cận từ trên xuống.
Ưu điểm chính của thuật toán này là:
- Thuật toán dễ mô tả hơn .
- Thuật toán này có thể hoạt động tốt hơn các thuật toán khác (nhưng không phải trong mọi trường hợp).
Giải pháp mang tính khả thi
Giải pháp khả thi là giải pháp cung cấp giải pháp tối ưu cho vấn đề.
Thuật toán tham lam
- Để bắt đầu, tập giải pháp (chứa các câu trả lời) là trống.
- Ở mỗi bước, một mục được thêm vào bộ giải pháp.
- Nếu bộ giải pháp khả thi, mục hiện tại được giữ lại.
- Mặt khác, mặt hàng bị từ chối và không bao giờ được xem xét lại.
Ví dụ - Cách tiếp cận Tham lam
Vấn đề: Bạn phải thực hiện thay đổi một số tiền bằng cách sử dụng số lượng xu nhỏ nhất có thể. Số tiền: $ 28 Xu hiện có: $ 5 xu $ 2 xu $ 1 xu
Giải pháp:
- Tạo một tập nghiệm trống = ().
- xu = (5, 2, 1)
- sum = 0
- Trong khi tổng ≠ 28, hãy làm như sau.
- Chọn một đồng xu C từ các đồng xu sao cho tổng + C <28.
- Nếu C + sum> 28, không trả về nghiệm.
- Khác, sum = sum + C.
- Thêm C vào tập giải pháp.
Tối đa 5 lần lặp đầu tiên, bộ giải pháp chứa 5 đồng $ 5. Sau đó, chúng ta nhận được 1 đồng 2 đô la và cuối cùng là 1 đồng 1 đô la.
Ứng dụng thuật toán tham lam
- Sắp xếp lựa chọn
- Vấn đề về Knapsack
- Cây kéo dài tối thiểu
- Vấn đề đường dẫn ngắn nhất nguồn đơn
- Vấn đề lên lịch công việc
- Thuật toán cây kéo dài tối thiểu của Prim
- Thuật toán cây kéo dài tối thiểu của Kruskal
- Thuật toán cây kéo dài tối thiểu của Dijkstra
- Mã hóa Huffman
- Thuật toán Ford-Fulkerson
