Contoh-contoh Algoritma Greedy

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.

Contoh Contoh Algoritma Greedy

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.


Contoh Contoh Algoritma Greedy

  • 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= Rumus Contoh Algoritma Greedy (Waku di dalam sistem) 

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

Contoh 3:  Tiga pelanggan dengan
t1 = 5, t2 = 10, t3 = 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.
Contoh Contoh Algoritma Greedy

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

Contoh Contoh Algoritma Greedy

  • Algoritma greedy untuk penjadwalan pelanggan akan selalu menghasilkan solusi optimum. 
  • Teorema. Jika t1 ≤ t2 ≤ … ≤  tn maka pengurutan  ij = j,  1 ≤ j ≤ n   meminimumkan

T =
Algoritma Greedy


untuk semua kemungkinan permutasi ij


Semoga penjelasan diatas membantu anda yaa?

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