Teknik Desain · Pelajaran 5 dari 10
Greedy dan bukti kebenarannya
10 menit baca · BelajarCode
Algoritma greedy mengambil pilihan yang terlihat terbaik di setiap langkah. Greedy cepat dan sederhana, tetapi hanya benar untuk masalah yang punya dua sifat:
- Sifat pilihan greedy: ada solusi optimal yang memuat pilihan greedy pertama.
- Substruktur optimal: setelah pilihan pertama, sisa masalahnya berbentuk sama dan solusi optimalnya ikut membentuk solusi optimal keseluruhan.
Pemilihan kegiatan
Diberikan kegiatan dengan waktu mulai dan selesai. Pilih sebanyak mungkin kegiatan yang tidak saling tumpang tindih.
1def pilih_kegiatan(kegiatan):2 terurut = sorted(kegiatan, key=lambda k: k[1])3 terpilih = []4 akhir = float("-inf")5 for mulai, selesai in terurut:6 if mulai >= akhir:7 terpilih.append((mulai, selesai))8 akhir = selesai9 return terpilih1011kegiatan = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]12print(pilih_kegiatan(kegiatan))[(1, 4), (5, 7), (8, 11), (12, 16)]
Bukti dengan argumen pertukaran. Misalkan g adalah kegiatan yang selesai paling awal, dan O adalah solusi optimal sembarang. Ambil kegiatan pertama di O, sebut o. Karena g selesai paling awal, g selesai tidak lebih lambat dari o. Ganti o dengan g di O: hasilnya tetap tidak tumpang tindih (semua kegiatan lain di O mulai setelah o selesai, jadi juga setelah g selesai) dan banyaknya sama. Jadi selalu ada solusi optimal yang memuat g. Setelah memilih g, sisanya adalah masalah yang sama untuk kegiatan yang mulai setelah g selesai. Dengan induksi, greedy menghasilkan solusi optimal.
Kode Huffman
Kode Huffman memampatkan teks dengan memberi kode biner pendek untuk karakter yang sering muncul. Algoritmanya greedy: gabungkan berulang kali dua simpul dengan frekuensi terkecil.
1import heapq2from collections import Counter34def huffman(teks):5 frekuensi = Counter(teks)6 heap = [(f, i, karakter) for i, (karakter, f) in enumerate(sorted(frekuensi.items()))]7 heapq.heapify(heap)8 nomor = len(heap)9 while len(heap) > 1:10 f1, _, kiri = heapq.heappop(heap)11 f2, _, kanan = heapq.heappop(heap)12 heapq.heappush(heap, (f1 + f2, nomor, (kiri, kanan)))13 nomor += 114 kode = {}15 def jelajah(simpul, awalan):16 if isinstance(simpul, str):17 kode[simpul] = awalan or "0"18 return19 jelajah(simpul[0], awalan + "0")20 jelajah(simpul[1], awalan + "1")21 jelajah(heap[0][2], "")22 return kode, frekuensi2324teks = "abracadabra"25kode, frekuensi = huffman(teks)26for karakter in sorted(kode, key=lambda k: (-frekuensi[k], k)):27 print(karakter, frekuensi[karakter], kode[karakter])28panjang = sum(len(kode[k]) for k in teks)29print(f"Total {panjang} bit, dibanding {len(teks) * 8} bit dengan ASCII")a 5 0 b 2 110 r 2 111 c 1 100 d 1 101 Total 23 bit, dibanding 88 bit dengan ASCII
Karakter "a" yang paling sering muncul mendapat kode terpendek. Huffman terbukti optimal di antara kode prefiks, juga dengan argumen pertukaran.
Greedy yang terlihat benar bisa salah
Untuk masalah knapsack 0/1 (barang tidak bisa dipecah), greedy berdasarkan nilai per berat tidak selalu optimal. Selalu cari bukti atau contoh tandingan sebelum memakai greedy.
Cek pemahaman
Apa inti argumen pertukaran dalam membuktikan algoritma greedy?
Latihan
Contoh tandingan knapsack
Tunjukkan dengan program bahwa greedy "ambil barang dengan nilai per berat tertinggi" gagal untuk knapsack 0/1 dengan kapasitas 50 dan barang (berat, nilai): (10, 60), (20, 100), (30, 120). Bandingkan dengan brute force.
Pembahasan
1from itertools import combinations23barang = [(10, 60), (20, 100), (30, 120)]4kapasitas = 5056terurut = sorted(barang, key=lambda b: b[1] / b[0], reverse=True)7berat = nilai = 08for b, v in terurut:9 if berat + b <= kapasitas:10 berat += b11 nilai += v12print("Greedy:", nilai)1314terbaik = 015for r in range(len(barang) + 1):16 for pilihan in combinations(barang, r):17 if sum(b for b, _ in pilihan) <= kapasitas:18 terbaik = max(terbaik, sum(v for _, v in pilihan))19print("Optimal:", terbaik)Greedy: 160 Optimal: 220
Greedy mengambil barang 10 kg dan 20 kg (nilai 160), lalu barang 30 kg tidak muat. Solusi optimal justru mengambil 20 kg dan 30 kg (nilai 220).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.