Algoritma Greedy

Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah program yang menyangkut persoalan 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.

1. Pengertian Algoritma Greedy
 Dalam arti 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

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. Elemen Algoritma Greedy

Elemen–elemen yang digunakan dalam penerapan algoritma greedy antara lain :

 
1. Himpunan Kandidat.
Himpunan yang berisi elemen pembentuk solusi. 

 
2. Himpunan Solusi.
Himpunan yang terpilih sebagai solusi persoalan. 

 
3. Fungsi Seleksi.
Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal. 

 
4. Fungsi Kelayakan.
Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada. 

 
5. Fungsi Solusi
Fungsi yang mengembalikan nilai boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap. 

 
6. Fungsi Objektif
Fungsi yang mengoptimalkan solusi.

3. Skema Umum Algoritma Greedy

1. Inisialisasi Himpunan Solusi dengan kosong. 

2. Pilih sebuah kandidat dari Himpunan Kandidat (dengan Fungsi Seleksi). 

3. Kurangi Himpunan Kandidat dengan kandidat yang telah terpilih di atas. 

4. Periksa apakah kandidat yang dipilih tersebut bersama – sama dengan Fungsi Seleksi membentuk solusi yang layak (dengan Fungsi Kelayakan). Jika ya, masukkan kandidat ke Himpunan Solusi; jika tidak buang kandidat tersebut dan tidak perlu ditelaah lagi.

5. Periksa apakah Himpunan Solusi yang sudah terbentuk telah memberikan solusi yang lengkap(dengan Fungsi Solusi). Jika ya, berhenti; jika tidak, ulangi dari langkah 2.

4. Study kasus

Sebagai contoh dari penyelesaian masalah yang sering dijumpai dalam kehidupan sehari-hari dengan algoritma greedy, mencari jarak terpendek dari peta. Misalkan kita ingin bergerak dari titik P ke titik R, dan kita telah menemukan beberapa jalur dari peta

Dari peta diatas maka kita bisa mencari jalur - jalur mana yang paling optimal dari kota P untuk menuju ke kota R menggunakan skema umum algoritma greedy.

1. langkah pertama yaitu ambil seluruh jalur yang bisa di lewati dari kota P.

2. lalu pilih jalur yang rute nya paling pendek dari semua jalur yang tadi sudah di ambil. dan buang         rute yang lainnya dari pilihan,

3. masukan jalur yang sudah di kunjungi ke himpunan solusi dan pindahkan posisi dari kota P ke             jalur yang baru.

4. lakukan langkah ke 2 dan ke 3 secara berulang hingga sampai ke kota R.

5. periksa apakah jalur - jalur yang ada dalam himpunan solusi sudah memberikan jalur yang tepat atau tidak; jika tidak ulangi dari langkah ke 2.

contoh lain ialah penukaran uang.

Misalkan tersedia koin : 1, 3, 5.

Uang senilai X=8 dapat di tukar dengan cara :
1+1+1+1+1+1+1+1 = 8 (8 koin)
1+1+1+1+1+3=8 (6 koin)
1+1+1+5=8 (4 koin)
1+1+3+3=8 (4 koin)
3+5=8 (2 koin) solusi optimal.

Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

5. Pseudocode algoritma greedy

contoh pseudocode penukaran koin.