ALGORITMA GREEDY
Algoritma Greedy merupakan metode yang paling
popular untuk memecahkan persoalan optimasi, mencari nilai maksimum sementara
dengan harapan akan mendapatkan solusi yang cukup baik. Meskipun tidak selalu
mendapatkan solusi yang terbaik (optimum), algoritma ini umumnya memiliki
kompleksitas waktu yang cukup efesien, sehingga algoritma ini sering digunakan
untuk kasus yang memerlukan solusi yang cepat
walaupun tidak optimal.
Algoritma
ini memiliki beberapa fungsi dasar, yaitu :
- Fungsi untuk melakukan penelusuran masalah.
- Fungsi untuk memilih local maximum dari pilihan-pilihan yang ada tiap langkahnya.
- Fungsi untuk mengisikan nilai local maximun ke solusi keseluruhan.
- Fungsi yang menentukan apakah solusi telah didapatkan.
Contoh
masalah sehari-hari menggunakan prinsip greedy :
- Memilih beberapa jenis investasi (penanaman modal)
- Mencari jalur tersingkat
- Memilih jurusan di perguruan tinggi
- Bermain kartu remi
Contoh
masalah menggukan pseudocode (Masalah Penukaran Koin):
Persoalan: Diberikan uang senilai A. Tukar A dengan
koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
(Minimum: 32 = 25 + 5 + 1 + 1) hanya 4 coin
(Minimum: 32 = 25 + 5 + 1 + 1) hanya 4 coin
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!)
Pseudocode algoritma greedy adalah sebagai berikut:
Function greedy(input C: himpunan_kandidat) himpunan_kandidat
Mengembalikan solusi dari persoalan optimasi dengan algoritma greedy
Masukan: himpunan kandidat C
Keluaran: himpunan solusi yang bertipe himpunan_kandidat
Deklarasi
Pseudocode algoritma greedy adalah sebagai berikut:
Function greedy(input C: himpunan_kandidat) himpunan_kandidat
Mengembalikan solusi dari persoalan optimasi dengan algoritma greedy
Masukan: himpunan kandidat C
Keluaran: himpunan solusi yang bertipe himpunan_kandidat
Deklarasi
x : kandidat
S : himpunan_kandidat
Algoritma:
S ¬ {} { inisialisasi S dengan kosong }
while (not 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) or C = {} }
if SOLUSI(S) then
return S
else
write(’tidak ada
solusi’)
endif
Sumber
Referensi:
