Materi tentang Algoritma Greedy (Beserta dengan Langkah-langkahnya)
Assalammu‘alaikum wr. wb.
Hello guys, Kembali lagi bersama Inzaghi's Blog! Jika kalian ingin menyelesaikan suatu masalah, pasti harus ada solusi. Salah satunya adalah dengan menggunakan Algoritma Greedy. Sebenarnya "Greedy" sendiri artinya "Rakus". Jadi jika diartikan secara harfiah, "Greedy Algorithm" berarti "Algoritma Rakus". Kok bisa Rakus ya? Untuk bisa menjawabnya, simak baik-baik pada Postingan kali ini.
Sumber Materi (Utama) : Informatika.STEI.ITB.ac.id (PDF), Tugasanalgo4blog.wordpress.com, dan 4bsiblog.wordpress.com
PENGERTIAN ALGORITMA GREEDY
A. Definisi Algoritma Greedy
Metode/Algoritma Greedy merupakan algoritma yang membentuk solusi langkah per langkah 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. Greedy sendiri diambil dari Bahasa Inggris yang artinya Rakus, Tamak atau Serakah.
B. Prinsip Utama Algoritma Greedy
Prinsip Utama dari Algoritma Greedy adalah “Take what you can get now!” yang berarti "Ambil apa yang bisa Anda dapatkan sekarang!". Maksud dari prinsip tersebut adalah sebagai berikut yaitu Pada setiap langkah dalam Algoritma Greedy, kita ambil keputusan yang paling optimal untuk langkah tersebut tanpa memperhatikan konsekuensi pada langkah selanjutnya. Sebagai contoh, jika kita manggunakan algoritma Greedy untuk menempatkan komponen diatas papan Sirkuit, sekali komponen telah diletakkan dan dipasang maka tidak dapat dipindahkan lagi. Kita namakan solusi tersebut dengan optimum lokal. Kemudian saat pengambilan nilai optimum lokal pada setiap langkah, diharapkan tercapai Optimum Global, yaitu tercapainya solusi optimum yang melibatkan keseluruhan langkah dari awal sampai akhir.
C. Skema umum Algoritma Greedy
Algoritma Greedy disusun oleh elemen, dan elemen-elemen yang digunakan dalam penerapan Algoritma Greedy antara lain :
1. Himpunan Kandidat
Himpunan yang berisi elemen pembentuk solusi.
2. Himpunan Solusi
Himpunan yang terpilih sebagai solusi persoalan.
3. Fungsi Seleksi
Fungsi yang memilih kandidat yang paling mungkin untuk mencapai solusi optimal.
4. Fungsi Kelayakan
Fungsi yang memeriksa apakah suatu kandidat yang dipilih dapat memberikan solusi yang layak. Maksudnya yaitu apakah kandidat tersebut bersama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala yang ada.
5. Fungsi Solusi
Fungsi yang mengembalikan nilai Boolean. True jika himpunan solusi yang sudah tebentuk merupakan solusi yang lengkap; False jika himpunan solusi belum lengkap.
6. Fungsi Objektif
Fungsi yang mengoptimalkan solusi.
Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu :
- Maksimasi (Maxizimation)
- Minimasi (Minimization)
CONTOH ALGORITMA GREEDY
A. Penukaran Uang
Sumber : Dosen.Perbanas.id dan Catatananalgo.Wordpress.com
Algoritma Greedy melibatkan pencarian sebuah himpunan bagian S dari himpunan bagian C, yang dalam hal ini, S harus memenuhi beberapa kriteria yang ditentukan, yaitu menyatakan suatu solusi dan S dioptimasi oleh fungsi obyektif. Contohnya adalah Penukaranan Uang, pada masalah penukaran Mata Uang :
- Himpunan Kandidat : Himpunan koin yang merepresentasikan nilai 1, 5, 10, dan 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 : Pililhlah nilai koin yang bernilai paling tinggi dari himpunan kandidat yang tersisa.
- Fungsi Layak : Memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang akan di tukarkan.
- Fungsi Obyektif : Jumlah koin yang digunakan minimum.
Berikut, inilah Pseudocode untuk Permasalahan Penukaran Uang :
function CoinExchange (input C: himpunan_Koin; A : integer) → himpunan_Koin
{
menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy
Masukan: himpunan kandidat C
Keluaran: himpunan solusi S
}
Deklarasi :
S : himpunan_Koin
x : Koin
Algoritma :
S ← {}
While (∑(nilai semua koin didalam S) ≠ A) and (C ≠ {}) do
x ← Koin yang mempunyai nilai terbesar
C ← C – {x}
If (∑ (nilai semua koin didalam S) + nilai koin x ≤ A Then
S ← S ∪ {x}
Endif
Endwhile
If (∑ (nilai semua koin didalam S) = A Then
Return S
Else
write (“tidak ada solusi”)
Endif
Endfunction
Contoh Kasus Penukaran Uang :
1. Terdapat Koin 1, 3, 4, 5. Jika sejumlah uang sebesar 7 ingin ditukarkan dengan koin, berapa minimal Koin yang didapat.
Uang yang ditukar : 7
Solusi Greedy : 7 = 5 + 1 + 1 (3 Koin) → tidak optimal
Solusi Optimal : 7 = 4 + 3 (2 Koin)
2. Terdapat Koin 1, 10, 15. Jika sejumlah uang sebesar 20 ingin ditukarkan dengan koin, berapa minimal Koin yang didapat.
Uang yang ditukar : 20
Solusi Greedy : 20 = 15 + 1 + 1 + 1 + 1 + 1 (6 Koin)
Solusi Optimal : 20 = 10 + 10 (2 koin)
3. Terdapat Koin 5, 10, 25, 50. Jika sejumlah uang sebesar 65 ingin ditukarkan dengan koin, berapa minimal Koin yang didapat.
65 = 5 + 5 + … + 5 (13 Koin)
65 = 10 + 5 + 5 + 5 + 5 + .. + 5 (12 Koin)
65 = 10 + 10 + 5 + 5 + 5 + .. + 5 (11 Koin)
65 = 10 + 10 + .. + 10 + 5 (7 Koin)
65 = 25 + 25 + 10 + 5 (4 Koin)
65 = 50 + 5 + 5 + 5 (4 Koin)
65 = 50 + 10 + 5 (3 Koin)
Minimum (Solusi Optimal) : 65 = 50 + 10 + 5 (3 Koin)
Jika pertanyaannya berapa maksimal koin yang didapat maka jawabannya adalah 13 Koin dengan kombinasi 5 + 5 + 5 + 5 + .. + 5
Penyelesaian dengan Exhaustive Search
Adapun penyelesaian dengan Exhaustive Search yaitu :
- 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
B. Penjadwalan
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.
Berikut, inilah Pseudocode untuk Permasalahan Penukaran Uang :
procedure PenjadwalanPelanggan(input n:integer)
{
Mencetak informasi deretan pelanggan yang akan diproses oleh server tunggal
Masukan: n pelangan, setiap pelanggan dinomori 1, 2, …, n
Keluaran: urutan pelanggan yang dilayani
}
Deklarasi :
i : integer
Algoritma :
{pelanggan 1, 2, …, n sudah diurut menaik berdasarkan ti}
for i←1 to n do
write(‘Pelanggan ‘, i, ‘ dilayani!’)
Endfor
Endfunction
Contoh untuk Kasus Penjadwalan :
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
============================================
Dan inilah Contoh lainnya :
C. Knapsack Problem
Istilah lain yang masih ada sangkut pautnya yaitu knapsnack problem. Knapsnack problem adalah masalah yang mana seseorang berhadapan dengan persoalan optimasi pemilihan benda mana yang bisa ditampung ke dalam suatu wadah berkapasitas terbatas. Adapun optimasi dimaksudkan agar dalam proses pemilihan benda mana yang hendak dimasukkan ke dalam suatu wadah yang dimaksud dihasilkan keuntungan semaksimal mungkin. Masing-masing dari benda yang hendak dimasukkan ini berat dan nilainya difungsikan dalam menentukan prioritasnya pada pemilihan tersebut.
Adapun nilai yang dimaksud bisa berupa harga barang, tingkat kepentingan, nilai sejarah dan lain-lain. Untuk wadah dalam bahasan ini mempunyai nilai konstanta sebagai nilai pembatas terhadap tiap-tiap benda yang hendak dimasukkan ke dalam wadah yang tersedia itu. Dalam hal ini ada sebuah tuntutan untuk menggunakan sebuah metode memasukkan benda yang dimaksud tersebut ke dalam sebuah wadah agar menghasilkan hasil yang optimal tetapi tidak melampaui kemampuan wadahnya.
Setelah mengetahui apa itu knapsnack problem, rasanya kurang lengkap jika tidak mengenal apa saja jenis-jenisnya. Jenis-jenis knapsnack problem bisa diamati dalam beberap variasi di antaranya :
- 0/1 Knapack problem dimana tiap barang cuma tersedia sebanyak 1 unit, ambil atau lepaskan begitu saja.
- Fracksional knapsack problem. Dalam hal ini barang bisa dibawa hanya sebagian. Jenis problem ini bisa masuk akal jika barang yang ada bisa dibagi-bagi seperti tepung, gula dan lain-lain.
- Bounded Knapsack problem. Pada jenis ini, masing-masing barang tersedia tersedia dalam N unit yang mana jumlahnya terbatas.
- Unbounded Knapshack problem. Untuk jenis Knapsack problem yang satu ini masing-masing barang yang tersedia jumlahnya minimal dua unit atau bahkan tak terbatas.
Pendekatan untuk Menyelesaikan Permasalahan Knapsack
Persoalan Knapsack merupakan suatu persoalan yang cukup menarik untuk diamati. Dalam kehidupan masalah knapsack kerap kali dijumpai pada bidang tertentu seperti pengangkutan barang (termasuk pengangkutan peti dalam kapal). Untuk urusan ini diharapkan adanya keuntungan maksimal yang diraih dalam usaha pengangkutan barang tersebut tanpa melebihi kapasitas yang tersedia. Maka dari itu, sebuah solusi sangat diharapkan mampu menyelesaikan persoalan tersebut. Sebagaimana diketahui, problem knapsack merupakan permasalahan pada optimasi kombinatorial yang mana anda harus menemukan solusi terbaik dari berbagai kemungkinan yang ada. Strategi yang diharapkan berperan dalam penuntasan masalah tersebut di antaranya sebagai berikut :
1. Brutal Force
Brutal Force merupakan pendekatan straightforward guna menyelesaikan masalah yang mana begitu bergantung pada definisi atas suatu konsep dana pernyataan masalah. Jika ada n item sebagai pilihannya, akan muncul 2 kemungkinan kombinasi yang dihasilkan item-item tersebut supaya diletakkan di knapsack. Dalam hal ini sebuah item bisa saja terpilih ataupun tidak terplih berdasarkan kombinasi tersebut. Selanjutnya, baik angka 0 maupun angka q akan dihidupkan sepanjang n. Apabila I menunjukkan angka itu artinya item demikian tidak terpilih sedangkan apabila angka 1, itu artinya item yang dimaksud dipilih.
2. Algoritma Greedy
Selanjutnya, terdapat Algoritma Greedy yang merupakan teknik pemrograman yang kerap kali digunakan dalam mengatasi permasalahan optimasi. Cara kerja algoritma ini yaitu dengan menggunakan heuristic dalam mencari sebuah solusi suboptimum dengan harapan solusi optimum. Algoritma Greedy ini memiliki tiga strategi dalam memilih objek mana yang hendak dimasukkan ke dalam wadah yang bernama knapsack. Ketiga strategi tersebut antara lain sebagai berikut.
- Algoritma Greedy by weight – Strategi ini menekankan pada bobot yang paling ringan dalam memasukkan suatu objek. Strategi ini berusaha memaksimalkan keuntungan dari banyaknya objek yang masuk. Dengan kata lain keuntungan akan diperoleh jika objek dimasukkan sebanyak mungkin ke dalam wadah knapsack. Mekanismenya dimulai dengan mengurutkan ke atas objek-objek yang dimaksud dengan mendasarkan pada beratnya. Berikutnya satu demi satu objek diambil hingga tak ada satu pun objek yang dapat dimasukkan atau algoritma knapsack penuh.
- Algoritma Greedy by profit – Teknik ini menekankan pada objek dengan keuntungan yang besar sebagai pengisi knapsack. Bisa dikatakan bahawa strategi ini berusaha memaksimalkan keuntungan dengan cara mendahulukan yang paling menguntungkan dalam memenuhi space yang tersedia. Prosesnya diawali dengan mengurutkan ke bawah objek-objek dengan mendasarkan pada profitnya. Barulah kemudian satu demi satu objek yang masih dapat ditampung dimasukkan ke dalam knapsack hingga tak ada lagi objek yang dapat dimasukkan atau knapsack penuh.
- Untuk menuntaskan macam-macam strategi dalam algoritma Greedy, yang terakhir yaitu Greedy by density. Strategi ini menekankan pada objek-objek dengan densitas terbesar dalam memenuhi wadah yang tersedia. Strategi ini berusaha memaksimalkan keuntungan yang ada dengan cara memilih objek dengan keuntungan tiap unit berat yang paling bear. Mekanismenya diawali dengan mencari nilai keuntungan per unit atau densisiy atas masing-masing objek. Selanjutnya, objek-objek yang dimaksud diurutkan dari segi densitynya. Barulah satu demi satu dari objek yang masih dapat ditampung dimasukkan hingga penuh ke dalam knapsack.
Setelah ketiga strategi yang telah disebutkan di atas diaplikasikan dan diuji, akan didapatkan hasil terbaik dengan menerapkan aturan ketiga, seperti memilih item yang memiliki nilai tinggi berdasarkan rasio bobot atas berat objek. Pemilihan objek yang didasarkan pada salah satu di antara ketiga strategi yang telah disebutkan sebelumnya memang tidak menjamin solusi optimal. Lain halnya dengan brutal force dimana strategi ini selalu mampu menghadirkan hasil optimal. Namun demikian, Greedy mengurangi banyaknya langkah pencarian.
Berikut, inilah Pseudocode untuk Knapsack Problem :
function Knapsack(input C : himpunan_objek, K : real) --> himpunan_solusi
{
648.044px; word-break: break-all;">Menghasilkan solusi persoalan knapsack dengan algoritma greedy yang menggunakan strategi pemilihan objek berdasarkan profit(pi),weight(wi),density (pi/wi). Solusi dinyatakan sebagai vektor X = x[1], x[2], …, x[n]. Asumsi: Untuk Greedy by profit seluruh objek sudah terurut berdasarkan nilai pi yang menurun. Untuk Greedy by weighted seluruh objek sudah terurut berdasarkan nilai wi yang menaik. Untuk Greedy by density seluruh objek sudah terurut berdasarkan nilai pi/wi yang menurun.}
}
Deklarasi :
i, TotalBobot : integer
Avalaible : boolean
x : himpunan_solusi
Algoritma :
for i←1 to n do
x[i] ← 0 { inisialisasi setiap status pengambilan objek i dengan 0 }
i ← 0
TotalBobot ← 0
Available ← true
while (i ≤ n) and (Available) do
{ cek objek ke-i }
i ← i + 1
if ( TotalBobot + w[i] ≤ K )
then
{ masukkan objek Ci ke dalam knapsack }
x[i] ← 1
TotalBobot ← TotalBobot + w[i]
else
Available ← false
x[i] ← 0
{ objek Ci tidak dimasukkan ke dalam knapsack }
Endif
Endwhile
{ i > n or not Available }
return x
Endfunction
Contoh :
Menentukan Solusi Knapsack Problem dan Fractional Knapsack Problem dengan K = 25, dengan himpunan berat tiap item, W = {24, 10, 10, 7} dan himpunan profit tiap item, P = {24, 18, 18, 10}
K = 25
a. Knapsack Problem
|
No.
|
W
|
P
|
d = P/W
|
w
|
p
|
d
|
Solusi
Optimal
|
|
1.
|
24
|
24
|
1
|
1
|
1
|
0
|
1
|
|
2.
|
10
|
18
|
1.8
|
0
|
0
|
1
|
0
|
|
3.
|
10
|
18
|
1.8
|
0
|
0
|
1
|
0
|
|
4.
|
7
|
10
|
1.4
|
0
|
0
|
0
|
0
|
|
Total Bobot
|
24
|
24
|
20
|
24
|
|||
|
Total Keuntungan
|
24
|
24
|
36
|
24
|
|||
W = 24
P = 24
D = 10+10 = 20
Solusi Optimal : X = {1, 0, 0, 0}
b. Fractional Knapsack Problem
|
No.
|
W
|
P
|
d = P/W
|
w
|
p
|
d
|
|
1.
|
24
|
24
|
1
|
1
|
1
|
0
|
|
2.
|
10
|
18
|
1.8
|
1/10
|
1/10
|
1
|
|
3.
|
10
|
18
|
1.8
|
0
|
0
|
1
|
|
4.
|
7
|
10
|
1.4
|
0
|
0
|
5/7
|
|
Total Bobot
|
25
|
25
|
25
|
|||
|
Total Keuntungan
|
25.8
|
25.8
|
43.1
|
|||
Solusi Optimal : X = {0, 1, 1, 5/7}
Itulah Materi tentang Algoritma Greedy yang telah saya sampaikan. Mohon maaf apabila ada kesalahan sedikitpun. Sebenarnya masih ada 2 (Dua) Materi Algoritma Greedy lainnya, yaitu Minimum Spanning Tree Problem dan Pemampatan Data. Tapi akan dibahasnnya di lain waktu.
Terima Kasih 😄😘👌👍 :)
Wassalammu‘alaikum wr. wb.
){kind=link}