Dalam kehidupan sehari hari, banyak terdapat persoalan yang menuntut pencarian solusi optimum. Persoalan tersebut dinamakan persoalan optimasi(optimization Problems). Persoalan Optimasi adalah persoalan yang tidak hanya mencari sekedar solusi, tetapi mencari solusi terbaik.
Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer dalam hal ini.
Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :
- Memilih beberapa jenis investasi
- Mencari jalur tersingkat
Ada juga yang dapat dilakukan algoritma ini dalam sesuatu yang biasa
dilakukan mesyarakat modern, yaitu memilih spesifikasi komputer yang
terbaik dengan budget maksimum tertentu seperti yang akan dibahas dalam
makalah singkat ini.
1. Definisi Algoritma Greedy
Algoritma Greedy membentuk solusi langkah per langkah (step by step).
Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah
solusi, karenanya pada setiap langkah harus dibuat keputusann yang
terbaik dalam menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah lagi pada langkah
selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy
untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah
diletakkan dan dipasang maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.
2. Skema umum Algoritma Greedy
Algoritma greedy disusun oleh elemen-elemen berikut:
- Himpunan kandidat.
Berisi elemen-elemen pembentuk solusi.
- Himpunan solusi
Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
- 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.
- 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.
- Fungsi obyektif
yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi(misalnya
panjang lintasan, keuntungan, dan lain-lain).Contoh pada masalah
Pemilihan Processor, berdasarkan benchmark elemen-elemen algoritma
greedy-nya adalah:
a.Himpunan kandidat: himpunan hardware yang terdiri dari Processor, Memory dan Graphic card
b.Himpunan solusi: Kombinasi Processor , Memory dan Graphic card
dengan Benchmark terbaik namun dengan total harga yang tidak melebihi
budget maksimum
c.Fungsi seleksi: Seleksi Processor, Memory dan Graphic card agar mendapat performa optimum dan tidak melebihi budget maksimum yang tersedia
d.Fungsi obyektif: Budget maksimum yang tersedia
Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu:
Maksimasi (maxizimation)
Minimasi (minimization)
Sebagai contoh saja:
1.Persoalan maksimasi
( MasalahPenukaranUang): 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)
Cara kerja algoritma ini adalah dengan membuat suatu rangkaian
keputusan/pilihan, dimana masing masing merupakan pilihan pada posisi
tersebut. Sekali suatu keputusan dipilih, maka tidak ada jalan untuk melakukan backtracking. Bentuk umumnya adalah :
while (problem belum selesai)
{
buat pilihan terbaik yang feasible
}
Contoh penyelesaian menggunakan algoritma greedy ini adalah mencari pohon perentang minimum, baik menggunakan Prim maupun Kruskal
Pohon perentang minimum
Misalkan G = (V, E) adalah suatu graph tidak berarah, terhubung, dan
mempunyai bobot yang non negatif. Maka pohon perentang minimum adalah
subgraph G yang mempunyai sifat berupa pohon
Mengandung semua simpul pada G
Mempunyai jumlah bobot pada busur yang minimum.
Y = {v0} untuk setiap v0 ? V
while (Y = V )
{
Cari busur (u,v)dengan bobot minimum dengan u ? Y
dan v ?/ Y
Masukkan busur (u, v) pada MST
Tambahkan v pada Y
}
Kode programnya adalah sebagai berikut
for (i = 1; i <= n; i ++)
{
V [i] . Reached = FALSE;
V [i] . Connect_Wt = INFINITY;
}
V [Start] . Connect_Wt = 0;
V [Start] . Connect_From = 0;
for (i = 1; i <= n; i ++)
{
Min_Connect = INFINITY;
for (j = 1; j <= n; j ++)
if (V [j] . Connect_Wt < Min_Connect)
{
Min_Connect = V [j] . Connect_Wt;
Min_V = j;
}
V [Min_V] . Reached = TRUE;
for (j = 1; j <= n; j ++)
if (! V [j] . Reached
&& Weight [Min_V] [j]
< V [j] . Connect_Wt)
{
V [j] . Connect_Wt = Weight [Min_V] [j];
V [j] . Connect_From = Min_V;
}
}
Algoritma Kruskal
Tempatkan masing masing simpul sebagai himpunan terpisah
for ( setiap busur (u,v) yang diurutkan bobotnya secara ascending)
if (u dan v berada dalam himpunan terpisah)
{
Masukkan busur (u,v) dalam MST
gabungkan himpunan yang mengandung u dan v
}
Inilah potongan programnya :
for (i = 1; i <= n; i ++)
{
V [i] . Reached = FALSE;
V [i] . Connect_Wt = INFINITY;
}
V [Start] . Connect_Wt = 0;
V [Start] . Connect_From = 0;
for (i = 1; i <= n; i ++)
{
Min_Connect = INFINITY;
for (j = 1; j <= n; j ++)
if (V [j] . Connect_Wt < Min_Connect)
{
Min_Connect = V [j] . Connect_Wt;
Min_V = j;
}
V [Min_V] . Reached = TRUE;
for (j = 1; j <= n; j ++)
if (! V [j] . Reached
&& Weight [Min_V] [j]
< V [j] . Connect_Wt)
{
V [j] . Connect_Wt = Weight [Min_V] [j];
V [j] . Connect_From = Min_V;
}
}
contoh algoritma greedy pada C++ dengan contoh aplikasi penukaran koin logam
#include
#include
#define size 99
void sort(int[], int);
main()
{
int x[size],i,n,uang,hasil[size];
printf("\n Banyak Koin :");
scanf("%d", &n);
printf("\n \n Masukkan Jenis Koin : \n");
for(i=1;i<=n;i++)
{
scanf("%d", &x[i]);
}
sort(x,n);
printf("\n Koin yang Tersedia :");
for(i=1;i<=n;i++)
{
printf("%d", x[i]);
printf("\n");
}
printf("\n");
printf("\n Masukkan Nilai yang Dipecah :");
scanf("%d", &uang);
printf("\n");
for(i=1;i<=n;i++)
{hasil[i]=uang/x[i];
uang=uang%x[i];
}
for(i=1;i<=n;i++)
{
printf("Keping %d", x[i]);
printf("-an sebanyak : %d", hasil[i]);
printf("\n \n");
}
getch();
return 0;
}
void sort(int a[], int siz)
{
int pass,hold,j;
for(pass=1;pass<=siz-1;pass++)
{
for(j=0;j<=siz-2;j++)
{ if(a[j+1] < a[j+2])
{
hold=a[j+1];
a[j+1]=a[j+2];
a[j+2]=hold;
}
}
}
}
Tidak ada komentar:
Posting Komentar