Algoritma Greedy

Definisi Algoritma Greedy

Algoritma greedy merupakan metode yang paling populer untuk memecahkan persoalan optimasi.

•       Persoalan optimasi (optimization problems): 

              ➔ persoalan mencari solusi optimum.

•       Hanya ada dua macam persoalan optimasi:

                 1.  Maksimasi (maximization)

                 2.  Minimasi (minimization)

Contoh persoalan optimasi:

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

➔ Persoalan minimasi

•       Greedy = rakus, tamak, loba, …

•       Prinsip greedy: “take what you can get now!”.

•       Algoritma greedy membentuk solusi langkah per langkah (step by step).

•       Pada setiap langkah, terdapat banyak pilihan yang perlu dievaluasi.

•       Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.

•       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 kedepan.   

2          .       Berharap bahwa dengan memilih langkah optimum local pada setiap langkah akan  berakhir    dengan optimum global.

               

•       Tinjau masalah penukaran uang:

                Strategi greedy: 

                Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa.

•       Misal: A = 32, koin yang tersedia: 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!)

Elemen-elemen algoritma greedy:

        1. Himpunan kandidat, C.

        2. Himpunan solusi, S

        3. Fungsi seleksi (selection function)

        4. Fungsi kelayakan (feasible)

        5. Fungsi obyektif

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  dioptimisasi oleh fungsi obyektif.

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.

Bantuk umum algoritma greedy

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

∙          Pada akhir kalang while-do diperoleh optimum global.

Contoh Soal

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)

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)

Contoh Kasus Algoritma Greedy

1. Masalah penukaran uang

        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.

Penyelesaian dengan algoritma greedy

•       Strategi 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).  

2. 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 t_i.

                Minimumkan total waktu di dalam sistem: 

                T =          (waktu di dalam sistem)

•       Ekivalen dengan meminimumkan waktu rata-rata pelanggan di dalam sistem. 

Penyelesaian dengan algoritma greedy

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

Adj

Author & Editor

Silahkan Copy Paste Tapi Cantumin Link Sumber Ya kk (^3^) Ok | Kalo Gak Tak Tabok (---)p