Algoritma Greedy merupakan merode yang paling populer
dalam memecahkan persoalan optimasi. Hanya ada dua macam persoalan optimasi,
yaitu maksimasi dan minimasi. Algoritma Greedy adalah algoritma yang memecahkan
masalah langkah per langkah. Pada setiap langkah, terdapat banyak pilihan yang
perlu dieskplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan
yang terbaik dalam menentukan pilihan. Pada setiap langkahnya merupakan
pilihan, untuk membuat langkah optimum lokal (local optimum) dengan harapan bahwa langkah sisanya mengarah ke
solusi optimum global (global optimum).
Prinsip dari Algoritma Greedy adalah “take
what you can get now”, mengambil pilihan yang terbaik yang dapat diperoleh
pada saat itu tanpa memperhatikan konsekuensi ke depan.
Skema Umum
Algoritma Greedy
Persoalan optimasi dalam konteks algoritma greedy disusun
oleh elemen-elemen sebagai berikut :
1.
Himpunan Kandidat, C.
Himpunan ini berisi elemen-elemen pembentuk
solusi. Pada setiap langkah, satu buah kandidat diambil dari himpunannya.
2.
Himpunan Solusi, S.
Himpunan ini berisi kandidat-kandidat yang
terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah
himpunan bagian dari himpunan kandidat.
3.
Fungsi Seleksi (selection function)
Fungsi ini dinyatakan dengan predikat
seleksi. Merupakan fungsi yang pada setiap langkahnya memilih kandidat yang
paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada
suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
4.
Fungsi Kelayakan (feasible)
Fungsi ini dinyatakan dengan predikat layak.
Fungsi kelayakan ini merupakan fungsi yang memeriksa apakah suatu kandidat yang
telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut
bersama-sama dengan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak
dimasukkan ke dalam himpunan solusi, sedangkan yang tidak layak dibuang dan
tidak pernah dipertimbangkan lagi.
5.
Fungsi Obyektif
Fungsi Obyektif ini merupakan sebuah fungsi
yang memaksimumkan atau meminimumkan nilai solusi.
Dengan kata lain, algoritma greedy melibatkan pencarian
sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini, S
harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi
dan S dioptimasi oleh fungsi obyektif.
Adakalanya, solusi optimum global yang diperoleh dari
algoritma greedy yang diharapkan sebagai solusi optimum dari persoalan, belum
tentu merupakan solusi optimum (terbaik), tetapi solusi sub-optimum atau pseudo-optimum.
Hal ini dikarenakan algoritma greedy tidak beroperasi secara menyeluruh
terhadap semua alternatif solusi yang ada dan terdapat beberapa fungsi seleksi
yang berbeda, yaitu jika fungsi seleksi tidak identik dengan fungsi obyektif
karena fungsi seleksi biasanya didasarkan pada fungsi obyektif. Sehingga harus
dipilih fungsi yang tepat jika menginginkan algoritma menghasilkan solusi
optimal atau nilai yang optimum. Jadi, pada sebagian masalah algoritma greedy
tidak selalu berhasil memberikan solusi yang benar-benar optimum, tetapi
algoritma greedy pasti memberikan solusi yang mendekati (approximation) nilai optimum.
Jika jawaban terbaik mutlak tidak diperlukan, maka
algortima greedy sering berguna untuk menghasilkan hampiran (approximation), daripada menggunakan
algoritma yang lebih rumit untuk menghasilkan solusi eksak. Bila algoritma
greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.
Berikut adalah
contoh pseudo-code Algoritma greedy :
Procedure greedy (input C : himpunan-kandidat, output S : himpunan-solusi) { Menentukan solusi optimum dari
persoalan optimasi dengan algoritma
greedy
Masukan : himpunan kandidat C
Keluaran : himpunan solusi S }
Deklarasi
x : kandidat;
Algoritma
S ß {} {inisialisasi S dengan kosong}
while (belum SOLUSI(S)) and (C ≠ {}) do
x ß SELEKSI (C); {pilih
sebuah kandidat dari C}
C ß C-{x} {elemen himpunan kandidat berkurang
satu}
if LAYAK(S U {x}) then
S ß S U {x}
endif
endwhile
{solusi(S)
sudah direroleh or C = {} }
Dalam
menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy.
pembuatan Prosedur Greedy dengan masukan berupa himpunan-kandidat dengan
variable C, dan keluaran berupa himpunan_solusi dengan variable S. Variabel x
dideklarasikan sebagai kandidat sementara yang di pilih.
Langkah
algoritma greedy : inisialisasi awal himpunan-solusi dengan kosong. Selama
himpunan solusi belum ditemukan dan himpunan-kandidat tidak kosong, maka akan
dilakukan pemilihan sebuah kandidat dari himpunan_kandidat untuk mengisi
variabel sementara x, sehingga i-rimpunan_kandidat menjadi berkurang satu dan
himpunan kandidat yang berkurang tadi menjadi himpunan kandidat yang baru. Jika
anggota himpunan_solusi merupakan anggota himpunan x, maka himpunan solusi yang
baru adalah anggota dari himpunan-solusi yang juga menjadi anggota dari
himpunan x. Himpunan _solusi sudah diperoleh atau himpunan-kandidat =himpunan
kosong (3; 1; 12).
Contoh
Algoritma Greedy pada Penukaran Uang
Persoalan :
Diberikan uang senilai A.
Tukar A dengan koin-koin
uang yang ada. Berapa jumlah minimum koin yang
diperlukan untuk penukaran tersebut ?
Contoh : tersedia koin-koin 1, 5, 10,
dan 25
Uang senilai 32 dapat ditukar dengan 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)
… dan seterusnya
Minimum : 32 = 25 + 5 + 1 + 1 hanya 4 koin
Strategi greedy yang digunakan adalah :
Pada setiap
langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa
dengan syarat (kendala) tidak melebihi nilai
uang yang ditukarkan.
Tinjau
masalah menukarkan uang 32 dengan koin 1, 5,10, dan 25:
Langkah
1 : pilih 1 buah koin 25 (Total = 25)
Langkah
2 : pilih 1 buah koin 5 (Total = 25 + 5
= 30)
Langkah
3 : pilih 2 buah koin 1 (Total = 25+5+1+1= 32)
Solusi :
Jumlah koin minimum = 4 (solusi optimal)
Pada setiap langkah di atas kita memperoleh optimum lokal, dan pada akhir algoritma kita memperoleh optimum global (yang pada contoh ini merupakan solusi optimum).
Pada masalah penukaran uang, elemen-elemen algoritma greedy-nya adalah :
1. Himpunan Kandidat : Himpunan koin yang merepresentasikan nilai 1, 5, 10,
25, paling sedikit mengandung satu koin untuk setiap nilai.
2. Himpunan Solusi : Total nilai koin yang dipilih tepat sama jumlahnya dengan
nilai uang yang ditukarkan.
3. Fungsi Seleksi : Pilihlah koin yang bernilai tertinggi dari himpunan
kandidat yang tersisa.
4. Fungsi Kelayakan : Memeriksa apakah nilai total dari himpunan koin yang dipilih
tidak melebihi jumlah uang yang harus dibayar.
5. Fungsi Obyektif : Jumlah koin yang digunakan minimum.
Contoh masalah
penukaran uang lainnya :
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, dan 1
Uang yang ditukar = 15
Solusi greedy : 15 = 10 + 1 + 1 +
1 + 1 + 1 (6 koin) à Tidak Optimal
Solusi optimal: 15 = 7 + 7 + 1 (3
koin)
c.
Koin : 15, 10, dan 1
Uang yang ditukar = 20
Solusi greedy : 20 = 15 + 1 + 1 +
1 + 1 + 1 (6 koin) à Tidak Optimal
Solusi optimal: 20 = 10 + 10 (3
koin)
Penyeselesaian dengan Exhaustive Search
Nilai uang yang ditukar :
A
Himpunan koin (multiset):
{d1, d2, …}.
Himpunan
solusi: X = {x1, x2, …, xn},
xi
= 1 jika di
dipilih, xi = 0 jika di tidak
dipilih.
·
Terdapat
2n kemungkinan solusi
-(nilai-nilai
X= {x1, x2, …, xn} )
·
Untuk
mengevaluasi fungsi obyektif= O(n)
·
Kompleksitas
algoritma exhaustive search seluruhnya= O(n⋅2n).
Berikut adalah
contoh pseudo-code penukaran uang
Algoritma greedy :
Algoritma CoinExchange(input C : himpunan_koin, A : integer)àhimpunan_koin
{ mengembalikan koin-koin yang total nilainya = A dengan jumlah minimum}
Deklarasi
x : koin
S : himpunan_koin
Algoritma
S ß {}
while (jumlah nilai semua koin di dalam S <> A ) and (C <> {}) do
x ß koin dengan nilai terbesar
C ß C – {x}
if (jumlah nilai semua koin di dalam S) + nilai koin x < A then
S ß S U {x}
endif
endwhile
if (jumlah nilai semua koin di dalam S) = A then
return S
else
write(‘tidak ada solusi’)
endif
Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan menurun (nononceasing order). Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n). Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu menghasilkan solusi optimal.
Sumber :
Bahan Kuliah Algoritma Greedy oleh Rinaldi Munir
http://repository.upi.edu/2676/6/S_MTK_0900626_Chapter3.pdf
