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)
(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.
- 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 = |  |
Semoga penjelasan diatas membantu anda yaa?
Kata Kunci : Contoh-contoh Algoritma Greedy,Algoritma Greedy, Skripsi Teknik Informatika, Contoh Skripsi, Skripsi. ilmuskripsi.com
Emoticon