Arfian Hidayat


Salurkan Ilmu Dengan Menulis

Algoritma Greedy

1. Penukaran Uang (contoh program)

Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?

Contoh 1 tersedia banyak koin 1, 5, 10, 25
Uang senilai A = 32 dapat ditukar dengan banyak cara berikut
32 = 1 + 1 + . . . + 1 (32 koin)
32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)
32 = 10 + 10 + 10 + 1 + 1 (5 koin)
. . . dst
Minimum 32 = 25 + 5 + 1 + 1 (4 koin)

Greedy = rakus, tamak, loba, . . .
Prinsip greedy `take what you can get now!
Algoritma greedy membentuk solusi langkah per langkah (step by step).
Pada setiap langkah, terdapat banyak pilihan yang perlu dieksplorasi.
Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan.
Pada setiap langkah, kita membuat pilihan optimum lokal (local optimum) dengan harapan bahwa langkah sisanya

mengarah ke solusi optimum global (global optimm)
Algoritma greedy adalah algoritma yang memecahkan masalah langkah per langkah. Pada setiap langkah :
1. mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi ke depan

(prinsip `take what you can get now!)
2. berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Tinjau masalah penukaran uang
Strategi greedy Pada setiap langkah, pilihlah koin dengan nilai terbesar dari himpunan koin yang tersisa.
Misal A = 32, koin yang tersedia 1, 5, 10, dan 25
Langkah 1 pilih 1 buah koin 25 (Total = 25)
Langkah 2 pilih 1 buah koin 5 (Total = 25 + 5 = 30)
Langkah 3 pilih 2 buah koin 1 (Total = 25+5+1+1= 32)
Solusi Jumlah koin minimum = 4 (solusi optimal!)

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 t ke-i
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 i j= j, 1 = j = n meminimumkan untuk semua kemungkinan permutasi

i ke-j

3. Integer Knapsack (0/1 Knapsack)
Penyelesaian dengan exhaustive search
Sudah dijelaskan pada pembahasan exhaustive search.
Kompleksitas algoritma exhaustive search untuk persoalan ini = O(n . 2 pangkat n).

Penyelesaian dengan algoritma greedy
Masukkan objek satu per satu ke dalam knapsack. Sekali objek dimasukkan ke dalam knapsack, objek tersebut tidak

bisa dikeluarkan lagi.
Terdapat beberapa strategi greedy yang heuristik yang dapat digunakan untuk memilih objek yang akan dimasukkan ke

dalam knapsack
1. Greedy by profit.
- Pada setiap langkah, pilih objek yang mempunyai keuntungan terbesar.
- Mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu.
2. Greedy by weight.
- Pada setiap langkah, pilih objek yang mempunyai berat teringan.
- Mencoba memaksimumkan keuntungan dengan dengan memasukkan sebanyak mungkin objek ke dalam knapsack.
3. Greedy by density.
- Pada setiap langkah, knapsack diisi dengan objek yang mempunyai pi/wi terbesar.
- Mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar.

Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal.
Contoh 4.
w1 = 6; p1 = 12; w2 = 5; p2 = 15;
w3 = 10; p3 = 50; w4 = 5; p4 = 10
Kapasitas knapsack K = 16

Posting Oleh Admin, 14 April 2016, 19:20


algoritma, algoritma greedy, bahasa c, contoh algoritma greedy, greedy, greedy algorithm, penukaran koin, penukaran koin dengan algoritma greedy, source greedy