Algoritma Greedy
Pengertian Metode Greedy
Algoritma Greedy merupakan metode yang paling
populer untuk memecahkan persoalan optimasi.
Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi
optimum.
Persoalan optimasi hanya ada dua macam:
1 . Maksimasi (maximization)
2. Minimasi (minimization)
Solusi optimum
(terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan
alternatif solusi yang mungkin.
Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution).
Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.
Greedy = rakus, tamak, loba
Algoritma Greedy adalah algoritma yang memecahkan masalah
langkah per langkah;
pada setiap langkah:
1. mengambil
pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan
konsekuensi ke depan (prinsip “take what you can get now!”)
2. berharap bahwa
dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum
global.
Contoh Kasus optimasi:
( Masalah Penukaran Uang): Diberikan uang senilai A. Tukar A dengan
koin-koin uang yang ada. Berapa jumlah minimum koin
yang diperlukan untuk penukaran tersebut?
Contoh 1: tersedia banyak koin 1, 5, 10, 25
Uang senilai A = 32 dapat
ditukar dengan banyak cara berikut:
32 = 1 + 1 +
… + 1 (32
koin)
32 = 5 + 5 +
5 + 5 + 10 + 1 + 1 (7
koin)
32 = 10 + 10
+ 10 + 1 + 1 (5
koin)
… dst
Minimum: 32 = 25 + 5 + 1 + 1 (4 koin)
Skema Umum Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen
berikut:
· Himpunan kandidat.
Berisi elemen-elemen pembentuk solusi.
· Himpunan solusi
Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
· Fungsi seleksi (selection function)
Memilih kandidat yang paling memungkinkan
mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak
pernah dipertimbangkan lagi pada langkah selanjutnya.
· Fungsi kelayakan (feasible)
Memeriksa apakah suatu kandidat yang telah
dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut
bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar
kendala (constraints) yang ada. Kandidat yang layak dimasukkan
ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak
pernah dipertimbangkan lagi.
· Fungsi obyektif, yaitu fungsi yang
memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan,
keuntungan, dan lain-lain).
Pada masalah penukaran uang:
· Himpunan kandidat: himpunan koin yang merepresentasikan nilai
1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
· Himpunan solusi: total nilai koin yang dipilih tepat sama
jumlahnya dengan nilai uang yang ditukarkan.
· Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari
himpunan kandidat yang tersisa.
· Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih
tidak melebihi jumlah uang yang harus dibayar.
· Fungsi obyektif: jumlah koin yang digunakan minimum.
Materi Analisis Algortima : Algoritma Greedy
Pseudo-code Algoritma Greedy
procedure greedy(input K:
himpunan_kandidat;output S : himpunan_solusi)
{ menentukan solusi optimum dari persoalan optimasi dengan
algoritma greedy
Masukan: himpunan
kandidat K
Keluaran: himpunan solusi
S}
Deklarasi
x : kandidat
Algoritma:
S¬{} { inisialisasi S dengan
kosong }
while (belum SOLUSI(S)) and (K ¹{}
) do
x¬SELEKSI(K); { pilih sebuah kandidat
dari K}
K¬K –
{x} { elemen himpunan
kandidat berkurang satu }
if LAYAK(S È{x}) then
S¬S È{x}
endif
endwhile
{SOLUSI(S)
sudah diperoleh or K= {} }
Pada akhir setiap lelaran, solusi yang
terbentuk adalah optimum lokal.
Pada akhir kalang while-do diperoleh optimum
global.
Warning: Optimum global belum tentu merupakan solusi optimum (terbaik),
tetapi sub-optimum atau pseudo-optimum.
Alasan:
1. Algoritma Greedy tidak beroperasi
secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada
metode exhaustive search).
2. Terdapat beberapa fungsi SELEKSI yang
berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma menghasilkan
solusi optiamal.
Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang optimal.
Contoh 2: tinjau masalah penukaran uang.
(a) Koin: 5, 4, 3, dan 1
Uang yang ditukar = 7.
Solusi greedy: 7 = 5 + 1 + 1 ( 3 koin) à tidak optimal
Solusi optimal: 7 = 4 + 3 ( 2 koin)
(b) Koin: 10, 7, 1
Uang yang ditukar: 15
Solusi greedy: 15 = 10 + 1 + 1 + 1 + 1 + 1 (6 koin)
Solusi optimal: 15 = 7 + 7 +
1 (hanya 3 koin)
(c) Koin: 15, 10, dan 1
Uang yang ditukar: 20
Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 +
1 (6 koin)
Solusi optimal: 20 = 10 +
10 (2 koin)
Penyelesaian dengan algoritma greedy
Strategi greedy: Pada
setiap langkah, pilih koin dengan nilai terbesar dari himpunan koin
yang tersisa
Berikut Function penyelesaian masalah
penukaran koin menggunakan Algoritma Greedy.
function CoinExchange(input K :
himpunan_koin, A : integer) -> himpunan_koin
{ mengembalikan koin-koin yang total nilainya = A, tetapi jumlah
koinya minimum}
Deklarasi
S : himpunan_koin
x : koin
Algoritma
S <-- {}
while (∑(nilai semua koin di dalam S) ≠ A) and (C ≠ {} ) do
x
<-- koin yang mempunyai nilai terbesar
K
<-- K - {x}
if (∑(nilai semua koin di dalam S) + nilai koin x < A then
S <-- S ῡ {x}
endif
endwhile
if (∑( nilai semua koin di dalam 5) = A then
return
S
else
write('tidak
ada solusi')
endif
· Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan
himpunan koin dalam urutan yang menurun (noninceasing order).
· Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu menghasilkan solusi
optimal (lihat contoh sebelumnya).
Referensi :
