ALGORITMA GREEDY

       Pada pembahasan kali ini kami akan membahas tentang apa itu GREEDY , dari pengertian greedy , contoh kasus serta Pseodocordnya.

Nah.... kali ini ayo kita bahas dulu apa itu greedy , Algoritma Greedy adalah salah satu algoritma yang dapat digunakan untuk mendapatkan solusi terbaik dan merupakan algoritma yang paling populer, dalam hal ini ALgoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”

Dalam kehidupan sehari hari, banyak terdapat persoalan yang menuntut pencarian solusi optimum. Persoalan tersebut dinamakan persoalan optimasi(optimization Problems). Persoalan Optimasi adalah persoalan yang tidak hanya mencari sekedar solusi, tetapi mencari solusi terbaik.
Secara Harfiah Greedy artinya rakus atau tamak, sifat yang berkonotasi negatif. Orang yang memiliki sifat ini akan mengambil sebanayak mungkin atau mengambil yang paling bagus atau yang paling mahal. Sesuai dengan arti tersebut, Prinsip Greedy adalah take what you can get now. Dalam kehidupan sehari hari Greedy dapat digunakan dalam masalah seperti :

§  Memilih beberapa jenis investasi

§  Mencari jalur tersingkat

Ada juga yang dapat dilakukan algoritma ini dalam sesuatu yang biasa dilakukan mesyarakat modern, yaitu memilih spesifikasi komputer yang terbaik dengan budget maksimum tertentu seperti yang akan dibahas dalam makalah singkat ini.

           Definisi Algoritma Greedy

      Algoritma Greedy membentuk solusi langkah per langkah (step by step). Terdapat banyak pilihan yang perlu di eksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusann yang terbaik dalam menentukan pilihan.Keputusan yang telah
diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi.
Pada setiap langkah diperoleh optimum lokal. Bila algoritma berakhir, kita berharap optimum lokal menjadi optimum global.
       

      Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

- Greedy = rakus, tamak, loba  
      
Algoritma Greedy adalah algoritma yang memecahkan masalah langkah per langkah;   
   pada setiap langkah:

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

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

Contoh persoalan optimasi:
  ( Masalah Penukaran Uang): Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh 1: tersedia banyak koin 1, 5, 10, 25
Uang senilai A = 32 dapat ditukar dengan banyak 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)
                  … dst                 
Minimum: 32 = 25 + 5 + 1 + 1       (4 koin)

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, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Pada masalah penukaran uang:

•      Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
•       Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
•      Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
•      Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
•      Fungsi obyektif: jumlah koin yang digunakan minimum

Materi Analisis Algortima : Algoritma Greedy

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 È {x}) then
                      S¬S È {x}
         endif
     endwhile

{SOLUSI(S) sudah diperoleh or C = {} }
Pada akhir setiap lelaran, solusi yang terbentuk adalah optimum lokal.
Pada akhir kalang while-do diperoleh optimum global.
Warning: Optimum global belum tentu merupakan solusi optimum (terbaik), tetapi sub-optimum atau pseudo-optimum.
Alasan:

1.       Algoritma Greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search). 

2.       Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita  ingin algoritma menghasilkan solusi optiamal.
Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang optimal.

