ALGORITMA GREEDY

ALGORITMA GREEDY (PAA pertemuan 1)

METODE GREEDY Metode yang digunakan untuk memperoleh solusi yang optimal dari suatu masalah yang mempunyai 2 indikator yaitu : adanya fungsi tujuan & pembatas (Constrain).

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, dankeputusan tersebut tidak dapat diubah lagi pada langkah selanjutnya.

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.

Greedy = rakus, tamak, loba, ….

Prinsip greedy adalah: “take what you can get now!”. 

Contoh masalah sehari-hari yang menggunakan prinsip greedy:

o   Memilih beberapa jenis investasi (penanaman modal)

o   Mencari jalur tersingkat dari Bandung ke Surabaya

o   Memilih jurusan di Perguruan Tinggi

o   Bermain kartu remi

Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang “tampaknya” memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya  mengarah ke solusi optimum global (global optimm).

Algoritma greedy membentuk solusi langkah per langkah (step by step).

Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah, pada setiap langkah:

1.mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan (prinsip “take what you can get now!”)

2.berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.

Contoh 1 (Masalah Penukaran uang):

Persoalan: Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Contoh: tersedia koin-koin 1, 5, 10, dan 25

Uang senilai 32 dapat ditukar dengan 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)

            … dan seterusnya                 

Minimum: 32 = 25 + 5 + 1 + 1       ) hanya 4 koin

Strategi greedy yang digunakan  adalah:

Pada setiap langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.

Tinjau masalah menukarkan uang 32 dengan koin 1, 5, 10, dan 25:

Langkah 1: pilih 1 buah koin 25  (Total = 25)

Langkah 2: pilih 1 buah koin 5   (Total = 25 + 5 = 30)

Langkah 3: pilih 2 buah koin 1  (Total = 25+5+1+1= 32) 

Solusi: Jumlah koin minimum = 4 (solusi optimal!)

Pada setiap langkah di atas kita memperoleh optimum lokal, dan pada akhir algoritma kita memperoleh optimum global (yang pada contoh ini merupakan solusi optimum).

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. 

 Skema Umum Algoritma Greedy

Misal kita mengasumsikan elemen algoritma greedysebagai 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 : 

1. Inisialisasi S dengan kosong.

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

3. Kurangi C dengan kandidat yang telah terpilih di atas.

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

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