Pengertian
Greedy atau istilah lainnya rakus,
tamak, loba adalah sejenis algoritma yang
menggunakan cara dengan mendekati pada pemecahan persoalan tersebut dengan
mencari nilai maksimum pada setiap langkahnya. Algoritma Greedy adalah algoritma yang
memecahkan persoalan secara step by step.
Greedy memilki
sifat take what you can get now. Pada greedy juga berharap
bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan
optimum global. Pada greedy terdapat persoalan yang disebut dengan persoalan
optimasi.
Persoalan optimasi memiliki dua
macam yaitu :
1. Maksimasi(Maximization)
2. Minimasi(Minimization)
Mencari solusi optimum yang terbaik
adalah yang memiliki solusi yang memiliki nilai minimum atau maksimum dari sekelompok
solusi yang mungkin. Solusi yang terpenuhi semua kendala adalah solusi layak. sedangkan solusi layak
yang mengoptimasikan fungsi optimasi disebut solusi optimasi.
Greedy memiliki rangka atau langkah dasar nya berikut adalah dasar – dasar nya :
- Himpunan kandidat.
Yaitu
berisi tentang pembentukan solusi.
- Himpunan solusi
Yaitu berisi kandidat-kandidat yang
terpilih dari penyeleksian sebagai solusi
persoalan.
- Fungsi seleksi
Memilih
kandidat yang munkin menjadi solusi optimal. Dan Kandidat yang sudah dipilih tidak
dibandingkan lagi pada langkah
selanjutnya.
- Fungsi kelayakan
Memeriksa
kandidat yang telah dipilih dapat memberikan solusi yang layak, yaitu kandidat dan
himpunan solusi tidak melanggar kendala yang ada. Kandidat yang layak masuk ke
himpunan solusi, sedangkan kandidat yang tidak layak dibuang.
- Fungsi obyektif
Yaitu fungsi yang memaksimumkan atau
meminimumkan nilai solusi.
Berikut adalah
algoritma umum greedynya:
procedure greedy(input
C: himpunan_kandidat; output S : himpunan_solusi)
Deklarasi
x : kandidat;
Algoritma:
S¬{} {
inisialisasi S dengan null atau kosong }
while (belum
SOLUSI(S)) and (C ¹ {}
) do
x¬SELEKSI(C);
C¬
C - {x}
if LAYAK(S ͜ {x}) then
S¬S
͜ {x}
endif
endwhile
{SOLUSI(S) sudah diperoleh atau C = {} }
Contoh Kasus
Greedy
dalam transportasi
Pertama terdapat
tabel alat pengakut dengan kapasitas 100 kg dengan 4 buah barang.
barang
|
berat
|
keuntugan
|
Massa jenis
|
1
|
24
|
68
|
2.913
|
2
|
46
|
87
|
1.911
|
3
|
65
|
147
|
2.074
|
4
|
39
|
42
|
1.076
|
Dengan
menggunakan algoritma greedy menghasilkan tabel
GB
|
GK
|
GM
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
109
|
206
|
206
|
keuntangan
GB:
greedy berat
GK:
greedy keuntungan
GM:
greedy Massa jenis
1 : barang yang
diangkut
0 : barang yang tidak
diangkut
Algoritma
Menghasilkan
solusi persoalan knapsack dengan algoritma greedy yang menggunakan strategi
pemilihan objek berdasarkan keuntungan (ki),berat(bi),masajenis (ki/bi). Solusi
dinyatakan sebagai
Asumsi:
Untuk Greedy by profit seluruh objek sudah terurut berdasarkan nilai ki yang menurun. Untuk
Greedy berat seluruh objek sudah terurut berdasarkan nilai bi yang menaik.Untuk
Greedy masajenis seluruh objek sudah terurut berdasarkan nilai ki/bi yang
menurun.
Algoritma
function greedyknapsack(input
C : himpunan_objek, K : real) → himpunan_solusi
deklarasi
Algoritma:
vektor A = a[1], a[2], …, a[n].
endfunction
procedure greedyangkut(input C: himpunan_objek, output
a : himpuan_solusi)
Deklarasi
i, BobotTotal
: integer
tersedia : boolean
a : himpunan_solusi
tersedia : boolean
a : himpunan_solusi
Algoritma:
for i ←
1 to n do
a[i]
← 0
endfor
i ←
0
BobotTotal
← 0
tersedia
← true
while (i
< n) and (tersedia) do
i ← i + 1
if BobotTotal + w[i] ← K then
a[i] ← 1
BobotTotal ← TotalBobot + w[i]
else
tersedia ← false
a[i] ← 0
endif
endwhile
endprocedure
Referensi
:
https://bertzzie.com/knowledge/analisis-algoritma/Greedy.html
http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html
Tidak ada komentar:
Posting Komentar