Pembuktian Algoritma Greedy

Sepanjang Section ini kita melihat algoritma greedy yang optimal: activity selection, fractional knapsack, Huffman, job scheduling. Namun tidak semua greedy optimal — pembuktian diperlukan sebelum kita percaya bahwa strategi greedy benar-benar menghasilkan solusi global optimal. Pada Chapter ini kita akan membahas tiga teknik formal pembuktian greedy: exchange argument, greedy stays ahead, dan matroid theory. Kita juga akan memverifikasi secara empiris bahwa greedy cocok dengan brute force pada banyak instance acak — validasi numerik terhadap pembuktian analitik.

Aturan: Tiga Teknik Pembuktian Greedy #

Pembuktian optimalitas greedy umumnya menggunakan salah satu dari tiga teknik berikut.

1. Exchange Argument #

Teknik paling umum. Langkahnya:

1. Misalkan S* adalah solusi optimal yang tidak memuat pilihan greedy pertama g.
2. Identifikasi elemen e di S* yang “bersaing” dengan g.
3. Ganti e dengan g di S*, menghasilkan S'.
4. Tunjukkan S' tetap feasible dan S' tidak lebih buruk dari S*.
5. Karena S* optimal, S' juga optimal. Maka ada solusi optimal yang memuat g — greedy-choice property terbukti.

2. Greedy Stays Ahead #

Bandingkan greedy dengan solusi optimal langkah demi langkah. Tunjukkan bahwa setelah k langkah, solusi greedy “lebih maju” (mis. jumlah elemen ≥, total profit ≥, finish time ≤) dibanding k elemen pertama solusi optimal. Maka di akhir, greedy minimal sama baik dengan optimal.

3. Matroid Theory #

Kerangka formal. Bila masalah dapat dimodelkan sebagai matroid (E, I) (dengan E himpunan elemen, I himpunan independent set yang memenuhi tiga aksioma), maka greedy selalu optimal. Contoh: MST berbasis graphic matroid; job scheduling berbasis transversal matroid.

Mekanisme: Contoh Exchange Argument pada Activity Selection #

Mari kita bedah exchange argument untuk activity selection secara formal.

Spesifikasi: diberikan n aktivitas dengan (start, finish), pilih himpunan kompatibel (non-overlapping) maksimum.

Greedy: sort by finish ascending, pilih aktivitas dengan finish paling awal, lalu iterasi pilih yang kompatibel.

Pembuktian:

1. Misalkan S* = {a_1, a_2, ..., a_k} solusi optimal dengan aktivitas terurut by finish ascending. Misalkan g adalah aktivitas dengan finish paling awal di seluruh input.
2. g.finish ≤ a_1.finish (karena g finish paling awal).
3. Aktivitas apa pun yang kompatibel dengan a_1 (start ≥ a_1.finish) juga kompatibel dengan g (karena g.finish ≤ a_1.finish ⟹ start ≥ a_1.finish ≥ g.finish).
4. Substitusi: S' = (S* \ {a_1}) ∪ {g}. S' feasible karena g kompatibel dengan a_2 (start a_2 ≥ a_1.finish ≥ g.finish).
5. |S'| = |S*| = k, jadi S' juga optimal dan memuat g.
6. Greedy-choice property terbukti: ada solusi optimal yang memuat g.

Setelah g dipilih, sub-masalah adalah memilih aktivitas maksimum dari {a : a.start ≥ g.finish} — struktur identik dengan masalah awal. Maka optimal substructure terpenuhi, dan greedy optimal.

Mekanisme: Greedy Stays Ahead pada Huffman Coding #

Untuk membuktikan Huffman optimal, teknik greedy stays ahead cocok digunakan. Intuisi: Huffman selalu menggabungkan dua node dengan frekuensi terkecil — ini menjaga pohon “tetap seimbang dari bawah” sehingga total panjang kode minimum.

Skema bukti (ringkas):

