Strategi greedy

Argumen penukaran pada pilihan lokal dan kondisi ketika greedy gagal.

Daftar isi

Greedy adalah strategi penyelesaian masalah yang membuat pilihan lokal terbaik pada setiap langkah dan tidak pernah menariknya kembali. Strategi ini hanya butuh satu lintasan sehingga sangat cepat, tetapi tidak semua soal menerima perlakuan seperti itu. Topik ini membahas syarat agar greedy benar, cara membuktikannya lewat argumen penukaran (exchange argument), satu contoh yang benar-benar optimal berupa pemilihan kegiatan, dan satu tandingan berupa pertukaran koin yang menjatuhkannya.

Pilihan lokal dan harapan global#

Algoritma greedy menilai setiap langkah secara terpisah dan mengambil opsi yang tampak paling menguntungkan saat itu, tanpa menimbang ulang keputusan lama. Harapannya, rangkaian pilihan lokal terbaik itu menghasilkan solusi global yang optimal. Harapan tersebut hanya terwujud pada sebagian soal. Sifat yang menentukannya disebut sifat pilihan greedy (greedy choice property), yaitu adanya satu pilihan lokal yang pasti termuat dalam setidaknya satu solusi optimal, sehingga mengambilnya tidak pernah merusak jawaban akhir.

Syarat kedua bersifat struktural dan melengkapi sifat pilihan greedy di atas. Sisa masalah setelah pilihan diambil harus berbentuk serupa dengan masalah aslinya, hanya lebih kecil, sehingga proses yang sama dapat diulang sampai habis. Kedua syarat ini tidak bisa diverifikasi dengan mata saja. Kriteria yang terlihat masuk akal bisa saja meleset pada kasus kecil, dan kegagalannya tidak menimbulkan error karena program tetap berjalan lalu menghasilkan jawaban yang keliru. Karena itu, setiap kriteria greedy layak dibuktikan atau setidaknya diuji dengan tandingan kecil sebelum dipercaya.

Argumen penukaran#

Argumen penukaran (exchange argument) adalah pembuktian standar untuk sifat pilihan greedy. Caranya, ambil satu solusi optimal yang tidak memuat pilihan greedy, lalu tukar satu elemennya menjadi pilihan greedy. Bila pertukaran itu tidak pernah mengurangi kualitas solusi, berarti ada solusi optimal yang memuat pilihan greedy, dan pilihan tersebut aman diambil sejak langkah pertama.

Pembuktian ini paling mudah dipahami pada pemilihan kegiatan. Misalkan kriteria greedy memilih kegiatan yang selesai paling awal, sedangkan suatu solusi optimal memulai dengan kegiatan lain yang selesai lebih lambat. Menukar kegiatan pembuka solusi optimal dengan kegiatan yang selesai paling awal tidak menabrak sisa jadwal, karena kegiatan baru melepaskan ruang waktu lebih cepat daripada yang lama. Jumlah kegiatan tetap sama, sehingga hasil penukaran tetap optimal. Argumen yang sama berlaku untuk sisa jadwal yang lebih kecil, dan begitulah kriteria selesai paling awal terbukti benar untuk soal ini. Polanya selalu sama, yaitu membuktikan bahwa penukaran tidak pernah lebih buruk, lalu mengulang argumennya pada sisa masalah yang lebih kecil.

Memilih kegiatan dengan greedy#

Soalnya, dari beberapa kegiatan dengan waktu mulai dan waktu selesai, pilih sebanyak mungkin kegiatan tanpa tumpang tindih. Kriteria greedy mengurutkan kegiatan menurut waktu selesai, lalu mengambil kegiatan berikutnya yang mulai tidak lebih awal daripada selesai kegiatan terakhir yang dipilih. Berkas berikut menerapkan urutan itu pada enam kegiatan harian sebuah organisasi kampus. Masukannya berupa pasangan jam yang kecil dan mudah diperiksa ulang dengan tangan. Variabel akhir_sebelumnya berperan sebagai batas yang bergerak, yaitu waktu selesai paling akhir dari kegiatan yang sudah dipilih, dan setiap kegiatan hanya dibandingkan dengan batas itu satu kali.

python pilih-kegiatan.py

"""Pemilihan kegiatan dengan greedy: urutkan berdasarkan waktu selesai paling awal."""

kegiatan = [
    ("rapat pagi", 1, 2),
    ("presentasi", 3, 4),
    ("piket ruangan", 0, 6),
    ("diskusi kelompok", 5, 7),
    ("senam bersama", 8, 9),
    ("rapat panitia", 5, 9),
]

urut = sorted(kegiatan, key=lambda k: k[2])  # kriteria greedy: selesai paling awal
print("urutan selesai :", urut)

