Cộng đồng chia sẻ tri thức Lib24.vn

Thuật toán tham lam

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 9:39:38


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. Theo 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 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ục bộ, cuối cùng có thể dẫn đến các giải pháp tối ưu hóa toàn cầu. Tuy nhiên, nhìn chung các thuật toán tham lam không cung cấp các giải pháp tối ưu hóa toàn cầu.

Đếm tiền

Vấn đề này là tính đến một giá trị mong muốn bằng cách chọn những đồng tiền í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 tiền lớn nhất có thể. Nếu chúng tôi được cung cấp các đồng xu 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. 1 - Chọn một đồng 10 đô la, số còn lại là 8
  2. 2 - Sau đó chọn một đồng 5 đô la, số còn lại là 3
  3. 3 - Sau đó chọn một đồng 2 đô la, số còn lại là 1
  4. 4 - Và cuối cùng, việc lựa chọn một đồng 1 đô la giải quyết vấn đề

Mặc dù, nó có vẻ hoạt động tốt, nhưng trong số 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 kết quả tối ưu tương tự.

Đối với hệ thống tiền tệ, nơi chúng tôi có các đồng tiền có giá trị 1, 7, 10, việc đếm các đồng xu cho giá trị 18 sẽ hoàn toàn tối ưu nhưng đối với số lượng như 15, nó có thể sử dụng nhiều tiền 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 đồng tiền. Trong khi đó, vấn đề tương tự có thể được giải quyết bằng cách chỉ sử dụng 3 đồng tiền (7 + 7 + 1)

Do đó, chúng tôi có thể kết luận rằng phương pháp 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 trong đó tối ưu hóa toàn cầu là mối quan tâm chính.

Ví dụ

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

  1. Vấn đề nhân viên bán hàng du lịch
  2. Thuật toán cây kéo dài tối thiểu của Prim
  3. Thuật toán cây kéo dài tối thiểu của Kruskal
  4. Thuật toán cây kéo dài tối thiểu của Dijkstra
  5. Đồ thị - Tô màu bản đồ
  6. Đồ thị - Vỏ Vertex
  7. Vấn đề về chiếc ba lô
  8. Vấn đề lập kế hoạ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


Được cập nhật: hôm qua lúc 8:17:33 | Lượt xem: 1000

Các bài học liên quan