Cấu trúc dữ liệu - Thuật toán tham lam

Một thuật toán được thiết kế để đạt được giải pháp tối ưu cho một vấn đề nhất định. Trong cách tiếp cận thuật toán tham lam, các quyết định được đưa ra từ miền giải pháp đã cho. Vì tham lam, giải pháp gần nhất có vẻ cung cấp một giải pháp tối ưu đã được chọn.

Các thuật toán tham lam cố gắng tìm một giải pháp tối ưu được bản địa hóa, điều này cuối cùng có thể dẫn đến các giải pháp được tối ưu hóa toàn cầu. Tuy nhiên, các thuật toán tham lam nói chung không cung cấp các giải pháp tối ưu hóa toàn cầu.

Đếm xu

Vấn đề này là đếm đến một giá trị mong muốn bằng cách chọn những đồng xu ít nhất có thể và cách tiếp cận tham lam buộc thuật toán phải chọn đồng xu lớn nhất có thể. Nếu chúng tôi được cung cấp các đồng 1, 2, 5 và 10 và chúng tôi được yêu cầu đếm ₹ 18 thì thủ tục tham lam sẽ là -

1 - Chọn một đồng ₹ 10, số còn lại là 8
2 - Sau đó chọn một đồng ₹ 5, số còn lại là 3
3 - Sau đó chọn một ₹ 2 xu, số còn lại là 1
4 - Và cuối cùng, việc chọn một đồng ₹ 1 giải quyết được vấn đề

Mặc dù, nó có vẻ hoạt động tốt, với số lượng này, chúng tôi chỉ cần chọn 4 đồng xu. Nhưng nếu chúng ta thay đổi một chút vấn đề thì cách tiếp cận tương tự có thể không thể tạo ra cùng một kết quả tối ưu.

Đối với hệ thống tiền tệ, nơi chúng ta có các đồng tiền có giá trị 1, 7, 10, đếm tiền cho giá trị 18 sẽ hoàn toàn tối ưu nhưng đối với số đếm như 15, nó có thể sử dụng nhiều đồng hơn mức cần thiết. Ví dụ, cách tiếp cận tham lam sẽ sử dụng 10 + 1 + 1 + 1 + 1 + 1, tổng cộng 6 xu. Trong khi vấn đề tương tự có thể được giải quyết bằng cách chỉ sử dụng 3 xu (7 + 7 + 1)

Do đó, chúng tôi có thể kết luận rằng cách tiếp cận tham lam chọn một giải pháp tối ưu hóa ngay lập tức và có thể thất bại khi tối ưu hóa toàn cầu là mối quan tâm lớn.

Ví dụ

Hầu hết các thuật toán mạng sử dụng cách tiếp cận tham lam. Đây là danh sách một vài trong số họ -

Vấn đề nhân viên bán hàng đi du lịch
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
Biểu đồ - Tô màu bản đồ
Đồ thị - Bìa đỉnh
Vấn đề về Knapsack
Vấn đề lên lịch công việc

Có rất nhiều vấn đề tương tự sử dụng phương pháp tham lam để tìm ra giải pháp tối ưu.