Greedy — Tham lam có chứng minh: Interval Scheduling và Huffman

TL;DR: Greedy algorithm xây dựng nghiệm bằng cách chọn lựa chọn cục bộ tốt nhất (locally optimal) tại mỗi bước, không bao giờ quay lui. Greedy đúng khi bài toán có hai tính chất: greedy choice property (lựa chọn tham lam không chặn nghiệm tối ưu) và optimal substructure (tối ưu toàn cục chứa tối ưu subproblem). Chứng minh bằng exchange argument: giả sử OPT khác greedy, hoán đổi một phần tử → OPT không tệ hơn → mâu thuẫn. Greedy SAI khi thiếu một trong hai tính chất — 0/1 knapsack và coin change với mệnh giá lạ là counter-example kinh điển.

Năm 2003, nhóm kỹ thuật tại Google gặp vấn đề: log file gzip của họ tốn 40% dung lượng hơn dự kiến. Sau khi kiểm tra, họ phát hiện Huffman coding — trái tim của gzip — đang không tối ưu vì frequency table bị tính sai. Huffman coding là thuật toán greedy thuần túy: mỗi bước chọn hai node có frequency nhỏ nhất để gộp. Không cần DP, không cần backtrack, chỉ cần một min-heap và lòng tin rằng lựa chọn tham lam tại mỗi bước dẫn đến tree tối ưu toàn cục. Nhưng lòng tin đó cần được chứng minh.

1. Analogy — Người trả tiền thừa vs người đầu bếp tối ưu

Greedy là người trả tiền thừa hạnh phúc: khi trả 43.000đ bằng tờ lớn nhất có thể (20k + 20k + 2k + 1k), anh ta không bao giờ đổi ý. Với hệ mệnh giá Việt Nam (1k, 2k, 5k, 10k, 20k, 50k, 100k), cách này luôn cho số đồng xu ít nhất. Tính chất này — hệ mệnh giá canonical — là greedy choice property.

Khi greedy thất bại: đất nước khác có mệnh giá {1, 3, 4}, cần trả 6. Greedy: 4 + 1 + 1 = 3 đồng. Tối ưu: 3 + 3 = 2 đồng. Greedy chọn 4 (lớn nhất không vượt 6) nhưng 4 "phá vỡ" kết hợp tốt hơn.

2. Hai tính chất bắt buộc

2.1 Greedy Choice Property

Định nghĩa: lựa chọn tham lam tại bước đầu tiên (cục bộ tốt nhất) luôn là thành phần của ít nhất một nghiệm tối ưu toàn cục.

Đây là tính chất không tầm thường. Nó không nói lựa chọn tham lam tốt nhất — nó nói lựa chọn tham lam không loại bỏ khả năng đạt tối ưu. Nếu tính chất này sai, greedy có thể "đi vào ngõ cụt" không thể hồi phục.

2.2 Optimal Substructure

Định nghĩa: nghiệm tối ưu của bài toán lớn chứa nghiệm tối ưu của subproblem còn lại sau khi đã thực hiện lựa chọn tham lam.

Cũng là tính chất của DP. Nhưng trong DP, bạn cần xét tất cả lựa chọn và lấy tối ưu. Trong greedy, bạn chỉ cần xét lựa chọn tham lam duy nhất — và chứng minh nó đủ.

3. Exchange Argument — Phương pháp chứng minh

Exchange argument là kỹ thuật chứng minh greedy choice property. Template:

1. Giả sử tồn tại nghiệm tối ưu OPT không theo lựa chọn tham lam.
2. Tìm sự khác biệt đầu tiên giữa OPT và nghiệm greedy — bước nào OPT không chọn như greedy.
3. Hoán đổi (exchange) phần tử OPT tại bước đó thành lựa chọn của greedy.
4. Chứng minh sau hoán đổi, nghiệm mới không tệ hơn OPT (objective không giảm hoặc không tăng).
5. Kết luận: bằng cách hoán đổi từng bước một, OPT có thể biến thành nghiệm greedy mà không tệ hơn → greedy tối ưu.

Ta áp dụng kỹ thuật này cho Interval Scheduling bên dưới.

Thử ngẫmbước 4 của exchange argument chỉ chứng minh nghiệm mới "không tệ hơn" OPT, không phải "tốt hơn". Kết luận ở bước 5, rằng greedy tối ưu, có còn đứng vững với mức chứng minh yếu hơn đó không?

4. Interval Scheduling — Chọn theo Finish Time

4.1 Bài toán

Cho n hoạt động, mỗi hoạt động i có [start[i], finish[i]). Một phòng họp chỉ có thể tổ chức một hoạt động tại một thời điểm (hai hoạt động không được chồng lấn). Tìm tập con nhiều hoạt động nhất có thể được tổ chức.

Sáu hoạt động cụ thể để chạy thử: A từ 0 đến 6, B từ 1 đến 4, C từ 3 đến 5, D từ 4 đến 7, E từ 5 đến 9, F từ 6 đến 10.

