Algoritma Greedy

Definisi Algoritma Greedy

Algoritma Greedy Merupakan jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara pada setiap langkahnya. Nilai maksimun sementara ini dikenal dengan istilah local maksimum. Pada kebanyakan kasus algoritma greedy tidak akan menghasilkan solusi paling optimal begitupun algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang cukup cepat.

Algoritma greedy membenttuk solusi langkah perlangkah ( step by step ). Terdapat banyak pilihan yang perlu dieksplorasi pada setiap langkah solusi, karenanya pada setiap langkah harus dibuat keputusan yang teerbaik dalam menentukan pilihan.

   Contoh kasus1

    Masalah penukaran uang

           Nilai uang yang ditukar: A

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

           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

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

          b. Agar pemilihan koin berikutnya optimal, maka perlu mengurutkan himpunan koin dalam 
              urutan yang menurun (noninceasing order).

          c. Jika himpunan koin sudah terurut menurun, maka kompleksitas algoritma greedy = O(n).

          d. Sayangnya, algoritma greedy untuk masalah penukaran uang ini tidak selalu 
              menghasilkan solusi optimal (lihat contoh sebelumnya).

      Pseudocode:

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

endfunction 



Contoh kasus 2

contoh penerapan greedy didalam transportasi

Pada tabel 1 terdapat sebuah alat angkut dengan kapasitas 100kg terdapat 4 buah barang dengan ukuran sebagai berikut :

 

Maka dengan menggunakan algoritma greedy diperoleh tabel 2 sebagai berikut : 

Keterangan:

GBW : Greey By weight

GBP : Greedy By Profit

Gbd: Greedy By Density

0 : Barang tidak diangkut

1 : Barang diangkut

Berdasarkan teori dan contoh algoritma greedy dalam menyelesaikan Knapsack Problem maka pseudocode algoritma greedy adalah sebagai berikut:

function Knapsack(input C: himpunan_objek, K : real) → himpunan_solusi

{menghasilkan solusi persoalan knapsack dengan algoritma greedy yang menggunakan strategi pemilihan objek berdasarkan profit(pi), weight(wi), density(pi/wi). Soulsinya dinyatakan sebagai vektor X = x[1], x[2], ... , x[n].

Asumsi : untuk greedy by profit seluruh objek sudah terurut berdasarkan nilai pi yang menurun. Untuk greedy gy weighted seluruh objek sudah terurut berdasar nilai wi yang menaik. Untuk greedy by density seluruh objek sudah terurut berdasarkan nilai pi/wi yang menurun}

Deklarasi :

            i,totalbobot : integer

           available : boolean

           x : himpunan_solusi 

Algoritma :

             for i ← 1 to n do

             x[i] ← 0 

             endfor

             i ← 0

             totalbobot ← 0

             available ← true

             while (i < n) and (available) do

                    i ← i + 1

                    if totalbobot + w[i] ← K then

                        x[i] ← 1

                        totalbobot ← totalbobot + w[i]

                    else

                        available ← false

                        x[i] ← 0

                    endif

             endwhile

endfunction