Menurut Munir, Rinaldi
(2004), dalam Bahasa Inggris, greedy berarti
rakus, tamak, atau loba. Definisi ini sangat sesuai dengan prinsip algoritma greedy, yaitu “take what you
can get now!”. Prinsip ini menggambarkan algoritma greedy yang
akan mengambil keputusan yang terbaik
pada setiap langkah penyelesaian, tanpa memperhitungkan akibatnya pada
keseluruhan permasalahan. Akan tetapi, agar algoritma
greedy benar-benar dapat
menyelesaikan masalah optimasi, pada setiap langkah harus dibuat keputusan
terbaik. Algoritma greedy merupakan salah satu algoritma yang sering digunakan untuk
memecahkan permasalahan optimasi. Dengan membuat pilihan Pada setiap langkah,
kita harus membuat pilihan optimum lokal (local
optimum), yang dapat diartikan sebagai keputusan terbaik yang diambil pada
langkah tersebut.
Karena algoritma greedy
biasanya dilakukan dalam beberapa
langkah, maka dalam satu permasalahan optimasi kita akan membuat beberapa pilihan optimum lokal, sesuai dengan
banyaknya langkah yang harus dilakukan. Diharapkan bahwa setiap kali diambil
pilihan optimum lokal, langkah-langkah setelahnya akan mengarah ke solusi
optimum global. Perlu diingat bahwa algoritma
greedy hanya memakai dua macam
persoalan optimasi, yaitu maksimasi (maximization)
dan minimasi (minimization).
Pada algoritma greedy, ada beberapa elemen yang harus diperhatikan,
yaitu:
1.
Himpunan kandidat (c)
himpunan ini berisi elemen-elemen pembentuk solusi.
2.
Himpunan solusi (s)
himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi dari permasalahan optimasi yang akan diselesaikan.
3.
Fungsi seleksi fungsi ini
akan memilih kandidat yang paling memungkinkan untuk mencapai solusi optimal.
Sesuai dengan prinsip algoritma greedy, kandidat yang sudah dipilih pada
suatu langkah tidak bisa diubah di langkah selanjutnya.
4.
Fungsi kelayakan fungsi
ini akan memeriksa kelayakan suatu kandidat yang telah dipilih. Dalam arti,
kandidat tersebut dan himpunan solusi yang terbentuk tidak melanggar constraints yang ada. Bila kandidat
layak, maka kandidat tersebut akan dimasukkan ke dalam himpunan solusi, dan
jika kandidat tersebut tidak layak, maka kandidat akan dibuang dan tidak akan
dipertimbangkan lagi dalam pencarian
solusi optimum.
5.
Fungsi obyektif fungsi ini
akan membuat nilai solusi maksimum atau minimum, sesuai dengan jenis optimasi apa yang dibutuhkan.
Dengan kata lain, algoritma
greedy akan melakukan pencarian sebuah himpunan bagian s dari himpunan
kandidat c. himpunan bagian s harus memenuhi
beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan s
dioptimisasi oleh fungsi obyektif. (http://informatika.stei.itb.ac.id/~rinaldi
.munir/Stmik/20132014genap/Algoritma%20Greedy%20(2004).ppt).
Rumus untuk menentukan
lintasan terpendek dengan Algoritma
Greedy sebagai berikut:
(1). Menentukan titik awal
dan titik tujuan, misalnya titik awal a.
(2). Periksa semua sisi
yang langsung bersisian dengan simpul a, pilih sisi yang bobotnya terkecil. Sisi
ini menjadi lintasan terpendek pertama, sebut saja L (1).
(3). Tentukan lintasan terpendek kedua dengan cara
berikut :
a. hitung: D (i) = panjang
L (1) + bobot sisi dari simpul akhir L (1) ke simpul i yang lain.
b. pilih D (i) yang terkecil.
c. Bandingkan D (i) dengan
bobot sisi (a, i). Jika bobot sisi (a, i) lebih kecil daripada D (i), maka L (2)
= L (1) U (sisi dari simpul akhir L (i) ke simpul D (i).
(4). Dengan cara yang
sama, ulangi langkah (2) untuk menentukan lintasan terpendek berikutnya (Henny Syahriza Lubis, 2009).
Belum ada tanggapan untuk "algoritma greedy"
Post a Comment