Algoritma GREEDY merupakan metode yang paling populer untuk memecahkan persoalan optimasi. Greedy sendiri diambil dari bahasa inggris yang artinya rakus , tamak atau serakah . Sehingga Algoritma Greedy dapat di definisikan algoritma yang memecahkan masalah langkah per langkah; pada setiap langkah dengan mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”) dan berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Kondisi yang harus dipenuhi:
Algoritma greedy membentuk solusi step by step dan terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.
- Terdapat kumpulan kandidat penyelesaian (solusi)
- Ada suatu cara/fungsi yang bisa memeriksa apakah satu kandidat betul merupakan solusi atau bukan
- Ada fungsi seleksi yang bisa memilih kandidat terbaik
- Ada sesuatu yang ingin dioptimalkan dalam persoalan yang dihadapi / ada objective function
Algoritma greedy membentuk solusi step by step dan terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya.
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.
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.
Skema Umum Algoritma Greedy :
Algoritma greedy disusun oleh elemen-elemen berikut:
1. Himpunan
kandidat.
Berisi elemen-elemen pembentuk solusi.
2. Himpunan
solusi
Berisi
kandidat-kandidat yang terpilih sebagai solusi
persoalan.
3. 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.
4. 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.
5. Fungsi
obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi
(misalnya panjang lintasan, keuntungan, dan lain-lain).
Contoh 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 layak:
memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi
jumlah uang yang harus dibayar.
5. Fungsi
obyektif: jumlah koin yang digunakan minimum.
Pseudo-code algoritma greedy adalah sebagai berikut:
|
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 È
{x}) then
S¬S È {x}
endif
endwhile
{SOLUSI(S) sudah diperoleh or C = {} }
|
Pada akhir setiap lelaran, solusi yang terbentuk adalah
optimum lokal. Pada akhir kalang while-do diperoleh optimum global.
Namun adakalanya optimum global merupakan solusi 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. pemilihan
fungsi SELEKSI: Mungkin saja terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja
dengan benar dan menghasilkan solusi yang benar-benar optimum
· Karena
itu, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan
solusi yang benar-benar optimum.
· Jika
jawaban terbaik mutlak (benar-benar optimum) tidak diperlukan, maka algoritma
greedy sering berguna untuk menghasilkan solusi yang menghampiri
(approximation) optimum, daripada menggunakan algoritma yang lebih rumit untuk
menghasilkan solusi yang eksak.
· Bila
algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara
matematis
Sumber Referensi :
Aryo Pinandito, ST, M.MT – PTIIK
Universitas Brawijaya
