Algoritma Greedy pert 3

Di materi greedy bagian sebelumnya, kita sudah bahas studi kasus dasar seperti coin change, activity selection, dan fractional knapsack. Nah, di bagian ini kita naik kelas sedikit, kita bahas greedy pada kasus yang lebih dekat dengan kebutuhan industri, khususnya yang berhubungan dengan optimasi, logistik, dan komputer modern.

 

📌 Studi Kasus 1: Optimasi Jaringan (Minimum Spanning Tree)

Ketika perusahaan internet seperti Telkom, Biznet, Indihome, atau penyedia jaringan global membangun jaringan kabel optik, mereka harus menentukan rute pemasangan kabel yang paling hemat biaya. Nah, di sinilah algoritma Greedy turun tangan melalui dua algoritma terkenal:

• Prim’s Algorithm
• Kruskal’s Algorithm

Dua algoritma ini menggunakan prinsip greedy: setiap langkah selalu memilih sisi (edge) dengan bobot paling kecil. Hasil akhirnya adalah pohon (tree) yang menghubungkan semua titik dengan biaya termurah.

Kenapa greedy cocok?

• karena bobot terkecil di setiap langkah berkontribusi pada total biaya terkecil
• masalah ini memiliki optimal substructure
• dan pilihan lokal terbaik memang memperbaiki solusi global

Ini diterapkan pada:

• desain jaringan internet
• pipa gas
• kabel listrik PLN
• jaringan komputer kampus

---

📌 Studi Kasus 2: Huffman Compression (Sebagai Sistem Kompresi File)

Kamu pasti pernah pakai ZIP, RAR, atau aplikasi seperti WinZip dan 7Zip. Di balik kompresi file, ada algoritma yang memanfaatkan greedy: Huffman Coding.

Huffman bekerja dengan memilih dua karakter yang paling jarang muncul, menggabungkannya, lalu mengulang terus sampai terbentuk pohon kode. Keputusannya selalu lokal: pilih dua frekuensi terkecil.

Ini termasuk contoh greedy yang dijamin optimal.

---

📌 Studi Kasus 3: Penjadwalan CPU (Shortest Job First)

Dalam sistem operasi, CPU harus memilih proses mana yang harus dijalankan dulu. Kalau kamu pakai HP, laptop, atau PC—sistem operasi menggunakan pendekatan greedy.

Salah satunya: Shortest Job First (SJF).

CPU memilih proses yang waktu eksekusinya paling pendek dulu. Ini terbukti mengurangi waktu tunggu rata-rata, dan sangat efisien.

---

📌 Studi Kasus 4: Mengatur Antrean Pesanan di Marketplace

Di marketplace seperti Shopee/Tokopedia, ada ribuan pesanan yang masuk. Sistem perlu memilih pesanan mana yang diproses dulu. Greedy sering digunakan untuk:

• memilih pesanan nilai tinggi dulu
• mengirim barang jarak terdekat dulu
• memproses pesanan yang paling cepat diselesaikan

Gampang, cepat, dan efektif.

---

19. Analisis Kompleksitas Algoritma Greedy

Salah satu alasan greedy disukai adalah karena kompleksitas waktunya sangat bagus. Secara umum, kompleksitas greedy adalah:

O(n log n) atau O(n)

Tergantung apakah perlu sorting atau tidak.

✔ Contoh Kompleksitas

Masalah Greedy	Kompleksitas
Activity Selection	O(n log n)
Fractional Knapsack	O(n log n)
Coin Change (dengan sorting)	O(n log n)
Huffman Coding	O(n log n)

Mayoritas algoritma greedy menggunakan sorting, sehingga kompleksitasnya biasanya O(n log n). Tapi ada juga yang hanya O(n), seperti memilih item terbesar tanpa sorting.

---

20. Kesalahan Umum Saat Menggunakan Greedy

Banyak siswa (dan bahkan programmer pemula) langsung memakai greedy tanpa analisis, padahal greedy tidak selalu benar. Kesalahan yang sering terjadi:

