Algoritma greedy

Pengertian Algoritma greedy


Algoritma greedy merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini dikenal dengan istilah optimum local. Pada kebanyakan kasus, algoritma greedy terkadang tidak akan menghasilkan solusi paling optimal. algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Greedy = rakus atau tamak
prinsip dasar dari greedy yaitu " take what you get now " .

Pemecahan masalah dalam Algoritma greedy  dilakukan langkah per langkah (step by step ) . Pada setiap langkah Algoritma Greedy
1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu (berdasarkan Prinsip "take what you can get now ")
2. Berharap bahwa memilih optimum local pada setiap langkah akan berakhir dengan optimum global.

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 

fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Contoh kasus 

Mencari jarak terpendek pada peta

Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta


Dimisalkan peta  direpresentasikan dengan titik-titik penghubung seperti berikut






dalam peta jarak terpendek sebenarnya



Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah seperti berikut:

1. Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.
2. Cari optimum local  ke titik selanjutnya.
3. Tandai graph sekarang sebagai graph yang telah dikunjungi, dan pindah ke local maximum yang telah ditentukan.
4. Kembali ke langkah 1 sampai titik tujuan didapatkan.

Jika mengapliikasikan langkah-langkah di atas pada graph A ke B maka hasil akhir adalah sebagai berikut

Dengan menggunakan algoritma greedy pada graph di atas, hasil akhir yang akan didapatkan sebagai jarak terpendek adalah A-C-D-E-F-B. Hasi jarak terpendek yang didapatkan ini tidak tepat dengan jarak terpendek yang sebenarnya (A-G-E-F-B). Algoritma greedy memang tidak selamanya memberikan solusi yang optimal, dikarenakan pencarian local maximum pada setiap langkahnya, tanpa memperhatikan solusi secara keseluruhan. Gambar berikut memperlihatkan bagaimana algoritma greedy dapat memberikan solusi yang kurang optimal.

Contoh Minimisasi Waktu di dalam Sistem (Penjadwalan)

Persoalan: Sebuah server (dapat berupa processor, pompa, kasir di bank, dll) mempunai n pelanggan (customer, client) yang harus dilayani. Waktu pelayanan untuk setiap pelanggan i adalah ti.
Minimumkan total waktu di dalam sistem:
  
T = (waktu di dalam sistem)
Ekivalen dengan meminimumkan waktu rata-rata pelanggan di dalam sistem.

Tiga pelanggan dengan

t1 = 7,    t2 = 12,     t3 = 5,

Enam urutan pelayanan yang mungkin:
============================================
Urutan        T
============================================                                              
1, 2, 3:    7 + (7 + 12) + (7 + 12 + 5 ) = 50
1, 3, 2:    7 + (7 + 5) + (7 + 5 + 12) = 43
2, 1, 3:    12 + (12 + 7) + (12 + 7 + 5) = 55
2, 3, 1:    12 + (12 + 5) + (12 + 5 + 7) = 53
3, 1, 2:    5 + (5 + 7) + (5 + 7 + 12) = 41 -> (optimal)
3, 2, 1:    5 + (5 + 12) + (5 + 12 + 7) = 46
============================================

Penyelesaian dengan metode greedy

Strategi greedy: Pada setiap langkah, pilih pelanggan yang membutuhkan waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.

function PenjadwalanPelanggan(input C : himpunan_pelanggan) ® himpunan_pelanggan

{ mengembalikan urutan jadwal pelayanan pelanggan yang meminimumkan waktu di dalam sistem }

Deklarasi

   S : himpunan_pelanggan

   i : pelanggann

Algoritma

  S ¬ {}

  while (C ¹ {}) do

     i ¬ pelanggan yang mempunyai t[i] terkecil

     C ¬ C - {i}

     S ¬ S È {i}    

  endwhile

 

  return S

Agar proses pemilihan pelanggan berikutnya optimal, urutkan pelanggan berdasarkan waktu pelayanan dalam urutan yang menaik.
Jika pelanggan sudah terurut, kompleksitas algoritma greedy = 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