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


Lebih Jelas Dapat di lihat di Web Saya Yang Ini..

MENGHITUNG ALGORITMA REQURSIF

MENGHITUNG ALGORITMA REQURSIF
(PERBAIKAN)

v  Menghitung faktorial dari 5 buah inputan.

N = 5!

Ø  Program faktorial (input x = integer, output hasil = integer)

Deklarasi

Algoritma

                If x = 1 then

                          Hasil  ß 1

                Else

                           Hasil ß faktorial (x-1)*x

                Endif

Ø  n = 5!

Ø  Pembatas F (1) = 1

Ø  F (x) = F (x-1) * x

F (5) = F (5-1) * 5 = F (4) * 5

F (4) = F (4-1) * 4 = F (3) * 4

F (3) = F (3-1) * 3 = F (2) * 3

F (2) = F (2-1) * 2 = F (1) * 2

F (1) = 1

Hasil = 1 * 2 * 3 * 4 * 5 = 120

5! = 120.

T(n) = T ( n – 1 ) + 1

T(5) = T ( 5-1 ) + 1 = T (4)+1

T(4) = T ( 5-2 ) + 1 = T(3) + 1

T(3) = T (5-3) + 1 = T (2) + 1

T (2) = T (5-4) + 1 = T (1) + 1

T (1) = T (5 - 5) + 1

T (1) = 0 + 1 = 1 € O (n)

v  Menghitung faktorial dari 3 buah inputan.

N = 3!

Ø  Program faktorial (input x = integer, output hasil = integer)

Deklarasi

Algoritma

                If x = 1 then

                          Hasil  ß 1

                Else

                           Hasil ß faktorial (x-1)*x

                Endif

Ø  n = 3!

Ø  Pembatas F (1) = 1

Ø  F (x) = F (x-1)*x

F (3) = F (3-1) * 3 = F (2) * 3

F (2) = F (2-1) * 2 = F (1) * 2

F (1) = 1

Hasil = 1 * 2 * 3 = 6

3! = 6.

T(n) = T ( n – 1 ) + 1

T(3) = T (3-1) + 1

T (3-1) = T (3-2) + 1

T (3-2) = T (3 – 3) + 1

T (1) = 0 + 1 = 1 € O (n)

v  Menghitung Tower of Hanoi dari 5 buah kotak

n = 5

Ø  n = 5

Ø  pembatas T(1) = 1

Ø  T(n) = 2T (n-1) + 1

T(5) = 2T (5-1) + 1 = T (4) + 1

T(4) = 2T (5-2) + 1 = T (3) + 1

T(3) = 2T (5-3) + 1 = T (2) + 1

T(2) = 2T (5-4) + 1 = T (1) + 1

T(1) = 2 (1) + 1

T(n) = 2^5-1 =31 € O (2ⁿ)


Lebih jelas di link yang ini.