PENGERTIAN ALGORITMA GREEDY
Algoritma
Greedy
merupakan metode yang paling populer untuk memecahkan persoalan optimasi yang merupakan
jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari
nilai maksimum sementara pada setiap langkahnya. Nilai maksimum sementara ini
dikenal dengan istilah local maximum. Pada kebanyakan kasus, algoritma
greedy tidak akan menghasilkan solusi paling optimal, begitupun algoritma
greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktu yang
cukup cepat.
Algoritma Greedy juga
merupakan langkah dalam mencari solusi atas sebuah masalah. banyak sekali
algoritma yang dapat kita gunakan dalam membangun sebuah program , salah
satunya adalah algoritma greedy. Greedy sendiri diambil dari bahasa inggris
yang artinya rakus, tamak atau serakah .Prinsip algoritma greedy adalah: “take
what you can get now!”.
Greedy = rakus, tamak, loba
Persoalan optimasi (optimization
problems) adalah persoalan yang menuntut pencarian
solusi optimum.
Persoalan
optimasi hanya ada
dua macam:
1 . Maksimasi
(maximization)
2.
Minimasi (minimization)
Solusi optimum (terbaik)
adalah solusi yang bernilai minimum atau maksimum dari sekumpulan alternatif
solusi yang mungkin. Solusi yang memenuhi semua kendala disebut solusi layak
(feasible solution). Solusi layak yang mengoptimumkan fungsi optimasi
disebut solusi optimum.
Algoritma Greedy
adalah algoritma yang memecahkan masalah pada setiap langkah per langkah, yaitu:
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
Skema
Umum Algoritma Greedy
Algoritma
greedy disusun oleh elemen-elemen berikut:
- Himpunan kandidat : Berisi elemen-elemen pembentuk solusi.
- Himpunan solusi : Berisi kandidat-kandidat yang terpilih sebagai solusi persoalan.
- Fungsi seleksi (selection function) : Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.
- Fungsi kelayakan (feasible) : Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.
- Fungsi obyektif, yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain).
Pada masalah penukaran
uang:
- Himpunan kandidat: himpunan koin yang merepresentasikan nilai 1, 5, 10, 25, paling sedikit mengandung satu koin untuk setiap nilai.
- Himpunan solusi: total nilai koin yang dipilih tepat sama jumlahnya dengan nilai uang yang ditukarkan.
- Fungsi seleksi: pilihlah koin yang bernilai tertinggi dari himpunan kandidat yang tersisa.
- Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar.
- Fungsi obyektif: jumlah koin yang digunakan minimum
Elemen-elemen algoritma
greedy:
1.
Himpunan kandidat, C.
2.
Himpunan solusi, S
3.
Fungsi seleksi (selection function)
4.
Fungsi kelayakan (feasible)
5.
Fungsi obyektif
Dengan
kata lain:
algoritma greedy melibatkan pencarian
sebuah himpunan bagian, S, dari himpunan kandidat, C; yang dalam
hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu
menyatakan suatu solusi dan S dioptimisasi oleh fungsi obyektif.
Pseudocode Umum
Algoritma Greedy
procedure
greedy(input C: himpunan_kandidat; output S :
himpunan_solusi)
{ menentukan solusi optimum dari
persoalan optimasi dengan algoritma greedy
Masukan:
himpunan kandidat C
Keluaran:
himpunan solusi S }
Deklarasi
x : kandidat;
Algoritma:
S⌐{} { inisialisasi S dengan kosong }
while (belum SOLUSI(S)) and (C 1 {} ) do
x⌐SELEKSI(C); { pilih sebuah kandidat dari C}
C⌐ C - {x} { elemen himpunan kandidat berkurang satu }
if
LAYAK(S È {x}) then
S⌐S È {x}
endif
endwhile
{SOLUSI(S) sudah diperoleh or
C = {} }
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).
Contoh Kasus Penukaran uang
Persoalan: Diberikan uang senilai A.
Tukar A dengan koin-koin uang yang
ada. Berapa jumlah minimum koin yang diperlukan untuk penukaran tersebut?
Contoh: tersedia koin-koin 1, 5, 10, dan 25
Uang senilai 32 dapat ditukar dengan 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)
… dan seterusnya
Minimum: 32 = 25 + 5 + 1 +
1 ) hanya 4 koin
Strategi greedy
yang digunakan adalah:
Pada setiap langkah, pilihlah koin dengan nilai sebesar
mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai
uang yang ditukarkan.
Tinjau masalah menukarkan uang 32 dengan koin 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!)
Pada setiap langkah di atas kita memperoleh optimum
lokal, dan pada akhir algoritma kita memperoleh optimum global (yang pada
contoh ini merupakan solusi optimum).
Contoh 2: 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)
Jika jawaban terbaik mutlak tidak diperlukan, maka
algoritma greedy sering berguna untuk menghasilkan solusi hampiran
(approximation), daripada menggunakan
algoritma yang lebih rumit untuk menghasilkan solusi yang eksak.
Bila algoritma greedy optimum, maka keoptimalannya itu
dapat dibuktikan secara matematis
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 = ∑i=1n (waktu di
dalam sistem)
Ekivalen dengan meminimumkan waktu rata-rata pelanggan di
dalam sistem.
Contoh Kasus Penjadwalan Pelanggan
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.
function
PenjadwalanPelanggan(input C : himpunan_pelanggan)à himpunan_pelanggan
{mengembalikan urutan jadwal pelayanan pelanggan yang
meminimumkan waktu di dalam system}
Deklarasi :
S :
himpunan pelanggan
i :
pelanggan
Algoritma:
Nß {}
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 peanggan yang akan diproses oleh
server tunggal
Masukan:n pelanggan, setiap pelanggan dinomori 1,2,…, n
Keluarn : urutan planggan yang dilayani}
Deklarasi:
i :integer
Algoritma :
{pelanggan 1,2,…, n sudah diurut naik berdasarkan ti}
For
i ß 1 to
n do
Output(i)
Endfor
Algoritma greedy untuk penjadwalan pelanggan akan selalu
menghasilkan solusi optimum.
Teorema. Jika t1 ≤ t2 ≤ … ≤ tn maka
pengurutan ij = j, 1 ≤ j ≤ n
meminimumkan
T
= ∑nk=1 ∑kk=j
tij
untuk semua
kemungkinan permutasi ij.
Knapsack
Maksimasi F = ∑ni=1 Pi X i
Dengan kendala (constraint)
∑ni=1 Wi Xi ≤ K
Yang dalam hal ini xi = 0 atau 1, i = 1,2,3…,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. Tinjau
persoalan 0/1 Knapsack dengan n = 4.
w1 = 2; p1 = 12
w2 =
5; p2 = 15
w3 =
10; p3 = 50
w4 =
5; p4 = 10
Kapasitas
knapsack W = 16
Solusi dengan algoritma greedy:
Properti objek
|
Greedy by
|
Solusi Optimal
|
|||||
i
|
Wi
|
Pi
|
Pi/
Wi
|
profit
|
weight
|
density
|
|
1
|
6
|
12
|
2
|
0
|
1
|
0
|
0
|
2
|
5
|
15
|
3
|
1
|
1
|
1
|
1
|
3
|
10
|
50
|
5
|
1
|
0
|
1
|
1
|
4
|
5
|
10
|
2
|
0
|
1
|
0
|
0
|
Total
bobot
|
15
|
16
|
15
|
15
|
|||
Total
keutungan
|
65
|
37
|
65
|
65
|
|||
Pada
contoh ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit dan density memberikan
solusi optimal, sedangkan pemilihan objek berdasarkan berat tidak memberikan
solusi optimal.
Kesimpulan
Algoritma greedy merupakan algoritma yang
besifat heuristik, mencari nilai maksimal sementara dengan harapan akan
mendapatkan solusi yang cukup baik. Meskipun tidak selalu mendapatkan solusi
terbaik (optimum), algoritma greedy umumnya memiliki kompleksitas waktu yang
cukup baik, sehingga algoritma ini sering digunakan untuk kasus yang memerlukan
solusi cepat meskipun tidak optimal seperti sistem real-time atau game.
Dari
impementasi yang kita lakukan, dapat dilihat bagaimana algoritma greedy
memiliki beberapa fungsionalitas dasar, yaitu:
1.
Fungsi untuk melakukan penelusuran masalah.
2.
Fungsi untuk memilih local maximum dari
pilihan-pilihan yang ada tiap langkahnya.
3.
Fungsi
untuk mengisikan nilai local maximum ke solusi keseluruhan.
4.
Fungsi yang menentukan apakah solusi telah
didapatkan.
Tentunya
fungsi-fungsi di atas juga dapat digabungkan atau dipecah lebih lanjut lagi,
menyesuaikan dengan strategi greedy yang dikembangkan.
Daftar Pustaka
Dikerjakan Oleh :
-
Shinta Oktaviana
-
Rekanur Arafah
-
Bella Noviani P
-
Zulfi Aprilia F
Tidak ada komentar:
Posting Komentar