Contoh-contoh Algoritma Greedy

1. Masalah penukaran uang

Nilai uang yang ditukar: A
        Himpunan koin (multiset):  {d1, d2, …, dn}.
Himpunan solusi: X = {x1, x2, …, xn},
xi = 1 jika di dipilih, xi = 0 jika di tidak dipilih.

Penyelesaian dengan exhaustive search

Untuk lebih jelasnya apa itu algoritma exhaustive search anda bisa membacanya pada artikel ini "Contoh Implementasi Algoritma Exhaustive Search "

• Terdapat 2n kemungkinan solusi

(nilai-nilai X = {x1, x2, …, xn} )

• Untuk mengevaluasi fungsi obyektif = O(n)

• Kompleksitas algoritma exhaustive search seluruhnya = O(n  2n ). 

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 ti. 

Minimumkan total waktu di dalam sistem:

      T=  (Waku di dalam sistem) 

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

Contoh 3:  Tiga pelanggan dengan

t₁ = 5, t₂ = 10, t₃ = 3

Enam urutan pelayanan yang mungkin:

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

Urutan T  

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

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 server merupakan 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.

• Agar proses pemilihan pelanggan berikutnya optimal, urutkan pelanggan berdasarkan waktu pelayanan dalam urutan yang menaik. 
• Jika pelanggan sudah terurut, kompleksitas algoritma greedy = O(n).

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

• Teorema. Jika t1 ≤ t2 ≤ … ≤  tn maka pengurutan  ij = j,  1 ≤ j ≤ n   meminimumkan

T =

untuk semua kemungkinan permutasi i_j


Semoga penjelasan diatas membantu anda yaa?

Kata Kunci : Contoh-contoh Algoritma Greedy,Algoritma Greedy, Skripsi Teknik Informatika, Contoh Skripsi, Skripsi. ilmuskripsi.com 

Tags : #algoritma

Share This :

Unknown