Algoritma greedy adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah:
1. mengambil pilihan yang terbaik yang dapat diperoleh saat itu
2. berharap bahwa dengan memilih optimum loklal pada setiap langkah akan mencapai optimum global.
Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global.
Prinsip algoritma greedy adalah: “take what you can get now!”.
Secara umum, algoritma greedy memiliki 5 elemen :
1. Himpunan kandidat, C.
Himpunan ini berisi elemen pembentuk solusi.
2. Himpunan solusi, S.
Berisi kandidat yang terpilih sebagai solusi persoalan.
3. Fungsi seleksi.
Fungsi yang memilih kandidat terpilih untuk ditambahkan ke dalam solusi.
4. Fungsi kelayakan
Fungsi yang memeriksa apakah suatu kandidat dapat digunakan untuk memberikan solusi. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak dipertimbangkan lagi.
5. Fungsi obyektif
Fungsi yang memaksimumkan atau meminimumkan solusi.
Masalah yang cocok dalam menggambarkan algoritma greedy adalah pada masalah penukaran uang koin. Seseorang memiliki uang koin yang bernilai 32, dan akan di tukar dengan nilai uang pada himpunan 1,5,10, dan 25. Terdapat berbagai cara untuk mendapatkan koin dengan nilai 32. Dengan menggunakan algoritma greedy, kombinasi yang diperoleh adalah :
1. Sebuah koin 25,
2. Sebuah koin 5,
3. Dan 2 buah koin 1.
elemen-elemen greedy pada kasus penukaran koin :
1. Himpunan kandidat : koin yang merepresentasikan nilai 1,5,10,25, paling sedikit mengandung satu koin untuk setiap nilai
2. Himpunan solusi : koin yang terpilih sehingga total nilai koin seluruhnya tepat sama jumlahnya dengan nilai uang yang ditukarkan.
3. Fungsi seleksi : pilih koin yang nilai nya paling tinggi dari himpunan kandidat yang tersisa.
4. Fungsi layak : periksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
5. Fungsi obyektif : jumlah koin yang digunakan minimum
-------------------------------------------------------------------------------------------
berikut algoritmanya :
function penukaran_koin(input c : himpunan_koin, A : integer) → himpunan_koin
{mengembalikan koin-koin yang total nilainya = A, tetapi jumlah koinnya minimum}
Deklarasi
s : himpunan_koin
x : koin
Algoritma
s ← {} //inisialisasi var S dengan Kosong
while (Σ(nilai semua koin di dalam s) ≠ A) and (c ≠ {} ) do //memeriksa apakah sudah //di temukan solusinya atau tidak.
x ← koin yang mempunyai nilai terbesar //x merupakan nilai koin terbesar dari himpunan kandidat
c ← c - {x} //kurangi c dengan x
if (Σ(nilai semua koin di dalam s) + nilai koin x ≤ A then //perikasa apakah kandidat
s ← s ∪ {x} //yg terpilih membentuk
endif // solusi yang layak jika
endwhile // ya maka masukan.
{mengembalikan koin-koin yang total nilainya = A, tetapi jumlah koinnya minimum}
Deklarasi
s : himpunan_koin
x : koin
Algoritma
s ← {} //inisialisasi var S dengan Kosong
while (Σ(nilai semua koin di dalam s) ≠ A) and (c ≠ {} ) do //memeriksa apakah sudah //di temukan solusinya atau tidak.
x ← koin yang mempunyai nilai terbesar //x merupakan nilai koin terbesar dari himpunan kandidat
c ← c - {x} //kurangi c dengan x
if (Σ(nilai semua koin di dalam s) + nilai koin x ≤ A then //perikasa apakah kandidat
s ← s ∪ {x} //yg terpilih membentuk
endif // solusi yang layak jika
endwhile // ya maka masukan.
if (Σ(nilai semua koin di dalam s) = A then
return s
else
write(tidak ada solusi untuk penukaran koin ini’)
endif
return s
else
write(tidak ada solusi untuk penukaran koin ini’)
endif
0 Comments