1. Misalkan ada pohon prefix code optimal T* dengan total panjang L*.
2. Misalkan x dan y adalah dua simbol dengan frekuensi terkecil. Bila x dan y bukan sibling paling dalam di T*, lakukan rotasi: tukar posisi x dengan node paling dalam. Total panjang tidak naik karena freq(x) minimal — rotasi menghemat atau sama.
3. Setelah rotasi, x dan y menjadi sibling paling dalam. Gabungkan keduanya menjadi node baru dengan frekuensi freq(x) + freq(y).
4. Sub-masalah: bangun Huffman untuk n-1 simbol (simbol x, y diganti dengan node gabungan). Sub-masalah punya struktur identik.
5. Induksi pada n: asumsi greedy optimal untuk n-1 simbol, maka optimal untuk n simbol.

Pembuktian rinci memerlukan induksi formal, namun intinya: greedy stays ahead karena setiap merge Huffman tidak menambah panjang lebih dari yang diperlukan oleh optimalitas lokal.

Kode: Verifikasi Empiris Greedy vs Brute Force #

Pembuktian formal meyakinkan, tetapi verifikasi empiris dengan random testing memberikan keyakinan tambahan dan membantu mendeteksi bug implementasi. Berikut kode yang menguji kesesuaian greedy dengan brute force pada activity selection.

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

struct Activity {
    int start, finish;
};

// Brute force: cek semua subset, kembalikan ukuran maksimum kompatibel
int bruteForce(const std::vector<Activity>& acts) {
    int n = acts.size();
    int best = 0;
    for (int mask = 0; mask < (1 << n); ++mask) {
        bool ok = true;
        for (int i = 0; i < n && ok; ++i) {
            if (!(mask & (1 << i))) continue;
            for (int j = i + 1; j < n && ok; ++j) {
                if (!(mask & (1 << j))) continue;
                // Cek overlap: a dan b overlap bila start < finish_other
                if (acts[i].start < acts[j].finish &&
                    acts[j].start < acts[i].finish) {
                    ok = false;
                }
            }
        }
        if (ok) {
            int cnt = __builtin_popcount(mask);
            best = std::max(best, cnt);
        }
    }
    return best;
}

// Greedy: sort by finish ascending, pilih kompatibel
int greedy(const std::vector<Activity>& acts) {
    std::vector<Activity> sorted = acts;
    std::sort(sorted.begin(), sorted.end(),
              [](const Activity& a, const Activity& b) {
                  return a.finish < b.finish;
              });
    int count = 0, lastFinish = -1;
    for (const auto& a : sorted) {
        if (a.start >= lastFinish) {
            ++count;
            lastFinish = a.finish;
        }
    }
    return count;
}

int main() {
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> distN(3, 10);
    std::uniform_int_distribution<int> distStart(0, 18);
    std::uniform_int_distribution<int> distLen(1, 6);

    const int NUM_TESTS = 200;
    int passes = 0;
    for (int t = 1; t <= NUM_TESTS; ++t) {
        int n = distN(rng);
        std::vector<Activity> acts(n);
        for (auto& a : acts) {
            int s = distStart(rng);
            int len = distLen(rng);
            a.start = s;
            a.finish = s + len;
        }
        int bf = bruteForce(acts);
        int gr = greedy(acts);
        bool pass = (bf == gr);
        if (pass) ++passes;
        if (t <= 5 || !pass) {
            std::cout << "Tes " << t << " (n=" << n
                      << "): brute=" << bf << ", greedy=" << gr
                      << " [" << (pass ? "PASS" : "FAIL") << "]\n";
        }
    }
    std::cout << "\nTotal: " << passes << "/" << NUM_TESTS << " tes lulus.\n";
    if (passes == NUM_TESTS) {
        std::cout << "Greedy == Brute pada semua instance acak — "
                     "pembuktian analitik terkonfirmasi empiris.\n";
    }
    return 0;
}

Output yang Dihasilkan:

Tes 1 (n=5): brute=4, greedy=4 [PASS]
Tes 2 (n=3): brute=3, greedy=3 [PASS]
Tes 3 (n=8): brute=4, greedy=4 [PASS]
Tes 4 (n=3): brute=2, greedy=2 [PASS]
Tes 5 (n=4): brute=3, greedy=3 [PASS]

Total: 200/200 tes lulus.
Greedy == Brute pada semua instance acak — pembuktian analitik terkonfirmasi empiris.

Bedah Kode Baris-per-Baris #