dipilih, akhir_sebelumnya = [], -1
for nama, mulai, selesai in urut:
    if mulai >= akhir_sebelumnya:   # tidak bertabrakan dengan pilihan sebelumnya
        dipilih.append(nama)
        akhir_sebelumnya = selesai

print("dipilih        :", dipilih)
print("jumlah maksimum:", len(dipilih))

text Keluaran

urutan selesai : [('rapat pagi', 1, 2), ('presentasi', 3, 4), ('piket ruangan', 0, 6), ('diskusi kelompok', 5, 7), ('senam bersama', 8, 9), ('rapat panitia', 5, 9)]
dipilih        : ['rapat pagi', 'presentasi', 'diskusi kelompok', 'senam bersama']
jumlah maksimum: 4

Keluaran menunjukkan empat kegiatan terpilih. Kegiatan piket ruangan (0 sampai 6) sengaja terlewat karena menutup dua kegiatan pendek, yaitu rapat pagi dan presentasi. Melewatinya membuka keduanya, sehingga jumlah pilihan menjadi lebih banyak, dan persis di titik inilah kriteria selesai paling awal bekerja. Dua kegiatan yang sama-sama selesai pada waktu 9 diurutkan mengikuti urutan asli daftarnya. Keputusan itu tidak mengubah hasil, karena senam bersama tetap terpilih, sedangkan rapat panitia selalu bertabrakan dengan pilihan yang sudah ada.

Varian Java#

Algoritma yang sama diterjemahkan ke Java tanpa perubahan logika: data kegiatan disimpan sebagai array dua dimensi berisi pasangan mulai dan selesai. Arrays.sort mengurutkannya dengan pembanding lambda yang hanya melihat elemen kedua, dan pembanding itu memakai Integer.compare alih-alih pengurangan langsung agar nilai balik tidak salah bila selisihnya melebihi rentang int. Pengurutan Java juga stabil untuk elemen bernilai sama, sehingga dua kegiatan yang selesai pada waktu 9 tetap mengikuti urutan penulisannya, sama seperti perilaku sorted pada Python. Bila nama kegiatan juga ingin dicetak, array paralel berisi nama atau objek kegiatan perlu ditambahkan, karena array int hanya memuat angkanya. Program dijalankan sebagai satu berkas dengan perintah java Kegiatan.java, tanpa tahap kompilasi manual.

java Kegiatan.java

import java.util.Arrays;

public class Kegiatan {
    // pemilihan kegiatan dengan greedy: urutkan berdasarkan waktu selesai paling awal

    public static void main(String[] args) {
        int[][] kegiatan = {
            {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}
        };
        Arrays.sort(kegiatan, (a, b) -> Integer.compare(a[1], b[1]));

        int jumlah = 0;
        int akhirSebelumnya = -1;
        StringBuilder dipilih = new StringBuilder();
        for (int[] k : kegiatan) {
            if (k[0] >= akhirSebelumnya) {
                jumlah++;
                if (dipilih.length() > 0) {
                    dipilih.append(", ");
                }
                dipilih.append("(").append(k[0]).append("-").append(k[1]).append(")");
                akhirSebelumnya = k[1];
            }
        }
        System.out.println("urutan selesai : " + Arrays.deepToString(kegiatan));
        System.out.println("dipilih        : " + dipilih);
        System.out.println("jumlah maksimum: " + jumlah);
    }
}

text Keluaran

urutan selesai : [[1, 2], [3, 4], [0, 6], [5, 7], [8, 9], [5, 9]]
dipilih        : (1-2), (3-4), (5-7), (8-9)
jumlah maksimum: 4

Keluarannya identik dengan versi Python, yaitu empat kegiatan terpilih dengan urutan kegiatan yang sama. Pemilihan interval direkam pada StringBuilder, sedangkan Arrays.deepToString mencetak seluruh urutan setelah pengurutan. Perbedaannya murni bahasa, bukan algoritma, sehingga argumen penukarannya tetap berlaku apa adanya.

Ketika greedy gagal#

Pertukaran koin adalah tandingan klasiknya. Dengan pecahan 1, 3, dan 4, tukar nilai 6. Greedy mengambil koin 4 lebih dulu, sisa 2 hanya bisa dilunasi dengan dua koin 1, sehingga totalnya tiga koin. Solusi optimal adalah dua koin 3. Pilihan lokal yang tampak besar itu menutup kombinasi 3 + 3 yang lebih hemat, dan inilah wujud sifat pilihan greedy yang tidak terpenuhi.

python koin-greedy.py

"""Pertukaran koin pecahan 1, 3, 4: greedy kalah dari solusi optimal pada nilai 6."""

pecahan = [4, 3, 1]   # pecahan terbesar lebih dulu, ciri pendekatan greedy


def koin_greedy(nilai):
    sisa, koin = nilai, []
    for p in pecahan:
        while sisa >= p:
            sisa -= p
            koin.append(p)
    return koin


