Penjelasan algoritma greedy: cara kerja, kode, dan contoh

Masalah yang diselesaikan algoritma greedy

Algoritma greedy menyasar masalah optimasi: memilih aktivitas terbanyak, memakai koin paling sedikit, membangun jaringan termurah, memampatkan file ke bit paling sedikit. Alih-alih menjelajahi setiap kombinasi, algoritma greedy mengurutkan atau memprioritaskan opsi dan memilih yang terbaik di setiap langkah. Biasanya hasilnya waktu O(n log n), sering hanya sebesar biaya pengurutan.

Bagian tersulitnya bukan kode, melainkan pembuktian. Banyak aturan greedy yang tampak wajar ternyata salah, jadi Anda harus membuktikan aturan itu benar atau mengujinya terhadap solusi brute-force.

Ide dasar dengan kata-kata sederhana

1. Temukan aturan yang meranking pilihan, misalnya "waktu selesai paling awal lebih dulu" atau "edge teringan lebih dulu".
2. Urutkan opsi berdasarkan aturan itu, atau simpan di priority queue.
3. Telusuri opsi dan ambil setiap opsi yang masih diizinkan oleh batasan.
4. Jangan pernah membatalkan pilihan.

Algoritma greedy benar bila dua sifat terpenuhi. Greedy-choice property: ada solusi optimal yang memuat pilihan greedy pertama. Optimal substructure: setelah pilihan itu diambil, sisa masalah adalah instans yang lebih kecil dari masalah yang sama. Pembuktian yang lazim adalah exchange argument: ambil solusi optimal mana pun dan tunjukkan bahwa menukar salah satu pilihannya dengan pilihan greedy tidak membuatnya lebih buruk.

Contoh: interval scheduling

Anda punya satu ruang rapat dan permintaan berikut (mulai, selesai): A (1, 4), B (3, 5), C (0, 6), D (5, 7), E (3, 9), F (5, 9), G (6, 10), H (8, 11). Pesan rapat sebanyak mungkin yang tidak saling tumpang tindih. Aturan greedy yang benar: selalu pilih rapat yang paling cepat selesai di antara yang mulai setelah rapat terakhir yang dipesan selesai.

Hasil: A, D, H, tiga rapat, yang merupakan jumlah maksimum. Mengapa berhasil: rapat yang paling cepat selesai menyisakan waktu paling banyak untuk yang lain, sehingga menggantikan rapat pertama pada jadwal optimal mana pun dengannya tidak pernah menimbulkan konflik.

Implementasi 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']

Contoh klasik kedua adalah fractional knapsack: bila Anda boleh mengambil sebagian barang, mengambil barang berdasarkan urutan nilai per satuan berat adalah optimal.

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

Ketika greedy gagal: counterexample

Kompleksitas waktu dan ruang

Ruang biasanya O(n) untuk salinan terurut atau heap. Jika input sudah terurut, banyak algoritma greedy berjalan dalam O(n).

Kapan memakai greedy dan penggunaannya di dunia nyata

• Gunakan greedy bila Anda bisa membuktikan greedy-choice property, atau bila jawaban aproksimasi yang cepat dapat diterima. Jika tidak, gunakan dynamic programming atau backtracking.
• Kompresi: Huffman coding membangun prefix code optimal dengan berulang kali menggabungkan dua simbol paling jarang; dipakai di dalam format seperti DEFLATE (ZIP, gzip, PNG).
• Jaringan: minimum spanning tree (Kruskal, Prim) dan routing jalur terpendek (Dijkstra).
• Penjadwalan: earliest deadline first, serta pemesanan ruangan atau mesin.
• Aproksimasi: untuk set cover, aturan greedy "pilih himpunan yang mencakup item belum tercakup terbanyak" tidak optimal tetapi dijamin berada dalam faktor logaritmik dari optimum.
• Soal wawancara: jump game, gas station, assign cookies, non-overlapping intervals, minimum number of arrows to burst balloons, task scheduler.