Hướng dẫn Thuật Toán Tham Lam (Greedy Algorithm) và ví dụ bằng PHP

Thuật toán tham lam (Greedy Algorithm) là một phương pháp giải quyết vấn đề bằng cách đưa ra các lựa chọn tối ưu nhất ở từng bước mà không cần quan tâm đến các bước tiếp theo. Đây là một kỹ thuật hữu ích cho các bài toán tối ưu hóa, nơi mà bạn muốn tìm một lời giải tốt nhất (tối đa hoặc tối thiểu) trong một tập hợp các lựa chọn.

1. Nguyên lý hoạt động của thuật toán tham lam

Nguyên lý chính của thuật toán tham lam là:

• Chọn lựa cục bộ tối ưu tại mỗi bước: Ở mỗi bước, bạn chọn lựa giải pháp tối ưu cục bộ mà không cần quan tâm đến tương lai.
• Tính chất của bài toán: Không phải tất cả các bài toán đều có thể giải quyết bằng thuật toán tham lam. Bài toán cần thỏa mãn tính chất "con suốt tối ưu" (Optimal Substructure) và "lựa chọn tham lam" (Greedy Choice Property).

Ví dụ điển hình: Bài toán chọn đồng xu có mệnh giá nhỏ nhất để trả tiền thối.

2. Các bước giải bài toán bằng thuật toán tham lam

1. Bước khởi tạo: Tìm ra lựa chọn tối ưu ở bước đầu tiên.
2. Lặp lại: Ở mỗi bước tiếp theo, chọn lựa một giải pháp tốt nhất trong số các lựa chọn hiện có.
3. Kết thúc: Khi đạt được kết quả mong muốn hoặc không còn giải pháp nào nữa.

3. Ví dụ cơ bản: Bài toán trả tiền bằng số lượng đồng xu ít nhất

Giả sử bạn có các đồng xu mệnh giá 1, 2, 5 và 10, và bạn cần trả số tiền là 28. Nhiệm vụ của bạn là sử dụng số lượng đồng xu ít nhất.

Giải pháp bằng thuật toán tham lam:

Ở mỗi bước, bạn sẽ chọn đồng xu có mệnh giá lớn nhất mà vẫn nhỏ hơn hoặc bằng số tiền còn lại.

Mã PHP:

while

4. Ví dụ mở rộng: Bài toán lập lịch công việc với thời gian kết thúc sớm nhất

Giả sử bạn có nhiều công việc với thời gian bắt đầu và kết thúc khác nhau. Nhiệm vụ của bạn là tìm số lượng công việc lớn nhất có thể thực hiện mà không trùng lặp thời gian.

Đầu vào:

• Mảng các công việc, mỗi công việc có thời gian bắt đầu và kết thúc.

Giải pháp:

Thuật toán tham lam sẽ chọn công việc có thời gian kết thúc sớm nhất, sau đó lặp lại quá trình này cho các công việc còn lại không trùng lặp với công việc đã chọn.

Mã PHP:

W

Giải thích mã:

• Danh sách đồ vật: Mỗi đồ vật được biểu diễn dưới dạng một mảng chứa trọng lượng và giá trị.
• Sắp xếp: Hàm usort() sắp xếp các đồ vật theo tỷ lệ value/weight giảm dần.
• Lựa chọn đồ vật: Mỗi lần kiểm tra xem túi còn sức chứa không, nếu có thể chọn toàn bộ một đồ vật, nó sẽ được thêm vào túi. Nếu không, chỉ một phần của đồ vật sẽ được chọn để lấp đầy túi.

Kết quả:

Giá trị lớn nhất có thể lấy được: 240
Danh sách đồ vật được chọn:
Đồ vật có trọng lượng 10 và giá trị 60 được chọn 100%.
Đồ vật có trọng lượng 20 và giá trị 100 được chọn 100%.
Đồ vật có trọng lượng 30 và giá trị 120 được chọn 33.333333333333%.

Phân tích:

Trong ví dụ này:

• Túi có sức chứa là 50.
• Thuật toán chọn toàn bộ hai đồ vật đầu tiên (10kg và 20kg) vì túi vẫn còn đủ chỗ.
• Sau đó, chỉ chọn một phần của đồ vật thứ ba (33.33% của đồ vật nặng 30kg) để lấp đầy túi.

Ứng dụng thực tế:

Bài toán "Cái túi dạng phân số" thường được sử dụng trong các tình huống thực tế như:

• Vấn đề lưu trữ dữ liệu: Tối ưu hóa không gian lưu trữ bằng cách chọn các tệp tin có giá trị cao nhất trước.
• Vấn đề đầu tư: Đầu tư vào các dự án hoặc cổ phiếu có lợi nhuận cao nhất trước khi hết ngân sách.
• Vấn đề vận tải: Tối ưu hóa lượng hàng hóa vận chuyển trong các xe tải có trọng tải giới hạn.

Thuật toán tham lam rất mạnh mẽ khi giải quyết các bài toán tối ưu hóa, đặc biệt là khi các bài toán có thể chia nhỏ thành các phần con độc lập. Bài toán "Cái túi dạng phân số" là một ví dụ điển hình về cách thuật toán tham lam có thể giúp đưa ra giải pháp tối ưu bằng cách đưa ra quyết định tốt nhất tại mỗi bước.

• Algorithm
• PHP