Definisi Algoritma Greedy dan Contoh Program

Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”
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.

Sumber :
http://topaninfo.blogspot.com/2012/12/Algoritma-GREEDY-Definisi-Contoh-Program.html#comment-form

Contoh Program :

#include <cstdlib>
#include <iostream>
#define size 99

using namespace std;

void PenjadwalanPelanggan(int n);

int main(int argc, char *argv[]){

int i;
int n;

cout<<"Masukkan jumlah Pelanggan : ";
cin>>n;
for (i=0; i<=n; i++){
cout<<" Pelanggan "<< i <<" dilayani "<<endl;
}

system("PAUSE");
return EXIT_SUCCESS;
}

Program Pencocokan String

Algoritma

procedure PencocokanString(input P : string, T: string, n, m : integer, output idx : integer)
{ Masukan: pattern P yang panjangnya m dan teks
T yang panjangnya n. Teks T direpresentasika
sebagai string (array of character)
Keluaran: lokasi awal kecocokan (idx)
}
Deklarasi
i : integer
ketemu : boolean
Algoritma:
i <-- 0
ketemu <-- false
while (i <-- n-m) and (not ketemu) do
j <-- 1
while (j <-- m) and (Pj = Ti+j ) do
j <-- j+1
endwhile
{ j > m or Pj <-- Ti+j }
if j = m then { kecocokan string
ditemukan }
ketemu <-- true
else
i <-- i+1 {geser pattern satu karakter ke
kanan teks }
endif
endfor
{ i > n – m or ketemu }
if ketemu then
idx <-- i+1
else
idx <-- -1
endif

Program

#include <cstdlib>
#include <iostream>

using namespace std;

void PencocokanString( string P, string T, int n, int m, int idx){
int i;
int j;
bool ketemu;


i = 0;
ketemu = false;
while (( i <= n - m ) && ( ! ketemu)){
j == 1;
while (( j <= m ) && ( P[j] = T[i + j])){
j = j + 1;
}
//{ j > m or P[j] =! T[i + j]}
if ( j == m ){
ketemu = true;
}else {
i = i + 1;
}
}
//{ i > n - m or ketemu }
if ( ketemu ){
idx = i + 1;
}else{
idx = -1;
}
}
int main(int argc, char *argv[])
{
int idx;
string T;
string P;
cout<<"Masukkan teks = ";
cin>>T;
cout<<"Masukksn kata yang dicari (pattern) = ";
cin>>P;
cout<<"Ditemukan di karakter ke = "<<idx;

cout<<endl;

system("PAUSE");
return EXIT_SUCCESS;

}

Running

Program Bilangan Prima

Algoritma

Program Prima{
faktor bilangan bulat N, tampilkan TRUE jika Prima FALSE jika bukan.
Deklarasi :
n : int
Prima : boolean
i : int
fak : int
Deskripsi :
for i <-- 2 to n do
if n mod i = 0 then
fak <-- fak+1
endif
endfor
if fak = 2 then
Prima <-- TRUE
else
Prima <-- FALSE
write (Prima)

Program
#include <cstdlib>
#include <iostream>

using namespace std;

bool Prima(int n){
int i, fak;
bool prima;

fak=1;

for ( i = 2; i <= n; i++){
if ( n % i == 0 ){
fak = fak + 1;
}
}
if ( fak == 2 ){
prima = true;
}else{
prima = false;
}

return prima;
}
int main(int argc, char *argv[])
{
int x;
cout << "Masukkan bilangan : ";
cin >> x;
if ( Prima(x) == 0 ){
cout << "Bilangan " << x << " bukan bilangan prima" <<endl;
}
else{
cout << "Bilangan " << x << " adalah bilangan prima" <<endl;
}
system("pause");
return 0;
}



Running

Program Brute Force Pangkat

#include <cstdlib>
#include <iostream>

using namespace std;
int pangkat (int a, int n){
int k,hasil;
hasil = 1;
for (k = 1;k <= n;k++){
hasil = hasil*a;
}
return hasil;
}

int main(int argc, char *argv[])
{
int a,n;
cout<<"Masukkan angka :";cin>>a;
cout<<endl;
cout<<"Masukkan pangkat :";cin>>n;
cout<<endl;
cout<<"Hasil perpangkatan = "<<pangkat(a,n);
cout<<"\n";

cout<<endl;
system("PAUSE");
return EXIT_SUCCESS;
}

Running

Menentukan nilai max-min dari n bilangan bulat

Deklarasi
Angka : integer
N : integer
max : integer
Min : integer
Deskripsi
Read (n)
Max ß1;
Min ß1;
For iß 1 to n do
Read(angka);
If (angka==1) ;
Max=angka; Min=angka; endif
Else if (max<angka)
Max=angka; endif
Else if (min>angka)
Min=angka; endif
End for


Program mencari nilai maximum dan minimum

#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[]){


int angka,n, max=1, min=1;
cout << " nilai terbesar dan terkecil" << endl;
cout << endl;
cout << "Masukkan bilangan yang diinputkan: ";
cin>>n;
for ( int i =1;i<=n;i++){
cout << "Masukkan Angka : ";
cin>>angka;
if ( i == 1 ) {
min = angka;
max = angka;}
else if ( min > angka ) {
min = angka; }
else if ( max < angka) {
max = angka;
} }
cout << "Nilai terkecil : " << min << endl;
cout << "Nilai terbesar : " << max << endl;
system("pause");
return 0;
}

Running

Program Tukar Bilangan

Algoritma

Deklarasi :
A : int (nilai pertama)
B : int (nilai kedua)
temp : int (variabel pembantu)

Deskripsi :
input (A,B)
temp <--A
A<--B
B<--temp
output (A,B)

Program

#include <cstdlib>
#include <iostream>

using namespace std;

void tukar(int& A, int& B){
int temp = A;
A = B;
B = temp;
}

int main(int argc, char *argv[])
{
int bil1, bil2;
cout<<"Masukkan bilangan 1 :";cin>>bil1;
cout<<"Masukkan bilangan 2 :";cin>>bil2;
tukar (bil1,bil2);
cout<<endl;
cout<<"===Setelah Ditukar==="<<endl;
cout<<endl;
cout<<"Bilangan 1 = "<<bil1<<endl;
cout<<"Bilangan 2 = "<<bil2<<endl;

system("PAUSE");
return EXIT_SUCCESS;
}



Running