Algoritma Greedy dan Implementasinya
Pada Program Java
Algoritma
greedy merupakan salah satu dari sekian banyak algoritma yang sering di
pakai dalam implementasi sebuah system atau program yang menyangkut mengenai
pencarian “optimasi”.
Di
dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah
macam persoalan Optimasi,yaitu:
1.
Maksimasi (maxizimation)
2.
Minimasi (minimization)
Solusi
optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari
sekumpulan alternatif solusi yang mungkin.
Elemen
persoalan optimasi:
1.
Kendala (constraints)
2.
Fungsi objektif (fungsi optiamsi)
Solusi
yang memenuhi semua kendala disebut solusi layak (feasible solution).
Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.
Algoritma
greedy merupakan metode yang paling populer untuk memecahkan persoalan
optimasi.
Greedy = rakus, tamak, loba, ….
Prinsip
greedy adalah: “take what you can get now!”.
Contoh
masalah sehari-hari yang menggunakan prinsip greedy:
- Memilih beberapa jenis investasi (penanaman modal)
- Mencari jalur tersingkat dari Bandung ke Surabaya
- Memilih jurusan di Perguruan Tinggi
- Bermain kartu remi
Pendekatan
yang digunakan di dalam algoritma greedy adalah membuat pilihan yang
“tampaknya” memberikan perolehan terbaik yaitu dengan membuat pilihan optimum
lokal (local optimum) pada setiap langkah dengan harapan bahwa
sisanya mengarah ke solusi optimum global (global optimm).
Algoritma
greedy adalah algoritma yang memecahkan masalah langkah per langkah pada
setiap langkah:
- Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)
- Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.
Pada
setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita
berharap optimum lokal menjadi 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).
Sekarang
kita lanjut ke contoh soal yang aja ya..biar lebih enak membedakan antara soal
mengenai optimasi/maksimasi dengan minimum/minimasi.
1.Persoalan
maksimasi
(
Masalah Penukaran Uang) Diberikan uang senilai A. Tukar A dengan koin-koin yang
ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
2. Persoalan
minimasi
Contoh1:
tersedia banyak koin 1, 5, 10, 25
Uang
senilai A = 32 dapat ditukar dengan banyak cara berikut:
32
= 1 + 1 + …+ 1 (32 koin)
32
= 5 + 5 + 5 + 5 + 10 + 1 + 1(7 koin)
32
= 10 + 10 + 10 + 1 + 1(5 koin)…dst
Minimum:
32 = 25 + 5 + 1 + 1 (4 koin)
Sebelum
ditutup artikel tentang algoritma greedy ini saya akan menjelaskan tentang apa yang
di pakai algoritma greddy dalam memecahkan masalah:
Algoritma
greedy dalam menyelesaikan masalah dengan langkah per langkah “bertahap” dengan
definisi pada setiap langkah algoritma greedy :
1.
Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan
konsekuensi kedepan (prinsip “take what you can get now!”)
2.
Berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir
dengan optimum global.
Implementasi Pada Program Java
Contoh penukaran koin :
Akan diberikan uang 450 dengan koin
yang ditukar adalah 100, 50, 25, dan 15 berapa solusi minimumnya???
Berikut contoh program untuk mencari
banyak koin degan menggunakan algoritma greedy.
import java.io.DataInputStream;
class algoritmaGreedy
{
public int i,j,k;
// konstruktor
algoritmaGreedy(){
}
// method untuk proses algoritma greedy
void Greedy(int koin[], int hasil[],int jum[],
int uang, int i)
{
int s [] = new int[uang];
while(jum[i] < uang)
{
k=(int)(Math.random()*koin.length);
s[hasil[i]] = koin[k];
if((jum[i] + s[hasil[i]]) <= uang)
System.out.print(s[hasil[i]]+" ");
jum[i]+=s[hasil[i]];
hasil[i]+=1;
}
System.out.print(" ");
if (jum[i] == uang)
System.out.println(" = "+hasil[i]+" koin");
else
System.out.println(" = Tidak ada solusi");
}
// method sorting
void sorting(int data[], int n)
{
for(i=0;i<n-1;i++){
for(j=0; j<n-1;j++)
if(data[j]<data[j+1])
{
k=data[j];
data[j]=data[j+1];
data[j+1]= k;
}
}
}
// method untuk mencari solusi max n min
void solusiGlobal(int data[],int jum[], int
uang)
{
int bin[] = new int[data.length];
j=0;
for (i=0;i<data.length;i++)
{
if(jum[i]==uang){
bin[j]=data[i];
j+=1;
}
}
sorting(bin,bin.length);
k=0;
for(i=0;i<bin.length;i++)
if(bin[i] != 0)
k+=1;
System.out.println("nSolusi Minimum : "+bin[k-1]);
System.out.println("Solusi Maximum : "+bin[0]);
}
}
class main
{
public static void main (String[] args) throws
Exception
{
DataInputStream entri = new DataInputStream(System.in);
System.out.print("Masukan jumlah uang yg di tukar: ");
int uang = Integer.parseInt(entri.readLine());
System.out.print("Masukkan banyaknya koin: ");
int n = Integer.parseInt(entri.readLine());
int koin[] = new int[n];
for(int i = 0;i<n;i++)
{
System.out.print("Koin ke-"+(i+1)+" : ");
koin[i] = Integer.parseInt(entri.readLine());
}
System.out.print("Masukkan batas iterasi: ");
int batas = Integer.parseInt(entri.readLine());
int hasil[] = new int [batas];
int jum[] = new int [batas];
// instansiasi objek greedy
algoritmaGreedy g = new algoritmaGreedy();
for(int i =0;i<batas;i++)
{
System.out.print("nSolusi ke-"+(i+1)+" = (");
g.Greedy(koin,hasil,jum,uang,i);
}
g.solusiGlobal(hasil,jum,uang);
}
}
Komentar
Posting Komentar