Algoritma Greedy

Pengertian Metode Greedy dan Algoritma Greedy

Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah. Pada setiap langkah tersebut akan dipilih keputusan yang paling optimal. Keputusan tersebut tidak perlu memperhatikan keputusan selanjutnya yang akan diambil, dan keputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

a. Prinsip Utama Algoritma Greedy

Prinsip utama algoritma greedy adalah ?take what you can get now!?. Maksud dari prinsip tersebut adalah sebagai berikut: Pada setiap langkah dalam algoritma greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai optimum global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.

b. 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.

c. Skema Umum Algoritma Greedy

Misal kita mengasumsikan elemen algoritma greedy sebagai berikut :

Himpunan Kandidat = C,

Himpunan Solusi = S,

Fungsi Seleksi = select(),

Fungsi Kelayakan = feasible(),

Fungsi Solusi = solution(), dan

Fungsi Obyektif = objective().

Skema umum dari algoritma greedy dapat kita tuliskan :

- Inisialisasi S dengan kosong.

- Pilih sebuah kandidat dari C (dengan select()).

- Kurangi C dengan kandidat yang telah terpilih di atas.

- Periksa apakah kandidat yang dipilih tersebut bersama ? sama dengan S membentuk solusi yang layak (dengan feasible()). Jika ya, masukkan kandidat ke S; jika tidak buang kandidat tersebut dan tidak perlu ditelaah lagi.

- Periksa apakah S yang sudah terbentuk telah memberikan solusi yang lengkap (dengan solution()). Jika ya, berhenti; jika tidak, ulangi dari langkah 2.

Contoh kasus algoritma greedy :

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.

Knapsack Problem

Knapsack problem adalah suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang di mana setiap barang tersebut mempunyai berat dan profit masing masing, sehingga dari pemilihan barang tersebut didapatkan profit yang maksimum.

Contoh kasus knapsack

§  w₁ = 10;  p₁ = 2

§  w₂ = 5;     p₂ = 3

§  w₃ = 15;   p₃ = 5

§  w₄ = 7;     p₄ = 7

§  w₅ = 6;     p₅ = 1

§  w₆ = 18;   p₆ = 4

§  w₇ = 3;     p₇ = 1

M = 15

Jawaban :    

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi/wi	profit	weight	density
1	2	10	5	1	1	1	1
2	3	5	1,7	1	1	0	1
3	5	15	3	1	0	1	1
4	7	7	1	0	0	0	0
5	1	6	6	1	1	1	1
6	4	18	4,5	1	1	1	1
7	1	3	3	0	1	1	0
Total bobot :				15	11	13	15
Total keuntungan :				54	42	52	54

Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkan weight dan density tidak memberikan solusi optimal.