1. for (int mask = 0; mask < (1 << n); ++mask): iterasi semua subset aktivitas. 2^n kemungkinan — hanya feasible untuk n kecil (≤ 20).
2. for (int i = 0; i < n && ok; ++i) for (int j = i + 1; j < n && ok; ++j): untuk setiap pasangan aktivitas di subset, cek overlap. Kompleksitas O(n^2) per subset.
3. if (acts[i].start < acts[j].finish && acts[j].start < acts[i].finish): kondisi overlap dua interval. Bila kedua kondisi true, interval tumpang tindih.
4. best = std::max(best, __builtin_popcount(mask));: __builtin_popcount menghitung jumlah bit 1 (jumlah aktivitas di subset). Catat maksimum.
5. std::sort(sorted.begin(), ..., [](...) { return a.finish < b.finish; }): greedy sort — kunci optimalitas activity selection.
6. if (a.start >= lastFinish) { ++count; lastFinish = a.finish; }: pilih aktivitas yang kompatibel dengan yang terakhir dipilih.
7. std::mt19937 rng(42);: PRNG dengan seed fixed. Seed tetap menjamin output reproducible di seluruh run.
8. std::uniform_int_distribution<int> distN(3, 10);: jumlah aktivitas per test acak di [3, 10]. Batas atas 10 karena brute force O(2^10 × 10^2) = 102400 per test.
9. if (passes == NUM_TESTS): bila semua tes lulus, greedy terbukti konsisten dengan brute force pada sample acak. Ini bukan pembuktian formal — tetapi memberi keyakinan kuat terhadap pembuktian analitik.

Matroid Theory: Kerangka Formal #

Matroid (E, I) terdiri dari himpunan elemen E dan koleksi independent set I ⊆ 2^E yang memenuhi aksioma:

1. Kosong independent: ∅ ∈ I.
2. Heredity: bila B ∈ I dan A ⊆ B, maka A ∈ I.
3. Augmentation: bila A, B ∈ I dengan |A| < |B|, maka ada e ∈ B \ A sehingga A ∪ {e} ∈ I.

Teorema: bila masalah optimasi dapat dimodelkan sebagai matroid berbobot (E, I, w) (dengan w: E → ℝ), maka algoritma greedy (sort by weight descending, tambah elemen selama tetap independent) menghasilkan basis dengan bobot maksimum.

Contoh matroid:

Tabel Pembuktian untuk Algoritma Greedy Klasik #

Komparasi Teknik Pembuktian #

Aplikasi Nyata Pembuktian Greedy #

• Verifikasi algoritma kompetisi: setelah implement greedy, uji dengan brute force pada n ≤ 10 untuk memastikan tidak ada counter-example.
• Design algoritma baru: pertukaran gagasan antara greedy dan DP — bila greedy terbukti via exchange argument, gunakan greedy; bila tidak, fallback ke DP.
• Sertifikasi sistem kritis: algoritma scheduling pada avionics, medical devices memerlukan pembuktian formal sebelum deploy.
• Optimasi compiler: pembuktian register allocation (graph coloring pada chordal graph, greedy optimal).

Ringkasan #

• Tiga teknik pembuktian greedy: exchange argument, greedy stays ahead, matroid theory.
• Exchange argument: tukar elemen solusi optimal dengan pilihan greedy, tunjukkan tetap optimal.
• Greedy stays ahead: bandingkan greedy dan optimal langkah demi langkah, tunjukkan greedy ≥ optimal.
• Matroid theory: kerangka formal — bila masalah = matroid, greedy dijamin optimal (mis. MST, Kruskal).
• Verifikasi empiris dengan random testing melengkapi pembuktian analitik — mendeteksi bug implementasi.
• Activity selection: bukti via exchange argument (aktivitas dengan finish paling awal selalu bisa dimasukkan ke solusi optimal).
• Huffman: bukti via greedy stays ahead (rotasi dua node terkecil ke sibling paling dalam).

Section Greedy Algorithms berakhir di sini. Bab berikutnya akan masuk ke Section Dynamic Programming — paradigma yang lebih aman tetapi lebih lambat, yang mengeksplorasi semua pilihan dan menyimpan hasil untuk digunakan ulang.