• Mengira greedy selalu optimal
• Tidak memeriksa sifat optimal substructure
• Menyelesaikan masalah knapsack 0/1 dengan greedy (pasti salah!)
• Mengambil keputusan lokal padahal masalah butuh analisis global

Jadi sebelum memakai greedy, pastikan:

• masalah punya greedy-choice property
• solusi optimal submasalah membentuk solusi optimal akhir

---

21. Contoh Soal HOTS Algoritma Greedy + Pembahasan

Sekarang kita masuk ke soal tingkat lanjut dengan pembahasan konsep dan alasan. Soal-soal ini cocok untuk latihan ujian atau penilaian akhir semester.

---

📌 HOTS 1 — Optimalisasi Energi

Sebuah robot memiliki kapasitas baterai 100 unit. Ada beberapa sumber energi (charger) dengan efisiensi berbeda:

A: memberi 40 energi dalam 10 detik
B: memberi 25 energi dalam 4 detik
C: memberi 10 energi dalam 2 detik

Robot ingin mengisi baterai secepat mungkin. Pilih sumber energi menggunakan pendekatan greedy.

Pembahasan:

Kita hitung rasio efisiensi energi per detik.

• A = 40/10 = 4
• B = 25/4 = 6.25
• C = 10/2 = 5

Urutan greedy: B → C → A

Greedy benar karena tujuan adalah “kecepatan” → pilih efisiensi tertinggi.

---

📌 HOTS 2 — Menghemat Biaya Logistik

Sebuah perusahaan ingin mengirim 10 paket ke 5 kota. Biaya pengiriman berbeda, dan perusahaan ingin menghemat biaya total.

Jika biaya per km dan jarak masing-masing kota diberikan, solusi greedy: pilih kota dengan jarak paling dekat dulu.

Tapi apakah selalu optimal? Tidak selalu! Jika kapasitas kendaraan terbatas, greedy bisa salah.

Diskusi seperti ini cocok untuk merangsang berpikir kritis siswa.

---

📌 HOTS 3 — Knapsack 0/1

Sering muncul soal seperti:

“Gunakan greedy untuk knapsack 0/1.”

Jawabannya: salah. Greedy tidak cocok untuk knapsack 0/1.

Ini pertanyaan konsep penting untuk memastikan siswa paham kapan greedy digunakan.

---

22. Contoh Pseudocode + Penjelasan Greedy Lebih Kompleks

Kita ambil contoh: mencari jalur dengan nilai tertinggi. Mirip dengan beberapa game strategi sederhana.

Kasus:

Pemain ingin mengambil koin di peta. Ada 5 koin dengan nilai berbeda. Strategi greedy: ambil koin bernilai terbesar yang bisa dijangkau.

Pseudocode:

START
coins = daftar koin
posisi = posisi pemain

WHILE ada koin tersisa:
    pilih koin dengan nilai paling besar
    jika koin dapat dijangkau:
        ambil
    else:
        hapus dari pilihan
END WHILE
END

Masalah seperti ini muncul pada AI sederhana dalam game.

---

23. Pemakaian Greedy oleh Perusahaan Besar

Greedy dipakai di perusahaan teknologi raksasa:

✔ Google

• pencarian rute (mengambil jalur tercepat saat ini)
• ranking iklan

✔ Meta (Instagram/Facebook)

• memilih postingan dengan skor engagement tertinggi
• memilih iklan paling relevan

✔ Uber / Grab

• matching driver–penumpang tercepat

✔ Netflix

• memilih rekomendasi yang paling mungkin ditonton (greedy)

Jadi jangan anggap greedy itu algoritma sepele. Ia adalah inti dari banyak sistem optimasi dunia nyata.

Andi Bronnanjar

Kualitas makhluk berdasarkan seberapa manfaat untuk sesama maupun lingkungan alam sekitar.

Bagikan Artikel ini