ALGORITMA GREEDY

ALGORITMA GREEDY

1.      Minimisasi Waktu di dalam Sistem (Penjadwalan)

Ø  Tiga pelanggan dengan ;

t1= 5,t2= 10, t3= 3,

Enam urutan pelayanan yang mungkin:

============================================

UrutanT

============================================

1, 2, 3:5 + (5 + 10) + (5 + 10 + 3 ) = 38

1, 3, 2: 5 + (5 + 3) + (5 + 3 + 10) = 31

2, 1, 3:10 + (10 + 5) + (10 + 5 + 3) = 43

2, 3, 1:10 + (10 + 3) + (10 + 3 + 5) = 41

3, 1, 2:3 + (3 + 5) + (3 + 5 + 10) = 29 (optimal)

3, 2, 1:3 + (3 + 10) + (3 + 10 + 5) = 34

Ø  Penyelesaian dengan Exhaustive Search

Ø  Urutan pelangan yang dilayani oleh servermerupakan suatu permutasi

Ø  Jika ada n orang pelanggan, maka tedapat n! urutan pelanggan 

Ø  Untuk mengevaluasi fungsi obyektif : O(n)

Ø  Kompleksitas algoritma exhaustive search= O(nn!)

Penyelesaian dengan algoritma greedy

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

function PenjadwalanPelanggan(input C : himpunan_pelanggan) ® himpunan_pelanggan { mengembalikan urutan jadwal pelayanan pelanggan yang meminimumkan waktu di dalam sistem }

Deklarasi

S : himpunan_pelanggan 

i : pelanggann 

Algoritma

S ¬ {} 

while (C ¹ {}) do

i ¬ pelanggan yang mempunyai t[i] terkecil 

C ¬ C - {i} S 

¬ S È {i} 

endwhile

return S

Ø  Agar proses pemilihan pelanggan berikutnya optimal, urutkan pelanggan berdasarkan waktu pelayanan dalam urutan yang menaik. 

Ø  Jika pelanggan sudah terurut, kompleksitas algoritma greedy= O(n). 

procedure PenjadwalanPelanggan(input n:integer)
 { Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n Keluaran: urutan pelanggan yang dilayani }

Deklarasi

i : integer 

Algoritma

{pelanggan 1, 2, ..., n sudah diurut menaik berdasarkan ti} 

for i¬1 to n do

write(‘Pelanggan ‘, i, ‘ dilayani!’) 

endfor

Ø  Algoritma greedy untuk penjadwalan pelanggan akan selalu menghasilkan solusi optimum. 

22.  Penukaran uang

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 algoritma greedy

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

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