Greedy Choice Property

Pada Chapter sebelumnya kita melihat greedy yang optimal untuk canonical coin denominations namun gagal untuk denominasi {1, 3, 4}. Pertanyaan mendasar muncul: kapan tepatnya kita boleh percaya bahwa pilihan lokal optimal akan menghasilkan solusi global optimal? Jawabannya adalah dua properti formal: greedy-choice property dan optimal substructure. Pada Chapter ini kita akan membahas keduanya secara formal, lalu memperkenalkan teknik exchange argument — alat utama untuk membuktikan greedy-choice property pada algoritma greedy klasik.

Aturan: Dua Properti Wajib untuk Greedy yang Optimal #

Agar algoritma greedy dijamin optimal, masalah harus memenuhi dua properti berikut:

Greedy-Choice Property: terdapat solusi optimal global yang mengandung pilihan greedy pertama. Artinya, pilihan yang diambil greedy pada langkah pertama tidak menghalangi tercapainya solusi global optimal.
Optimal Substructure: solusi optimal masalah mengandung solusi optimal untuk sub-masalah yang tersisa setelah pilihan greedy diambil. Sub-masalah harus independen — solusi pada satu sub-masalah tidak memengaruhi sub-masalah lain.

Tanpa kedua properti ini, greedy tidak dapat dijamin optimal. Banyak masalah yang memenuhi optimal substructure tetapi gagal greedy-choice property (mis. 0/1 knapsack), sehingga membutuhkan dynamic programming.

Mekanisme: Intuisi di Balik Greedy-Choice Property #

Misalkan kita punya masalah optimasi dengan solusi optimal S*. Greedy memilih g sebagai pilihan pertamanya. Greedy-choice property menyatakan bahwa kita selalu bisa “menukar” elemen pertama solusi optimal S* dengan g tanpa membuat S* menjadi tidak optimal.