4.2 Greedy: chọn theo finish time sớm nhất

IntervalScheduling(activities[]):
    Sắp xếp activities theo finish time tăng dần
    -- O(n log n)

    selected <- []
    last_finish <- 0    -- thời điểm kết thúc của hoạt động được chọn gần nhất

    for each activity a trong activities (đã sort):
        if a.start >= last_finish:    -- không chồng lấn
            selected.append(a)
            last_finish <- a.finish

    return selected

Time: O(n log n)  Space: O(n)

4.3 Trace ví dụ

Sau khi sort theo finish time: B[1-4], C[3-5], A[0-6], D[4-7], E[5-9], F[6-10].

Kết quả: chọn B và D — 2 hoạt động. (Đây là tối ưu: không thể chọn 3 hoạt động không chồng lấn từ 6 hoạt động này.)

Bảng trace kể được kết quả nhưng không kể được lý do, vì lý do là một chuyện hình học. Đặt sáu hoạt động lên đúng trục thời gian thì A tự tố cáo mình: A bắt đầu sớm nhất, nên tiêu chí "start time sớm nhất" sẽ vớ ngay nó — và mất luôn cả C lẫn D, vì A kéo tới t = 6 và một mình nuốt quá nửa trục. B kết thúc ở t = 4, chừa lại nguyên đoạn 4 đến 10. Đó là toàn bộ nội dung của exchange argument bên dưới, phát biểu bằng hình: finish sớm nhất là tiêu chí chiếm ít tương lai nhất.

4.4 Chứng minh bằng Exchange Argument

Claim: Greedy (sort theo finish time) cho số hoạt động tối đa.

Proof:

• Gọi nghiệm greedy là G = {g₁, g₂, ..., gₖ} (sắp xếp theo finish time).
• Gọi nghiệm tối ưu là OPT = {o₁, o₂, ..., oₘ} (sắp xếp theo finish time).
• Ta chứng minh k = m (greedy chọn không ít hơn OPT).

Lemma: với mọi j ≤ min(k,m), ta có finish(gⱼ) ≤ finish(oⱼ).

Chứng minh lemma bằng induction:

• j = 1: greedy chọn g₁ là hoạt động finish sớm nhất trong tất cả → finish(g₁) ≤ finish(o₁). (OPT chọn gì đó ≥ min finish time.)
• j → j+1: giả sử finish(gⱼ) ≤ finish(oⱼ). OPT chọn oⱼ₊₁ với start(oⱼ₊₁) ≥ finish(oⱼ). Vì finish(gⱼ) ≤ finish(oⱼ) ≤ start(oⱼ₊₁), hoạt động oⱼ₊₁ tương thích với greedy sau bước j. Greedy chọn gⱼ₊₁ là hoạt động tương thích finish sớm nhất → finish(gⱼ₊₁) ≤ finish(oⱼ₊₁).

Kết luận: Nếu m > k (OPT tốt hơn), thì oₖ₊₁ tồn tại. Lemma cho finish(gₖ) ≤ finish(oₖ), và oₖ₊₁ tương thích với greedy sau bước k — greedy sẽ chọn thêm ít nhất một hoạt động, mâu thuẫn với k là kết thúc greedy. Do đó m ≤ k. Mà OPT là tối ưu nên m ≥ k. Vậy m = k.

Thử ngẫmlemma trên chỉ so sánh finish(gⱼ) với finish(oⱼ) từng cặp một, chưa từng so sánh trực tiếp G với OPT. Vì sao chứng minh từng cặp lại đủ để kết luận cho toàn bộ tập?

5. Huffman Coding — Greedy xây cây prefix code

5.1 Bài toán

Cho n ký tự với tần suất freq[c]. Tìm prefix-free code (không mã nào là prefix của mã khác) gán chuỗi bit cho mỗi ký tự sao cho tổng chiều dài mã hoá toàn bộ văn bản là nhỏ nhất.

Bài toán tương đương: xây binary tree T sao cho Σ freq[c] × depth(c) nhỏ nhất, trong đó depth(c) là độ sâu của ký tự c trong cây.

5.2 Huffman Algorithm

Huffman(freq[]):
    H <- MinHeap rỗng (keyed by frequency)

    for each ký tự c:
        H.push(LeafNode(c, freq[c]))    -- tạo node lá cho mỗi ký tự

    while H.size() > 1:
        left <- H.pop()     -- node tần suất thấp nhất
        right <- H.pop()    -- node tần suất thấp thứ hai
        merged <- InternalNode(left, right,
                               freq = left.freq + right.freq)
        H.push(merged)      -- gộp thành node mới, đẩy lại heap

    return H.pop()    -- root của Huffman tree

Time: O(n log n)  Space: O(n)

5.3 Ví dụ — 5 ký tự

Ký tự và tần suất: A=45, B=13, C=12, D=16, E=9, F=5.

Huffman codes: A=0, B=101, C=100, D=111, E=1101, F=1100.

