Algoritma Greedy

Algoritma Greedy

Pengetian:

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

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.

       

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 Kasus:

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)

Pseudo Code:

function CoinExchange(input C : himpunan_koin, A : integer) -> himpunan_koin

{ mengembalikan koin-koin yang total nilainya = A,tetapi jumlah koinnya minimum}

Deklarasi

      S : himpunan_koin

      x : koin

  

Algoritma

S <-  {}

while (∑ (nilai semua koin di dalam S) ≠ A) and (C ≠ {} ) do

      x <- koin yang mempunyai nilai terbesar

      C <- C – {x}

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

            S <- S È  {x}

      endif

endwhile

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

       return S

else

       write(“tidak ada solusi”)

endif

Referensi:

http://kurniadi-addi.blogspot.co.id/2015/07/materi-analisis-algortima-algoritma.html