flowchart LR subgraph S_OPT ["Solusi Optimal S*"] A1[e1] A2[e2] A3["..."] end subgraph S_GREEDY ["Solusi Greedy"] G1[g] G2[e2'] G3["..."] end A1 -- "exchange" --> G1 S_OPT -->|optimal| S_GREEDY

Langkah pembuktian khas:

Asumsikan S* adalah solusi optimal yang tidak mengandung g.
Identifikasi elemen e di S* yang “bersaing” dengan g (mis. aktivitas dengan start time sama).
Ganti e dengan g di S*, menghasilkan S'.
Tunjukkan S' tetap feasible (memenuhi constraint) dan tidak lebih buruk dari S*.
Karena S* optimal, S' juga optimal. Maka ada solusi optimal yang mengandung g.

Inilah inti exchange argument. Pembuktian ini bersifat konstruktif: kita menunjukkan eksplisit cara menukar elemen tanpa merusak optimalitas.

Contoh: Greedy-Choice Property pada Activity Selection #

Sebagai ilustrasi, mari kita terapkan exchange argument pada activity selection: diberikan n aktivitas dengan (start_i, finish_i), pilih himpunan aktivitas maksimum yang tidak tumpang tindih.

Greedy choice: pilih aktivitas dengan finish time paling awal.

Pembuktian informal:

Misalkan S* adalah solusi optimal dan a* adalah aktivitas pertama (finish time paling awal) di S*.
Misalkan g adalah aktivitas dengan finish time paling awal di seluruh masukan. Greedy memilih g.
Karena g.finish ≤ a*.finish, aktivitas apa pun yang tidak tumpang tindih dengan a* juga tidak tumpang tindih dengan g. (Ganti a* dengan g tetap feasible.)
Maka S' = S* − {a*} ∪ {g} adalah solusi optimal lain yang mengandung g.
Sub-masalah yang tersisa adalah memilih aktivitas maksimum dari aktivitas dengan start ≥ g.finish. Ini optimal substructure karena bersifat independen terhadap pilihan awal.

Greedy-choice property terbukti. Algoritma greedy yang memilih earliest finish time akan menghasilkan solusi optimal global.

Kode: Demonstrasi Konsep #

Kode berikut mengilustrasikan bagaimana greedy-choice property bekerja pada activity selection, dengan trace eksplisit pilihan greedy pertama dan pertukaran terhadap solusi optimal.

cpp
#include <iostream>
#include <vector>
#include <algorithm>

struct Activity {
    int id;
    int start;
    int finish;
};

// Greedy: pilih aktivitas dengan finish time paling awal
std::vector<int> greedyActivitySelection(std::vector<Activity> acts) {
    // Sort ascending by finish time
    std::sort(acts.begin(), acts.end(),
              [](const Activity& a, const Activity& b) {
                  return a.finish < b.finish;
              });

    std::vector<int> chosen;
    int lastFinish = -1;
    for (const auto& a : acts) {
        if (a.start >= lastFinish) {
            chosen.push_back(a.id);
            lastFinish = a.finish;
        }
    }
    return chosen;
}

int main() {
    std::vector<Activity> acts = {
        {1, 1, 4}, {2, 3, 5}, {3, 0, 6},
        {4, 5, 7}, {5, 3, 9}, {6, 5, 9},
        {7, 6, 10}, {8, 8, 11}, {9, 8, 12},
        {10, 2, 14}, {11, 12, 16}
    };

    auto chosen = greedyActivitySelection(acts);

    std::cout << "Aktivitas terpilih (id): ";
    for (int id : chosen) std::cout << id << ' ';
    std::cout << '\n';
    std::cout << "Jumlah aktivitas: " << chosen.size() << '\n';

    return 0;
}

Output yang Dihasilkan:

text

Aktivitas terpilih (id): 1 4 8 11
Jumlah aktivitas: 4

Bedah Kode Baris-per-Baris #

struct Activity { int id; int start; int finish; };: struktur data aktivitas. Field id dipertahankan agar output dapat ditelusuri kembali ke aktivitas asli.
std::sort(acts.begin(), acts.end(), [](...) { return a.finish < b.finish; }): urutkan ascending by finish time. Sort ini menyiapkan kandidat greedy — yang paling awal finish di depan.
int lastFinish = -1;: penanda waktu selesai aktivitas terakhir yang dipilih. Mulai dari -1 agar aktivitas dengan start 0 dapat dipilih.
if (a.start >= lastFinish): cek non-overlap. Aktivitas a boleh dipilih hanya bila mulai setelah aktivitas sebelumnya selesai.
chosen.push_back(a.id); lastFinish = a.finish;: catat aktivitas terpilih, lalu update lastFinish. Pilihan ini tidak akan dibatalkan — inilah greedy.
Output 1 4 8 11: id aktivitas terpilih dengan finish time 4, 7, 11, 16 — empat aktivitas non-overlapping, yang merupakan maksimum.

Optimal Substructure pada Activity Selection #

Setelah greedy memilih aktivitas g (finish time paling awal), sub-masalah yang tersisa adalah memilih aktivitas maksimum dari himpunan aktivitas yang start ≥ g.finish. Sub-masalah ini:

Independen: pilihan di sub-masalah tidak memengaruhi kelayakan aktivitas sebelum g.finish.
Struktur identik: sama dengan masalah awal, hanya dengan input yang lebih kecil.
Optimal: solusi optimal sub-masalah digabung dengan g menghasilkan solusi optimal masalah awal.

Inilah yang membuat rekursi greedy bekerja: setiap pilihan greedy memperkecil masalah tanpa kehilangan jaminan optimalitas.

Klasifikasi Masalah berdasarkan Properti #

Masalah	Greedy-Choice	Optimal Substructure	Algoritma Optimal
Activity selection	Ya	Ya	Greedy
Fractional knapsack	Ya	Ya	Greedy
Huffman coding	Ya	Ya	Greedy (min-heap)
MST (Kruskal/Prim)	Ya	Ya	Greedy
Dijkstra (non-negative)	Ya	Ya	Greedy
0/1 knapsack	Tidak	Ya	Dynamic Programming
Matrix chain multiplication	Tidak	Ya	Dynamic Programming
Longest common subsequence	Tidak	Ya	Dynamic Programming
Travelling salesman	Tidak	Ya	DP / branch & bound

Pola jelas terlihat: greedy cocok bila kedua properti terpenuhi. Bila hanya optimal substructure tanpa greedy-choice, gunakan DP.

Teknik Pembuktian Greedy #

Tiga teknik utama untuk membuktikan greedy-choice property:

Exchange argument — paling umum. Asumsikan solusi optimal yang tidak memakai pilihan greedy, tukar elemennya, tunjukkan solusi pengganti tetap optimal.
Greedy stays ahead — tunjukkan solusi greedy selalu “lebih maju” (mis. finish lebih awal, profit lebih tinggi) dibanding solusi optimal pada setiap langkah. Maka di akhir, greedy minimal sama baik.
Matroid theory — kerangka formal. Bila masalah dapat dimodelkan sebagai matroid (mis. graphic matroid untuk MST), greedy dijamin optimal.

flowchart TD A[Greedy algorithm] --> B{Pembuktian optimalitas?} B --> C[Exchange argument] B --> D[Greedy stays ahead] B --> E[Matroid theory] C --> F[Tukar elemen solusi optimal<br/>dengan pilihan greedy] D --> G[Tunjukkan greedy selalu<br/>lebih maju tiap langkah] E --> H[Modelkan sebagai matroid]

Aplikasi Pembuktian: Fractional Knapsack #

Untuk membuktikan greedy optimal pada fractional knapsack:

Greedy choice: ambil item dengan rasio value/weight tertinggi.
Exchange argument: misalkan S* solusi optimal tidak mengandung g (item rasio tertinggi). Maka S* mengandung sejumlah item rasio lebih rendah. Karena rasio g ≥ rasio semua item lain, kita dapat menukar sebagian berat item lain dengan berat g yang setara — total value tidak berkurang, malah bisa naik. Kontradiksi dengan asumsi S* optimal bila tidak mengandung g.
Optimal substructure: setelah g habis (atau kapasitas penuh), sub-masalah adalah fractional knapsack dengan item tersisa dan kapasitas tersisa — struktur identik.

Pembuktian rinci akan dibahas pada Chapter Pembuktian Algoritma Greedy. Untuk sekarang, perhatikan bahwa exchange argument berlaku universal untuk membuktikan greedy-choice property.

Ringkasan #

Greedy optimal hanya bila greedy-choice property dan optimal substructure terpenuhi.
Greedy-choice property: ada solusi optimal yang mengandung pilihan greedy pertama.
Optimal substructure: solusi optimal masalah mengandung solusi optimal sub-masalah.
Exchange argument adalah teknik utama: tukar elemen solusi optimal dengan pilihan greedy, tunjukkan tetap optimal.
Activity selection membuktikan greedy-choice property dengan menukar aktivitas pertama solusi optimal dengan aktivitas finish paling awal.
Banyak masalah punya optimal substructure tetapi tanpa greedy-choice — di sinilah DP diperlukan.

Chapter berikutnya akan membahas Activity Selection secara lengkap, dengan implementasi C++ dan trace langkah demi langkah.