Thuật toán tham lam là gì: cách hoạt động, code và ví dụ

Thuật toán tham lam giải bài toán gì

Thuật toán tham lam nhắm tới các bài toán tối ưu: chọn được nhiều hoạt động nhất, dùng ít đồng xu nhất, xây mạng rẻ nhất, nén tệp thành ít bit nhất. Thay vì duyệt mọi tổ hợp, thuật toán tham lam sắp xếp hoặc ưu tiên các phương án và chốt phương án tốt nhất ở mỗi bước. Điều đó thường cho thời gian O(n log n), thường chỉ là chi phí sắp xếp.

Phần khó không nằm ở code mà ở chứng minh. Nhiều quy tắc tham lam tự nhiên là sai, nên bạn phải chứng minh quy tắc đúng hoặc kiểm thử nó với lời giải vét cạn.

Ý tưởng bằng lời đơn giản

1. Tìm một quy tắc xếp hạng các lựa chọn, ví dụ “kết thúc sớm nhất trước” hoặc “cạnh nhẹ nhất trước”.
2. Sắp xếp các phương án theo quy tắc đó, hoặc giữ chúng trong hàng đợi ưu tiên.
3. Duyệt qua các phương án và lấy từng phương án vẫn được ràng buộc cho phép.
4. Không bao giờ hoàn tác một lựa chọn.

Thuật toán tham lam đúng khi hai tính chất sau cùng thỏa. Tính chất lựa chọn tham lam: có một lời giải tối ưu chứa lựa chọn tham lam đầu tiên. Cấu trúc con tối ưu: sau khi đưa ra lựa chọn đó, phần còn lại của bài toán là một bản nhỏ hơn của cùng bài toán. Cách chứng minh thường dùng là lập luận hoán đổi (exchange argument): lấy một lời giải tối ưu bất kỳ và chỉ ra rằng đổi một lựa chọn của nó sang lựa chọn tham lam không làm nó tệ đi.

Ví dụ: lập lịch khoảng thời gian

Bạn có một phòng họp và các yêu cầu sau (bắt đầu, kết thúc): A (1, 4), B (3, 5), C (0, 6), D (5, 7), E (3, 9), F (5, 9), G (6, 10), H (8, 11). Hãy đặt được nhiều cuộc họp không chồng nhau nhất có thể. Quy tắc tham lam đúng là: luôn chọn cuộc họp kết thúc sớm nhất trong số những cuộc bắt đầu sau khi cuộc họp đã đặt gần nhất kết thúc.

Kết quả: A, D, H, ba cuộc họp, là mức tối đa. Vì sao đúng: cuộc họp kết thúc sớm nhất để lại nhiều thời gian nhất cho mọi việc khác, nên thay cuộc họp đầu tiên của bất kỳ lịch tối ưu nào bằng nó không bao giờ gây xung đột.

Cài đặt bằng Python

def max_meetings(meetings):
    """meetings: list of (name, start, end). Returns the booked names."""
    booked, last_end = [], float("-inf")
    for name, start, end in sorted(meetings, key=lambda m: m[2]):
        if start >= last_end:
            booked.append(name)
            last_end = end
    return booked

requests = [("A", 1, 4), ("B", 3, 5), ("C", 0, 6), ("D", 5, 7),
            ("E", 3, 9), ("F", 5, 9), ("G", 6, 10), ("H", 8, 11)]
print(max_meetings(requests))  # ['A', 'D', 'H']

Một ví dụ kinh điển thứ hai là bài toán cái túi phân số (fractional knapsack): khi bạn được lấy một phần của vật, lấy các vật theo thứ tự giá trị trên mỗi đơn vị khối lượng là tối ưu.

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns the best total value."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * take / weight
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))  # 240.0

Khi tham lam thất bại: các phản ví dụ

Độ phức tạp thời gian và không gian

Không gian thường là O(n) cho bản sao đã sắp xếp hoặc heap. Nếu đầu vào đã được sắp xếp, nhiều thuật toán tham lam chạy trong O(n).

Khi nào dùng tham lam và ứng dụng thực tế

• Dùng tham lam khi bạn chứng minh được tính chất lựa chọn tham lam, hoặc khi chấp nhận đáp án xấp xỉ nhanh. Nếu không, hãy dùng quy hoạch động hoặc quay lui.
• Nén dữ liệu: mã hóa Huffman xây các mã tiền tố tối ưu bằng cách liên tục gộp hai ký hiệu ít xuất hiện nhất; nó được dùng trong các định dạng như DEFLATE (ZIP, gzip, PNG).
• Mạng: cây khung nhỏ nhất (Kruskal, Prim) và định tuyến đường đi ngắn nhất (Dijkstra).
• Lập lịch: hạn chót sớm nhất trước (earliest deadline first), và đặt phòng hoặc máy.
• Xấp xỉ: với bài toán phủ tập hợp (set cover), quy tắc tham lam “chọn tập phủ nhiều phần tử chưa được phủ nhất” không tối ưu nhưng đảm bảo nằm trong hệ số logarit của tối ưu.
• Bài phỏng vấn: jump game, gas station, assign cookies, non-overlapping intervals, minimum number of arrows to burst balloons, task scheduler.