Lập trình

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 món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba… 

Thuật toán tham lam là thuật toán tối ưu hóa tổ hợp. Thuật toán tìm kiếm, lựa chọn giải pháp tối ưu địa phương ở mỗi bước đi với hy vọng tìm được giải pháp tối ưu toàn cục. Chẳng hạn áp dụng thuật toán tham lam với bài toán hành trình của người giao hàng: ở mỗi bước hãy đi đến thành phố gần thành phố hiện tại nhất.

Lựa chọn giải pháp nào được cho là tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ thuộc vào các lựa chọn trước đó. Nhưng nó không thể phụ thuộc vào một lựa chọn nào trong tương lai hay phụ thuộc vào lời giải của các bài toán con.

Thuật toán tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Đó là khác biệt giữa thuật toán này và quy hoạch động. Giải thuật quy hoạch động duyệt hết và luôn đảm bảo tìm thấy lời giải. Tại mỗi bước của thuật toán, quy hoạch động đưa ra quyết định dựa trên các quyết định của bước trước, và có thể xét lại đường đi của bước trước hướng tới lời giải. 

Giải thuật tham lam quyết định sớm và thay đổi đường đi thuật toán theo quyết định đó, và không bao giờ xét lại các quyết định cũ, vì vậy có thể là một thuật toán không tối ưu.

 

Các bài toán sử dụng thuật toán tham lam

1) Bài toán xếp lịch

2) Bài toán xếp ba lô

3) Bài toán trả tiền của máy rút tiền tự động ATM 

4) Bài toán tìm đường đi ngắn nhất

    Thuật toán tìm đường đi ngắn nhất Dijkstra

    http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

5) Thuật toán mã hóa dữ liệu Huffman coding

    http://en.wikipedia.org/wiki/Huffman_tree

6) Thuật toán tìm cây phủ tối thiểu 

    Kruskal’s algorithm

    http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

    Prim's algorithm

    http://en.wikipedia.org/wiki/Prim%27s_algorithm

 

Ví dụ: Bài toán xếp lịch

Giả sử bạn có n hoạt động S={1,2,…n} sử dụng một tài nguyên nào đó, mà mỗi lần chỉ một hoạt động sử dụng tài nguyên đó

Mỗi một hoạt động bao gồm :

Thời gian bắt đầu:Bi (i là chỉ số)

Thời gian kết thúc :Ei 

Với Bi <=Ei 

Yêu cầu: tìm tập hợp A có kích thước cực đại các hoạt động tương thích nhau mà không xung đột. A là tập hợp cần tìm (kết quả của bài toán) 

Bạn nên sắp xếp dữ liệu đầu vào hay nói cách khác là điều chỉnh dữ liệu đầu vào một cách hợp lý trước khi giải quyết bài toán. Dữ liệu vào của bài toán đã được sắp xếp trước theo thứ tự tăng dần của thời gian kết thúc

 

Thuật toán bài toán xếp lịch

Chạy 1 vòng lặp thực hiện việc:

Kiểm tra ở tập B nếu hoạt động nào có thời gian bắt đầu Bi không trùng hay đè lên thời gian kết thúc Ej của hoạt động đã được bổ sung vào A trước đó thì cho vào A (Bi >= Ej trước)

Ngược lại thì bỏ qua xét tiếp 

Vòng lặp dừng lại khi B rỗng 

 

Greedy-select (B,E)

{

n=length(B);

A=B[1];j=1;

for (i=2;i<=n;i++)

{ 

if ( B[i]>=E[j])

A=A+B[i];

  j=i;

}

return A;

}