Đọc cây theo trục dọc thì thấy ngay vì sao mã dài ngắn khác nhau: mỗi lần gộp hai node tần suất nhỏ nhất là đẩy chúng xuống sâu thêm một tầng, mà độ sâu chính là số bit. F và E bị gộp ngay bước đầu nên rơi xuống đáy với mã 4 bit; A không bị gộp lần nào nên dừng lại ngay dưới gốc với mã 1 bit.

Chiều dài trung bình: (45×1 + 13×3 + 12×3 + 16×3 + 9×4 + 5×4) / 100 = (45+39+36+48+36+20)/100 = 224/100 = 2.24 bits/ký tự.

So với fixed-length (3 bits/ký tự cho 6 ký tự): tiết kiệm 25%. Đây là nền tảng của gzip, bzip2, DEFLATE.

5.4 Vì sao Huffman đúng

Greedy choice: hai ký tự có tần suất nhỏ nhất luôn nằm ở độ sâu lớn nhất trong cây tối ưu (bài chứng minh qua exchange argument — hoán đổi hai node depth-max với hai node freq-min không làm tăng cost).

Optimal substructure: sau khi gộp hai node frequency nhỏ nhất thành node mới với freq = f₁ + f₂, bài toán còn lại là Huffman cho (n-1) ký tự — tối ưu đệ quy.

Thử ngẫmnếu file log của bạn chỉ có 2 ký tự phân biệt, cây Huffman cho ra mã dài bao nhiêu bit mỗi ký tự, và nén có còn ích lợi gì không?

6. Khi nào Greedy SAI

6.1 0/1 Knapsack — đã thấy ở bài trước

Items không chia được, nên lựa chọn tham lam (ratio value/weight cao nhất) có thể chiếm hết không gian và chặn kết hợp tốt hơn.

6.2 Coin Change với mệnh giá lạ

Mệnh giá {1, 3, 4}, cần đổi 6.

Greedy (chọn mệnh giá lớn nhất không vượt amount):

• Chọn 4 (còn 2)
• Chọn 1 (còn 1)
• Chọn 1 (còn 0)
• Kết quả: 3 đồng

DP tối ưu:

• Chọn 3 + 3
• Kết quả: 2 đồng

Vì sao greedy sai? Khi chọn 4, ta "phá vỡ" khả năng dùng hai đồng 3. Mệnh giá {1, 3, 4} không có tính canonical — đồng 4 không "bao trùm" được tổ hợp {3, 1} theo cách làm tối ưu. Greedy choice property không thỏa mãn.

6.3 Shortest Path với edge âm

Dijkstra (greedy: luôn expand đỉnh gần nhất) sai khi có edge âm — xem bài Dijkstra. Một edge âm có thể làm path "dài" trở thành path ngắn hơn sau khi greedy đã finalize đỉnh đó.

6.4 Tóm tắt: khi nào greedy đúng vs sai

7. Liên hệ các bài khác

• 0/1 Knapsack: Counter-example trực tiếp cho greedy — bài này giải thích tại sao DP cần thiết thay greedy. Hai bài đọc liên tiếp tạo bức tranh đầy đủ về ranh giới greedy/DP.
• Backtracking: Khi greedy sai và DP quá tốn không gian/thời gian, backtracking là lựa chọn thứ ba — thử tất cả kết hợp với cắt tỉa. Tam giác greedy/DP/backtracking là framework quyết định thuật toán tối ưu.
• Hàng đợi ưu tiên: Huffman coding phụ thuộc hoàn toàn vào min-heap — mỗi bước cần pop 2 phần tử min và push 1 phần tử mới. Hiểu heap là hiểu vì sao Huffman O(n log n).
• Dijkstra: Dijkstra là thuật toán greedy trên graph — mở rộng đỉnh có dist nhỏ nhất. Bài đó chứng minh greedy invariant đúng khi không có negative edge — cùng template exchange argument.

8. Deep Dive

9. Tóm tắt

• Greedy đúng khi có hai tính chất: greedy choice property (lựa chọn tham lam không chặn tối ưu) và optimal substructure (tối ưu lớn chứa tối ưu con).
• Exchange argument: chứng minh bằng cách giả sử OPT khác greedy, hoán đổi một phần tử, chứng minh nghiệm mới không tệ hơn → greedy tối ưu.
• Interval Scheduling: sort theo finish time sớm nhất, chọn tham lam. Chứng minh: greedy "chiếm ít tương lai nhất" — tạo nhiều room nhất cho hoạt động tiếp theo.
• Huffman Coding: gộp hai node min-frequency mỗi bước qua min-heap, O(n log n). Nền tảng của gzip/DEFLATE.
• Greedy SAI: 0/1 knapsack (không chia được), coin change với mệnh giá lạ, Dijkstra với negative edge. Greedy đúng với fractional knapsack, interval scheduling, Huffman, Dijkstra (no negative edge).
• Không bao giờ dùng greedy mà không chứng minh greedy choice property — dù trực giác có vẻ đúng.

10. Tự kiểm tra

Bài tiếp theo: Backtracking và cắt tỉa