ALGORITMA GREEDY

         ALGORITMA GREEDY

     Algoritma Greedy merupakan metode yang paling popular dalam memecahkan persoalan optimasi. Hanya ada dua macam persoalan optimasi, yaitu maksimasi dan minimasi. Algoritma Greedy adalah algoritma yang memcahkan masalah langkah perlangkah (step by step). Algoritma Greedy membentuk solusi langkah perlangkah. Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi. Oleh Karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkahnya merupakan pilihan untuk membuat langkah optimum local ( local optimum) dengan harapan bahwa langkah sisanya mengarah ke solusi optimasi global (global optimum). Prinsip Greedy adalah “take what you can get now”, mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan kosekuensi ke depan.

Contoh masalah sehari-hari yang menggunakan prinsip greedy:

·           Memilih beberapa jenis investasi (penanaman modal)

·           Mencari jalur tersingkat / terpendek

·           Memilih jurusan di Perguruan Tinggi

·           Bermain kartu remi

·           Memecah uang 

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!)

procedure greedy(input C: himpunan_kandidat;

                 output S : himpunan_solusi)

{ menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy

  Masukan: himpunan kandidat C

  Keluaran: himpunan solusi S

}

Deklarasi

       x : kandidat;

Algoritma:

         S¬{}                               { inisialisasi S dengan kosong }

         while (belum SOLUSI(S)) and (C ¹ {} ) do

         x¬SELEKSI(C);            { pilih sebuah kandidat dari C}

         C¬ C - {x}      { elemen himpunan kandidat berkurang satu }

            if LAYAK(S È {x}) then

                S¬S È {x}

           endif

   endwhile

Endprocedure

{SOLUSI(S) sudah diperoleh or C = {} } 

Contoh 2 : Minimisasi Waktu di dalam Sistem (Penjadwalan)

Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai npelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan sudah ditetapkan sebelumnya, yaitu pelanggan i membutuhkan waktu t_i. Kita ingin meminimumkan total waktu di dalam sistem, Karena jumlah pelanggan adalah tetap, meminimumkan waktu di dalam sistem ekivalen dengan meminimumkan waktu rata-rata

Misalkan kita mempunyai tiga pelanggan dengan

            t₁ = 5,   t₂ = 10,             t₃ = 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 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).

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 t_i}

  for i¬1 to n do

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

  endfor

Endprocedure

Sumber :
http://dasarsukses.blogspot.co.id/2011/04/algoritma-greedy.html