Algoritma Greedy

    Algoritma Greedy merupakan merode yang paling populer dalam memecahkan persoalan optimasi. Hanya ada dua macam persoalan optimasi, yaitu maksimasi dan minimasi. Algoritma Greedy adalah algoritma yang memecahkan masalah langkah per langkah. Pada setiap langkah, terdapat banyak pilihan yang perlu dieskplorasi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Pada setiap langkahnya merupakan pilihan, untuk membuat langkah optimum lokal (local optimum) dengan harapan bahwa langkah sisanya mengarah ke solusi optimum global (global optimum). Prinsip dari Algoritma Greedy adalah “take what you can get now”, mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan.

Skema Umum Algoritma Greedy

Persoalan optimasi dalam konteks algoritma greedy disusun oleh elemen-elemen sebagai berikut :

       1.      Himpunan Kandidat, C.

Himpunan ini berisi elemen-elemen pembentuk solusi. Pada setiap langkah, satu buah kandidat diambil dari himpunannya.

       2.      Himpunan Solusi, S.

Himpunan ini berisi kandidat-kandidat yang terpilih sebagai solusi persoalan. Dengan kata lain, himpunan solusi adalah himpunan bagian dari himpunan kandidat.

       3.      Fungsi Seleksi (selection function)

Fungsi ini dinyatakan dengan predikat seleksi. Merupakan fungsi yang pada setiap langkahnya memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

       4.      Fungsi Kelayakan (feasible)

Fungsi ini dinyatakan dengan predikat layak. Fungsi kelayakan ini merupakan fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.

       5.      Fungsi Obyektif

Fungsi Obyektif ini merupakan sebuah fungsi yang memaksimumkan atau meminimumkan nilai solusi.

    Dengan kata lain, algoritma greedy melibatkan pencarian sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimasi oleh fungsi obyektif.

       Adakalanya, solusi optimum global yang diperoleh dari algoritma greedy yang diharapkan sebagai solusi optimum dari persoalan, belum tentu merupakan solusi optimum (terbaik), tetapi solusi sub-optimum atau pseudo-optimum. Hal ini dikarenakan algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada dan terdapat beberapa fungsi seleksi yang berbeda, yaitu jika fungsi seleksi tidak identik dengan fungsi obyektif karena fungsi seleksi biasanya didasarkan pada fungsi obyektif. Sehingga harus dipilih fungsi yang tepat jika menginginkan algoritma menghasilkan solusi optimal atau nilai yang optimum. Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum, tetapi algoritma greedy pasti memberikan solusi yang mendekati (approximation) nilai optimum.

    Jika jawaban terbaik mutlak tidak diperlukan, maka algortima greedy sering berguna untuk menghasilkan hampiran (approximation), daripada menggunakan algoritma yang lebih rumit untuk menghasilkan solusi eksak. Bila algoritma greedy optimum, maka keoptimalannya itu dapat dibuktikan secara matematis.

Berikut adalah contoh pseudo-code Algoritma greedy :

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 U {x}) then

         S ß S U {x}

      endif

   endwhile

   {solusi(S) sudah direroleh or C = {} }

Dalam menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy. pembuatan Prosedur Greedy dengan masukan berupa himpunan-kandidat dengan variable C, dan keluaran berupa himpunan_solusi dengan variable S. Variabel x dideklarasikan sebagai kandidat sementara yang di pilih.

Langkah algoritma greedy : inisialisasi awal himpunan-solusi dengan kosong. Selama himpunan solusi belum ditemukan dan himpunan-kandidat tidak kosong, maka akan dilakukan pemilihan sebuah kandidat dari himpunan_kandidat untuk mengisi variabel sementara x, sehingga i-rimpunan_kandidat menjadi berkurang satu dan himpunan kandidat yang berkurang tadi menjadi himpunan kandidat yang baru. Jika anggota himpunan_solusi merupakan anggota himpunan x, maka himpunan solusi yang baru adalah anggota dari himpunan-solusi yang juga menjadi anggota dari himpunan x. Himpunan _solusi sudah diperoleh atau himpunan-kandidat =himpunan kosong (3; 1; 12).

Contoh Algoritma Greedy pada 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).

Pada masalah penukaran uang, elemen-elemen algoritma greedy-nya adalah :

    1.  Himpunan Kandidat : Himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.

    2.  Himpunan Solusi : Total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.

       3.     Fungsi Seleksi : Pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.

     4.   Fungsi Kelayakan : Memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.

       5.     Fungsi Obyektif : Jumlah koin yang digunakan minimum.

Contoh masalah penukaran uang lainnya :

       a.      Koin : 5, 4, 3, dan 1

       Uang yang ditukar = 7

       Solusi greedy : 7 = 5 + 1 + 1    (3 koin) à Tidak Optimal

       Solusi optimal: 7 = 4 + 3         (2 koin)

       b.      Koin : 10, 7, dan 1

       Uang yang ditukar = 15

       Solusi greedy : 15 = 10 + 1 + 1 + 1 + 1 + 1      (6 koin) à Tidak Optimal

       Solusi optimal: 15 = 7 + 7 + 1                         (3 koin)

       c.       Koin : 15, 10, dan 1

       Uang yang ditukar = 20

      Solusi greedy : 20 = 15 + 1 + 1 + 1 + 1 + 1      (6 koin) à Tidak Optimal

      Solusi optimal: 20 = 10 + 10                           (3 koin)

Penyeselesaian dengan Exhaustive Search

Nilai uang yang ditukar : A

Himpunan koin (multiset):  {d₁, d₂, …}.

Himpunan solusi: X = {x₁, x₂, …, x_n},

   x_i = 1 jika d_i dipilih, x_i = 0 jika d_i tidak dipilih.

·         Terdapat 2ⁿ kemungkinan solusi

-(nilai-nilai X= {x1, x2, …, xn} )

·         Untuk mengevaluasi fungsi obyektif= O(n)

·         Kompleksitas algoritma exhaustive search seluruhnya= O(n⋅2ⁿ).

Berikut adalah contoh pseudo-code penukaran uang Algoritma greedy :

Algoritma CoinExchange(input C : himpunan_koin, A : integer)àhimpunan_koin

{ mengembalikan koin-koin yang total nilainya = A dengan jumlah minimum}

Deklarasi

   x : koin

   S : himpunan_koin

Algoritma

   S ß {}

   while (jumlah nilai semua koin di dalam S <> A ) and (C <> {}) do

      x ß koin dengan nilai terbesar

      C ß C – {x}

      if (jumlah nilai semua koin di dalam S) + nilai koin x < A then

         S ß S U {x}

      endif

   endwhile

   

   if (jumlah nilai semua koin di dalam S) = A then

      return S

   else

      write(‘tidak ada solusi’)

   endif

Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan menurun (nononceasing order). Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n). Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu menghasilkan solusi optimal. 

Sumber :

Bahan Kuliah Algoritma Greedy oleh Rinaldi Munir

http://repository.upi.edu/2676/6/S_MTK_0900626_Chapter3.pdf

Read More