Thuật Toán Tham Lam (Greedy Algorithms) (phần 1)

Gọi là thuật toán tham lam nham nhưng thực chất tham lam không được gọi là thuật toán, mà nó là một kỹ thuật, một phương pháp để ta tiến hành giải một bài toán lập trình.

Vậy thì thuật toán tham lam là gì?

Một thuật toán tham lam, như tên gọi cua nó, đó là luôn luôn làm một sự lựa chọn tốt nhất tại thời điểm hiện tại. Điều này có nghĩa rằng, sự lựa chọn tốt nhất ở mỗi bước sẽ dẫn tới lời giải tối ưu nhất

Vậy bạn chọn lựa tối ưu hóa bằng cách nào?

Giả sử bạn có một hàm cần để tối ưu hóa (hoặc cực đại hóa, hoặc cực tiểu hóa hàm đó). Một thuật toán tham lam sẽ thực hiện các lựa chọn tham lam ở mỗi bước để đảm bảo rằng hàm đã cho là tối ưu. Thuật toán tham lam chỉ có một lần tính toán lời giải tối ưu với mục đích nó không bao giờ trở lại và đảo ngược quyết định.

Thuật toán tham lam có một vài sự thuận lợi và không thuận lợi:

1.  Khá dễ để tiến hành một thuật toán tham lam cho một bài toán
2.  Phân tích thời gian chạy của thuật toán tham lam sẽ dễ dàng hơn kỹ thuật khác (như Chia để trị). Với kỹ thuật chia để trị, không rõ ràng liệu kỹ thuật này là nhanh hay chậm. Lý do là ở mỗi mức của đệ quy kích thước nhỏ hơn và số lượng của bài toán con lớn hơn.
3. Khó khăn của tham lam là bạn rất vất vả để hiểu chính xác vấn đề. Thậm chí với giải thuật chính xác rồi, cũng rất khó khăn để chứng minh tại sao nó đúng. Chứng minh một giải thuật tham lam là đúng có cảm giác là cả một nghệ thuật hơn là một khoa học, vì nó đòi hỏi rất nhiều sự sáng tạo

Lưu ý: Hầu như các giải thuật tham lam đều không chính xác. Một ví dụ sẽ được mô tả trong bài báo sau đây.

C. Tạo ra một Giải thuật tham lam như thế nào?

Bài toán: Là một  người bận rộn, bạn có đúng T thời gian để làm một vài thứ thú vị và bạn muốn làm nhiều thứ nhất có thể.

Cho một mảng A gồm các số có kiểu int, trong đó mỗi phần tử biểu thị thời gian hoàn thiện thứ đó. Hãy tính toán số thứ bạn có thể làm với thời gian giới hạn

Đây là một bài toán tham lam đơn giản. Ở mỗi bước, ta phải chọn lựa tham lam bằng cách chọn các công việc có thời gian hoàn thành ít nhất. ở  đây ta có hai biến là thời gian hiện tại (currentTime) và số công việc (numberofThings). Để hàm thành, ta phải:

1. Sắp xếp mảng A theo chiều không giảm
2. Chọn lựa mỗi công việc để làm
3. Cộng thời gian để hoàn thành vào biến currungtime
4. Công một tới số lượng công việc

Lặp lại điều này trong khi biến currenttimem nhỏ hơn hoặc bằng T

#include #include using namespace std; const int MAX = 105; int A[MAX]; int main() { int T, N, numberOfThings = 0, currentTime = 0; cin >> N >> T; for(int i = 0;i > A[i]; sort(A, A + N); for(int i = 0;i T) break; numberOfThings++; } cout << numberOfThings << endl; return 0; }

Chia sẻ:

• X
• Facebook

Thích Đang tải...