def koin_optimal(nilai):
    # tabel DP kecil sebagai pembanding, dibedah pada topik DP satu dimensi
    dp = [0] + [999] * nilai
    for n in range(1, nilai + 1):
        for p in pecahan:
            if p <= n and dp[n - p] + 1 < dp[n]:
                dp[n] = dp[n - p] + 1
    koin, sisa = [], nilai
    while sisa > 0:
        for p in pecahan:
            if p <= sisa and dp[sisa - p] + 1 == dp[sisa]:
                koin.append(p)
                sisa -= p
                break
    return koin


for nilai in range(1, 11):
    g, o = koin_greedy(nilai), koin_optimal(nilai)
    status = "sama" if len(g) == len(o) else "GREEDY KALAH"
    print(f"nilai {nilai:2d} | greedy {str(g):12s} {len(g)} koin | "
          f"optimal {str(o):9s} {len(o)} koin | {status}")

text Keluaran

nilai  1 | greedy [1]          1 koin | optimal [1]       1 koin | sama
nilai  2 | greedy [1, 1]       2 koin | optimal [1, 1]    2 koin | sama
nilai  3 | greedy [3]          1 koin | optimal [3]       1 koin | sama
nilai  4 | greedy [4]          1 koin | optimal [4]       1 koin | sama
nilai  5 | greedy [4, 1]       2 koin | optimal [4, 1]    2 koin | sama
nilai  6 | greedy [4, 1, 1]    3 koin | optimal [3, 3]    2 koin | GREEDY KALAH
nilai  7 | greedy [4, 3]       2 koin | optimal [4, 3]    2 koin | sama
nilai  8 | greedy [4, 4]       2 koin | optimal [4, 4]    2 koin | sama
nilai  9 | greedy [4, 4, 1]    3 koin | optimal [4, 4, 1] 3 koin | sama
nilai 10 | greedy [4, 4, 1, 1] 4 koin | optimal [4, 3, 3] 3 koin | GREEDY KALAH

Jalur greedy tiga koin melawan jalur optimal dua koin untuk nilai 6 dengan pecahan 1, 3, 4

Keluaran memperlihatkan dua kegagalan, yaitu nilai 6 dan nilai 10, sementara delapan nilai lain kebetulan sama. Diagram menunjukkan akar persoalan pada nilai 6, yaitu koin 4 yang diambil lebih dulu menyisakan angka 2, dan angka itu hanya bisa dilunasi dengan dua koin 1. Satu tandingan kecil sudah cukup untuk menyimpulkan bahwa kriteria koin terbesar tidak memiliki sifat pilihan greedy untuk pecahan ini.

Kesalahan umum#

Mengurutkan menurut waktu mulai paling awal. Kegiatan panjang yang mulai lebih dulu menghalangi dua kegiatan pendek setelahnya, seperti piket ruangan 0 sampai 6 yang menutup rapat pagi dan presentasi. Perbaikannya satu kata, yaitu urutkan menurut waktu selesai, karena waktu selesai yang menentukan ruang sisa.
Mempercayai kriteria tanpa pembuktian. Jawaban yang tampak benar pada beberapa contoh bukan bukti. Jalankan pencarian lengkap pada masukan kecil sebagai pembanding, atau susun argumen penukarannya, sebelum kriteria dipakai pada masukan besar.
Menyimpulkan greedy selalu buruk. Kegagalan pada pertukaran koin tidak membatalkan keberhasilan pada pemilihan kegiatan. Kedua soal punya struktur berbeda, sehingga alatnya dipilih per soal, bukan per kesan.
Membandingkan waktu mulai kegiatan dengan nol, bukan dengan akhir kegiatan terakhir. Gejalanya seluruh kegiatan lolos ujian pertama lalu saling menabrak satu sama lain. Batas pembandingnya harus variabel yang bergerak seiring pilihan, bukan titik tetap awal hari.

Ringkasan#

Greedy mengambil pilihan lokal terbaik tanpa menariknya kembali, cepat tetapi menuntut bukti bahwa pilihan itu aman.
Argumen penukaran membuktikan pilihan greedy setidaknya sama baiknya dengan pilihan mana pun dalam solusi optimal.
Pemilihan kegiatan terbukti optimal dengan kriteria selesai paling awal, pada Python maupun Java.
Pecahan 1, 3, 4 untuk nilai 6 menghasilkan tiga koin dengan greedy melawan dua koin optimal, bukti bahwa kriteria koin terbesar tidak berlaku di sini.

Referensi#

Greedy algorithm — Wikipedia — definisi greedy, sifat pilihan greedy, dan contoh soal yang bisa diselesaikan dengan satu lintasan.
Activity selection problem — Wikipedia — soal pemilihan kegiatan dengan kriteria selesai paling awal beserta pembuktiannya.