Algoritme rakus adalah pendekatan untuk memecahkan masalah dengan memilih opsi terbaik yang tersedia saat ini, tanpa mengkhawatirkan hasil yang akan diperoleh di masa mendatang. Dengan kata lain, pilihan terbaik lokal bertujuan untuk menghasilkan hasil terbaik secara global.

Algoritme ini mungkin bukan pilihan terbaik untuk semua masalah. Ini mungkin menghasilkan hasil yang salah dalam beberapa kasus.

Algoritma ini tidak pernah kembali untuk membalikkan keputusan yang dibuat. Algoritma ini bekerja dengan pendekatan top-down.

Keuntungan utama dari algoritma ini adalah:

1. Algoritmanya adalah lebih mudah untuk dijelaskan.
2. Algoritma ini bisa tampil lebih baik daripada algoritme lain (tetapi, tidak di semua kasus).

Solusi yang Layak

Solusi yang layak adalah yang memberikan solusi optimal untuk masalah tersebut.

Algoritma Greedy

1. Untuk memulainya, kumpulan solusi (berisi jawaban) kosong.
2. Di setiap langkah, item ditambahkan ke set solusi.
3. Jika set solusi layak, item saat ini disimpan.
4. Jika tidak, item tersebut ditolak dan tidak pernah dipertimbangkan lagi.

Contoh – Pendekatan Serakah

Problem: You have to make a change of an amount using the smallest possible number of coins.
Amount: $28

Available coins:
  $5 coin
  $2 coin
  $1 coin

Larutan:

1. Buat yang kosong solusi-set = {}.
2. koin = {5, 2, 1}
3. jumlah = 0
4. Sementara jumlah ≠ 28, lakukan hal berikut.
5. Pilih koin C dari koin seperti yang jumlah + C <28.
6. Jika C + jumlah> 28, tidak mengembalikan solusi.
7. Lain, jumlah = jumlah + C..
8. Menambahkan C untuk solusi-set.

Hingga 5 iterasi pertama, kumpulan solusi berisi 5 Koin $ 5. Setelah itu, kita dapatkan 1 Koin $ 2 dan akhirnya, 1 Koin $ 1.

Aplikasi Algoritma Greedy

• Sortir Pilihan
• Masalah Knapsack
• Pohon Rentang Minimum
• Masalah Jalur Terpendek Sumber Tunggal
• Masalah Penjadwalan Pekerjaan
• Algoritma Pohon Rentang Minimal Prim
• Algoritma Pohon Rentang Minimal Kruskal
• Algoritma Pohon Rentang Minimal Dijkstra
• Huffman Coding
• Algoritma Ford-Fulkerson