§  Contoh 2: tinjau masalah penukaran uang.
(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, 1
Uang yang ditukar: 15
            Solusi greedy:  15 = 10 + 1 + 1 + 1 + 1 + 1    (6 koin)
            Solusi optimal: 15 = 7 + 7 + 1                         (hanya 3 koin)
(c)        Koin: 15, 10, dan 1
            Uang yang ditukar: 20
            Solusi greedy: 20 = 15 + 1 + 1 + 1 + 1 + 1     (6 koin)
            Solusi optimal: 20 = 10 + 10                           (2 koin)
          
Penyelesaian dengan exhaustive search
-  Terdapat 2n kemungkinan solusi
            (nilai-nilai X = {x1, x2, …, xn} )
-   Untuk mengevaluasi fungsi obyektif = O(n)
-   Kompleksitas algoritma exhaustive search seluruhnya = O(n × 2n ).

  Penyelesaian dengan algoritma greedy

Strategi greedy:  Pada setiap langkah, pilih koin dengan nilai  terbesar dari himpunan koin yang tersisa 

Persoalan optimasi (optimization problems): persoalan yang menuntut pencarian solusi optimum. 

                Persoalan optimasi hanya ada dua macam:

                1 . Maksimasi (maximization)

                2. Minimasi (minimization) 

Solusi optimum (terbaik) adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mungkin.

Solusi yang memenuhi semua kendala disebut solusi layak (feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi disebut solusi optimum.

Greedy = rakus, tamak, loba   

       

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

Contoh persoalan optimasi:

  ( Masalah Penukaran Uang): Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Contoh 1: tersedia banyak koin 1, 5, 10, 25

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

                  … dst                  

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

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, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).

Pada masalah penukaran uang:

• Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
• Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
• Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
• Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
• Fungsi obyektif: jumlah koin yang digunakan minimum

Materi Analisis Algortima : Algoritma Greedy

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

                      S¬S È {x}

         endif

     endwhile

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

Pada akhir setiap lelaran, solusi yang terbentuk adalah optimum lokal.

Pada akhir kalang while-do diperoleh optimum global.

Warning: Optimum global belum tentu merupakan solusi optimum (terbaik), tetapi sub-optimum atau pseudo-optimum.

Alasan:

1. Algoritma Greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search). 

 2. Terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita  ingin algoritma menghasilkan solusi optiamal.

Jadi, pada sebagian masalah algoritma greedy tidak selalu berhasil memberikan solusi yang optimal.

Contoh 2: tinjau masalah penukaran uang.

(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, 1

Uang yang ditukar: 15

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

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

(c)        Koin: 15, 10, dan 1

            Uang yang ditukar: 20

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

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

           

Penyelesaian dengan exhaustive search

—  Terdapat 2n kemungkinan solusi

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

—  Untuk mengevaluasi fungsi obyektif = O(n)

—  Kompleksitas algoritma exhaustive search seluruhnya = O(n × 2n ).

  Penyelesaian dengan algoritma greedyStrategi greedy:  Pada setiap langkah, pilih koin dengan nilai  terbesar dari himpunan koin yang tersisa 

·          Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam urutan yang menurun (noninceasing 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 (lihat contoh sebelumnya). 

Contoh Algoritma Greedy mencari jarak terpendek dari peta

Misalkan kita ingin bergerak dari titik A ke titik B, dan kita telah menemukan beberapa jalur dari peta.
Untuk mencari jarak terpendek dari A ke B, sebuah algoritma greedy akan menjalankan langkah-langkah
seperti berikut:
Kunjungi satu titik pada graph, dan ambil seluruh titik yang dapat dikunjungi dari titik sekarang.

1.  Cari local maximum ke titik selanjutnya.
2.  Tandai graph sekarang sebagai graph yang telah 
3.  dikunjungi, dan pindah ke local maximum yang telah ditentukan.
4.  Kembali ke langkah 1 sampai titik tujuan didapatkan.

Dengan  menggunakan algoritma greedy pada graph di atas hasil akhir jarak terpendek adalah ACDEFB. Hasil jarak terpendek ini sbenarnya tidak tepat dengan jarak pendek sebenarnya(A-G-E-F-B). Maka dari aalgoritma yang tidak selamanya benar namu algoritma yang mendekati nilai kebenaran.
Pemecahan Masalah dengan Algoritma Greedy
Strategi greedy untuk memilih job:   
                        Pada setiap langkah, pilih job i dengan
                        pi yang terbesar untuk menaikkan nilai
                        fungsi obyektif F.
Contoh:
(p1, p2, p3, p4) = (50, 10, 15, 30)
(d1, d2, d3, d4) = (2, 1, 2, 1)

 
Solusi optimal: J = {4, 1} dengan F = 80.

  

 
Kompleksitas algoritma greedy : O(n2).