Sabtu, 03 Desember 2016

ALGORITMA GREEDY

           No comments   
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 :
1.      Memilih beberapa jenis investasi.
2.      Mencari jalur tersingkat dari Bandung ke Surabaya.
3.      Memilih jurusan di Perguruan Tinggi
4.      Bermain Kartu Remi
5.      Memilih spesifikasi komputer yang terbaik dengan budget maksimum tertentu.

1.1          Definisi Algoritma Greedy

Algoritma greedy adalah langkah per langkah dalam mencari solusi atas sebuah masalah. Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan. Keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya. Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi”.

1.2          Personal Optimasi

Persoalan Optimasi adalah persoalan yang tidak hanya mencari sekedar solusi, tetapi mencari solusi terbaik. Dalam kehidupan sehari hari, banyak terdapat persoalan yang menuntut pencarian solusi optimum. Persoalan tersebut dinamakan persoalan optimasi(optimization Problems).

Persoalan optimasi ada dua macam :
        ·         Maksimasi (maximization)
        ·         Minimasi (minimization)

Contoh Persoalan Optimasi :
( Masalah Penukaran Uang): Diberikan uang senilai A = 32. Tukar A dengan koin-koin uang yang tersedia banyak koin 1, 5, 10, 25. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
              ·         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)

1.3          Solusi Optimasi

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

1.4          Skema Umum Algoritma Greedy

Elemen-elemen algoritma greedy :

       1.     Himpunan kandidat, C
       Berisi elemen-elemen pembentuk solusi.
       2.     Himpunan solusi, S
       Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
       3.      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.
       4.      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.
       5.      Fungsi obyektif
       Fungsi objektif yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi(misalnya            panjang lintasan, keuntungan, dan lain-lain).

      Contoh :
       Pada masalah penukaran uang:
a.       Himpunan kandidat, C : Himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
b.      Himpunan solusi, S : Total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
c.       Fungsi seleksi: Pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
d.      Fungsi layak : Memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
e.       Fungsi obyektif: Jumlah koin yang digunakan minimum.

 

1.5          Skema Umum Algoritma Greedy Dalam Notasi Algoritma

             Skema Algoritma dapat dirumuskan sebagai berikut :
                                                   i.            Inisialisasi S dengan nilai kosong.
                                                  ii.            Pilih sebuah kandidat (dengan fungsi SELEKSI) dari C
                                                  iii.          Kurangi C dengan kandidat yang sudah dipilih dari langkah ii
                                                  iv.           Periksa apakah kandidat yang dipilih bersama” himpunan solusi membentuk solusi 
                                   yang layak (diperiksa oleh Fungsi FEASIBLE).
               Jika YA à masukkan kandidat ke himpunan solusi ,
               TIDAK à buang kandidat
                                                    v.            Periksa apakah himpunan solusi sudah memberikan solusi lengkap (dengan fungsi 
                                   SOLUSI)
               Jika YA à berhenti ,
               TIDAK à ulangi langkah ii

Skema umum algoritma greedy dalam pscedu-code :



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

        ·         Pada akhir dikalangan while-do diperoleh optimum global.

         Referensi :

0 komentar:

Posting Komentar