Greedy algorithm (Kĩ thuật tham lam)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

 

1. Bài toán tối ưu tổ hợp:

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X thuộc D có dạng X = (x1, x2,…xn) được gọi là một phương án.
  • Cần tìm một phương án X thuộc D sao cho hàm  f(X) đạt min (max). Phương án X như vậy gọi là tối ưu.

Ta có thể tìm thấy phương án tối ưu bằng “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để tìm phương án tốt nhất. Mặc dù tập D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng vét cạn ta có thể cần một thời gian hàm mũ.

2. Nội dung kĩ thuật tham lam (tham ăn):

Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang ăn món ngon thứ hai, lại ăn hết món ngon thứ hai và chuyển sang món ngon thứ 3..

Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp bẳng cách xây dựng một phương án X. Phương án X này được xây dựng bằng cách lựa chọn từng thành phần  Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta sẽ phải chấp nhận giá trị cuối cùng còn lại.

Áp dụng kĩ thuật tham lam sẽ cho ta một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.

Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này.

Các bài toán ví dụ: Các bạn tìm hiểu các bài toán như: “Bài toán trả tiền của máy rút tiền tự động ATM”, “Bài toán cái balô”, “Bài toán đường đi của người giao hàng”, …

Advertisements