Pengertian,Contoh Kasus Dan Pseudocode Algoritma Greedy

Pengertian

Greedy adalah satu dari sekian banyak algoritma yang ada ,greedy termasuk algoritma yang cukup populer karna banyak digunakan untuk menyelesaikan banyak persoalan .

Greedy merupakan algoritma untuk menyelesaikan dengan solusi terbaik dengan cara optimasi yaitu :

                1. Optimasi Maksimasi (maximization)
                2. Optimasi Minimasi (minimization)

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


CONTOH KASUS :

Minimisasi Waktu di dalam Sistem (Penjadwalan)

Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan sudah ditetapkan sebelumnya, yaitu pelanggan i membutuhkan waktu ti. Kita ingin meminimumkan total waktu di dalam sistem,

                T = (waktu di dalam sistem untuk pelanggan i)

Karena jumlah pelanggan adalah tetap, meminimumkan waktu di dalam sistem ekivalen dengan meminimumkan waktu rata-rata.

Misalkan kita mempunyai tiga pelanggan dengan

                t1 = 5,    t2 = 10, t3 = 3,

maka enam urutan pelayanan yang mungkin adalah:

Urutan                  T
=================================                                              
1, 2, 3:   5 + (5 + 10) + (5 + 10 + 3 ) = 38
1, 3, 2:   5 + (5 + 3) + (5 + 3 + 10) = 31
2, 1, 3:   10 + (10 + 5) + (10 + 5 + 3) = 43
2, 3, 1:   10 + (10 + 3) + (10 + 3 + 5) = 41
3, 1, 2:   3 + (3 + 5) + (3 + 5 + 10) = 29 ¬ (optimal)
3, 2, 1:   3 + (3 + 10) + (3 + 10 + 5) = 34

Pemecahan Masalah dengan Algoritma Exhaustive Search

Urutan pelangan yang dilayani oleh server merupakan suatu permutasi

Jika ada n orang pelanggan, maka tedapat n! urutan pelanggan. Waktu yang dibutuhkan untuk mengevaluasi fungsi obyektif adalah O(n), oleh karena itu kompleksitas algoritma exhaustive search untuk masalah ini adalah O(nn!)

Pemecahan Masalah dengan Algoritma Greedy

Strategi greedy untuk memilih pelanggan berikutnya adalah:

• Pada setiap langkah, masukkan pelanggan yang membutuhkan waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani. 

• Agar proses pemilihan pelanggan berikutnya optimal, maka perlu mengurutkan waktu pelayanan seluruh pelanggan dalam urutan yang menaik. Jika waktu pengurutan tidak dihitung, maka kompleksitas algoritma greedy untuk masalah minimisasi waktu di dalam sistem adalah O(n).

Algoritma :

procedure PenjadwalanPelanggan(input n:integer)

{ Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal

  Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n

  Keluaran: urutan pelanggan yang dilayani

}                              

Deklarasi

   i : integer

Algoritma:

  {pelanggan 1, 2, ..., n sudah diurut menaik berdasarkan ti}

  for i¬1 to n do

     write(‘Pelanggan ‘, i, ‘ dilayani!’)

  endfor   

Pseucode

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;

}

}

}

}