Các thuật toán tham lam là một loại chiến lược thuật thuật toán mà tạo ra sự lựa chọn tối ưu tại mỗi bước với hy vọng tìm ra tối ưu toàn cầu. chúng được sử dụng rộng rãi để giải quyết các vấn đề tối ưu hóa nơi mà các quyết định địa phương dẫn đến một giải pháp tối ưu toàn cầu. bài này khám phá khái niệm của các thuật toán tham lam, cung cấp các ví dụ thực tế, và cho thấy làm thế nào để thực hiện các phép tính liên quan.

Thuật toán tham lam là gì?

Một thuật toán tham lam xây dựng một giải pháp bằng từng mảnh, luôn luôn chọn mảnh tiếp theo cung cấp lợi ích ngay lập tức. Cách tiếp cận này đơn giản và hiệu quả nhưng không luôn luôn đảm bảo giải pháp tổng thể tốt nhất cho mọi vấn đề. Nó có hiệu quả nhất khi vấn đề hiển thị các tính chất tham lam và cơ sở hạ tầng tối ưu.

Gương mẫu thực tiễn

Những ví dụ này cho thấy làm thế nào để có những lựa chọn tối ưu địa phương có thể dẫn đến một giải pháp tối ưu toàn cầu trong những tình huống cụ thể.

Tính toán và giải phẫu

Hãy xem xét vấn đề thay đổi đồng xu nơi mục tiêu là thay đổi một số tiền nhất định bằng số tiền ít nhất, giả sử các giáo phái tiền bạc là 1, 5, 10, và 25 xu, và số tiền đó là 63 xu.

Tính toán từng bước một:

  • Chọn 25 xu (còn lại: 63 - 25 = 38)
  • Chọn 25 xu (còn lại: 38 - 25 = 13)
  • Chọn 10 xu (còn lại: 13 - 10 = 3)
  • Chọn 1 xu (còn lại: 3 - 1 = 2)
  • Chọn 1 xu (còn lại: 2 - 1 = 1)
  • Chọn 1 xu (còn lại: 1 - 1 = 0)

Tổng số tiền được dùng: 6.