METODE GREEDY
Untuk mendapatkan solusi optimal dari permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain).
Proses Kerja Metode Greedy :
Untuk menyeselesaikan suatu permasalahan dengan N input data yg terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yg diselesaikan dengan memilih beberapa solusi yg mungkin (feasible
solution/feasible sets), yaitu bila telah memenuhi fungsi tujuan/obyektif.
Metode GREEDY digunakan dlm penyelesaian
masalah - masalah :
- Optimal On Tape Storage Problem
- Knapsack Problem
- Minimum Spanning Tree Problem
- Shortest Path Problem.
Optimal Storage on Tapes Problem
-Bagaimana mengoptimalkan penyimpanan, agar data yang disimpan dapat termuat dengan optimal.
-Bagaimana susunan yang harus dibentuk
Proses pemecahannya
1.nilai panjang data (L), waktu penyimpanan (t) dan waktu rata-rata (MRT) jika ada
2.Tentukan urutan penyimpanan datanya
3.Hitung total penyimpanan ( jika ada kapasitas media penyimpanan maka totaltidak boleh melebihi)
4.Pilih total yang minimum (sesuai dengan unsur efisiensi dan efektifitas)
Contoh Sederhana :
Contohnya adalah pada kasus penukaran uang, misalkan kita memiliki uang senilai 32 dan akan kita tukarkan dengan koin, uang koin pecahan yang tersedia adalah 1, 5, 10, 25, jika kita mengharapkan agar pecahan yang kita miliki sedikit mungkin maka kita bisa menggunakan metode greedy dengan cara memilih pecahan terbesar terlebih dahulu. mari kita lihat
uang 32. pecahan 1,5,10,25 dengan metode greedy kita harus memilih pecahan terbesar terlebih dahulu yaitu 25, kemudian baru mengambil sampai sesuai dengan uang yang kita miliki. yaitu= 25+5+1+1=32(4 koin) sebenarnya ada beberapa alternatif solusi pemecahan masalah diatas sebagai berikut
32=1+1+1+1+…+1 (32 koin)
32=5+5+5+5+10+1+1 (7koin)
32=10+10+10+1+1 (5koin)
Dalam hal ini metode greedy berhasil mendapat kan hasil maksimal secara global atau secara keseluruhan dengan mengambil koin yang terbesar terlebih dahulu.
Namun ada kalanya metode greedy gagal mendapatkan solusi optimal, hal ini juga dikarenakan oleh sifat metode greedy itu sendiri yang memperhatikan keuntungan lokal(diawal) tanpa memperhatikan kemungkinan solusi yang lain, contoh:
Uang yang ditukar sebesar 7
Koin yang tersedia 5,4,3, dan 1
jika kita menukarkan uang tersebut dengan metode greedy maka kita harus mengambil pecahan terbesar lebih dulu yaitu 5, baru kemudian kita memilih pecahan berikutnya hingga genap berjumlah 7
7=5+1+1 (3koin)
alternatif solusi
7=4+3 (2koin)
pada contoh diatas jelas terlihat bahwa metode greedy gagal memberikan solusi optimal.
Untuk mata uang dollar AS, euro Eropa, dan crown Swedia, algoritma greedy selalu memberikan solusi optimum. Misalnya untuk menukarkan $6,39 dengan uang kertas (bill) dan koin sen (cent), kita dapat memilih:
•Satu buah uang kertas senilai $5
•Satu buah uang kertas senilai $1 ($5 + $1 = $6))
•Satu koin 25 sen ($5 + $1 + 25c = $6,25)
•Satu koin 10 sen ($5 + $1 + 25c + 10c = $6,35)
•Empat koin 1 sen ($5 + $1 + 25c + 10c + 1c + 1c + 1c + 1c = $6,39)
Contoh 1:
Diketahui 3 program yang akan disimpan dalam media penyimpanan dengan panjangmasing-masing 5, 10, dan 3. Bagaimana proses penyimpanan yang optimal denganmetode greedy.
Jawab
1.Tentukan nilai panjang, waktu, dan waktu rata-rata
Ada 3 program, dimisalkan panjangnya L1, L2, dan L3 dengan nilai L1=5, L2=10, danL3=3Waktu, disini tidak diketahui, berarti dianggap waktu tidak mempengaruhi prosespenyimpanan, berarti tidak ada waktu rata-rata.Berarti dalam kasus ini yang berpengaruh ha nya panjang dari setiap datanya.
2.Urutan penyimpanan dengan menggunakan teknik faktorial sesuai dengan jumlahdata.
Dari kasus diketahui jumlah data (n) adalah 3, berarti kombinasi yang dibutuhkanadalah n!, yaitu 3!=3*2*1 = 6. Jadi dibutuhkan 6 langkah dalam prosespenyusunannya.
No Order D(L)Total1 1,2,3 5+(5+10)+(5+10+3) 382 1,3,2 5+(5+3)+(5+3+10) 313 2,1,3 10+(10+5)+(10+5+3) 434 2,3,1 10+(10+3)+(10+3+5) 415 3,1,2 3+(3+5)+(3+5+10) 296 3,2,1 3+(3+10)+(3+10+5) 34Ket. No:1 : Order 1 = 5Order 1, 2 =5+10Order 1,2,3 = 5+10+3Jadi Total Order 1,2,3 = 5+(5+10)+(5+10+3)
3.Dari nilai di atas didapat nilai minimal adalah
a.Nilai terkecil pertama adalah 29, yaitu untuk posisi penyimpanan urutan ke-3 padaposisi pertama
b.Nilai terkecil kedua adalah 31, yaitu untuk posisi penyimpanan urutan ke-1 padaposisi pertama
c. Nilai terkecil ketiga bukan 34 dan 38, sebab urutan penyimpanan pada posisi ke-3dan ke-1 sudah diwakili oleh 29 dan 31, sehingga untuk urutan ketiga adalah 41.
Knapsack
1. Tentukan Fungsi Tujuan, yaitu mencari nilai maximum dari jumlah hasil perkalian antara nilai profit (Pi) dengan nilai probabilitas (Xi)
Maximum ∑Pi.Xi
2. Tentukan Fungsi Pembatas, yang merupakan hasil penjumlahan dari perkalian antara bobot (Wi) dengan nilai probabilitas (Xi) yang tidak boleh melebihi dari kapasitas media penyimpanan (M)
∑Wi.Xi≤M, dimana
0≤Xi≤1, Pi>0, Wi>0
Dari ke-2 cara di atas berarti kita harus mengetahui
1. Jumlah objek (n)
2. Bobot setiap objek (Wi)
3. Profit setiap objek (Pi)
4. Probabilitas setiap objek (Xi), dan
5. Kapasitas media penyimpanan (M)
Seperti penulis sudah sampaikan di atas bahwa permasalahan knapsack ini bisa diselesaikan dengan 3 cara, yaitu matematika, kriteria greedy dan algoritma greedy.
Penulis mencoba untuk membahas satu persatu.
1. Cara Matematika, kita harus memperhatikan nilai probabilitas dari setiap barang, karena nilai inilah sebagai penentunya dengan memperhatikan nilai probabilitas (Xi) yaitu 0≤Xi≤1. Disini nilai Xi kisarannya sangat banyak bisa 0, 0.1, 0.01, 0.001, …., 1.
2. Kriteria greedy dengan memperhatikan:
a. Pilih objek dengan nilai profit terbesar (Pi)
b. Pilih objek dengan bobot terkecil (Wi)
c. Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
3. Algortima greedy, yaitu
PROCEDURE GREEDY KNAPSACK (P, W, X, n)
REAL P(1:n), W(1:n), X(1:n), M, isi
INTEGER i, n
X(1:n) = 0
isi = M
FOR i = 1 TO n DO
IF W(i) > isi THEN EXIT ENDIF
X(i) = 1
isi = isi – W(i)
REPEAT
IF i ≤ n THEN X(i) = isi/W(i) ENDIF
END GREEDY KNAPSACK
Teknik yang ke-3 ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan nilai Pi/Wi.
Contoh :
Diketahui 3 barang yang akan disimpan pada suatu tempat yang memiliki kapasitas maksimal sebesar 20 Kg. Berat masing-masing barang adalah 18 Kg, 15 Kg, dan 10 Kg dimana setiap barang memiliki profit sebesar masing-masing 25, 24, dan 15. Tentukan barang mana saja yang dapat disimpan ke dalam tempat penyimpanan sehingga diperoleh nilai profit yang maksimal.
Jawab
1. Cara matematika
n = 3, (1, 2, 3) objek
M = 20 kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X1, X2, X3) (W1. X1) + (W2. X2) + (W3. X3) ≤ M (P1. X1) + (P2. X2) + (P3. X3)
1 (1, 2/15, 0) (18.1) + (15.2/15) + (10.0) ≤ 20 (25.1) + (24.2/15) + (15.0)
20 28,2
2 (1, 0, 1/5) (18.1) + (15.0) + (10.1/5) ≤ 20 (25.1) + (24.0) + (15.1/5)
20 28
3 (0, 1, ½) (18.0) + (15.1) + (10.1/2) ≤ 20 (25.0) + (24.1) + (15.1/2)
20 31,5
4 (1/3, ½, ½) (18.1/3) + (15.1/2) + (10.1/2) ≤ 20 (25.1/3) + (24.1/2) + (15.1/2)
18,5 27,83
… …. …. ….
Dengan cara ini sulit untuk menentukan yang paling optimal sebab kita harus mencari nilai probabilitas yang tersebar antara 0 dan 1, 0 ≤ Xi ≤ 1 untuk setiap objek. Cara ini disarankan tidak digunakan.
2. Cara kriteria greedy
n = 3, (1, 2, 3) objek
M = 20 kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
Kriteria greedy :
a. Pilih objek dengan nilai profit terbesar (Pi)
Susun data sesuai kriteria:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X1, X2, X3) (W1. X1) + (W2. X2) + (W3. X3) ≤ M (P1. X1) + (P2. X2) + (P3. X3)
a (1, 2/15, 0) (18.1) + (15.2/15) + (10.0) ≤ 20 (25.1) + (24.2/15) + (15.0)
20 28,2
b. Pilih objek dengan bobot terkecil (Wi)
Susun data sesuai kriteria:
(P3, P2, P1) = (15, 24, 25)
(W3, W2, W1) = (10, 15, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X3, X2, X1) (W3. X3) + (W2. X2) + (W1. X1) ≤ M (P3. X3) + (P2. X2) + (P1. X1)
b (1, 2/3, 0) (10.1) + (15.2/3) + (18.0) ≤ 20 (15.1) + (24.2/3) + (25.0)
20 31
c. Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
Data yang diketahui:
(P1, P2, P3) = (25, 24, 15)
(W1, W2, W3) = (18, 15, 10)
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria:
(P2, P3, P1) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18)
Solusi ke Nilai Probabilitas Fungsi Pembatas Fungsi Tujuan
∑ Wi.Xi ≤ M ∑ Pi.Xi (Maximum)
(X2, X3, X1) (W2. X2) + (W3. X3) + (W1. X1) ≤ M (P2. X2) + (P3. X3) + (P1. X1)
c (1, 1/2, 0) (15.1) + (10.1/2) + (18.0) ≤ 20 (24.1) + (15.1/2) + (25.0)
20 31,5
Dari 3 kriteria di atas dapat disimpulkan bahwa fungsi tujuan yang bernilai maximum adalah 31,5 dengan fungsi pembatasnya adalah 20 dan nilai probabilitasnya adalah (X2, X3, X1) = (1, 1/2, 0), jadi disini yang memeberikan hasil optimal pada kriteria yang ke-3 yaitu Pilih objek dengan nilai perbandingan profit dengan bobot yang terbesar (Pi/Wi)
3. Cara algoritma greedy
Teknik ini akan efektif jika objek disusun secara tidak naik (non increasing) berdasarkan nilai Pi/Wi.
Data yang diketahui:
n = 3, (1, 2, 3) objek
M = 20 kapasitas
(W1, W2, W3) = (18, 15, 10)
(P1, P2, P3) = (25, 24, 15)
Nilai probabilitas 0 ≤ Xi ≤ 1
perbandingan profit dengan bobot
P1/ W1 = 25/18 = 1,39
P2/ W2 = 24/15 = 1,6
P3/ W3 = 15/10 = 1,5
Susun data sesuai kriteria (non increasing):
(P2, P3, P1) = (24, 15, 25) atau
(P1, P2, P3) = (24, 15, 25)
(W2, W3, W1) = (15, 10, 18) atau
(W1, W2, W3) = (15, 10, 18)
Masukkan nilai kriteria di atas ke dalam algoritma greedy
1. PROCEDURE GREEDY KNAPSACK (P, W, X, n) nama prosedur/proses
2. REAL P(1:n), W(1:n), X(1:n), M, isi variabel yang digunakan
3. INTEGER i, n variabel yang digunakan
4. X(1:n) = 0
5. isi = M
6. FOR i = 1 TO n DO
7. IF W(i) > isi THEN EXIT ENDIF
8. X(i) = 1
9. isi = isi – W(i)
10. REPEAT
11. IF i ≤ n THEN X(i) = isi/W(i) ENDIF
12. END GREEDY KNAPSACK akhir prosedur/proses
Proses kegiatan dimulai dari langkah ke- 4 sampai dengan 11.
X(1:3) = 0, artinya X(1)=0, X(2)=0, X(3)=0
isi = M = 20
Pengulangan untuk i = 1 sampai dengan 3
Untuk i = 1
Apakah W(1) > isi
Apakah 15 > 20, jawabnya tidak, karena tidak maka perintah dibawah IF dikerjakan.
X(1) = 1 nilai probabilitas untuk objek pada urutan pertama (X1)
isi = 20 – 15 = 5
REPEAT mengulang untuk perulangan FOR
Untuk i = 2
Apakah W(2) > isi
Apakah 15 > 5, jawabnya ya, karena ya maka perintah EXIT dikerjakan, yaitu keluar dari pengulangan/FOR dan mengerjakan perintah di bawah REPEAT.
Apakah 2 ≤ 3, jawabnya ya, karena ya maka X(2) = 5/10 = ½ nilai probabilitas untuk objek pada urutan kedua (X2).
Selesai (akhir dari prosedur greedy knapsack)
Berarti untuk nilai X(3) = 0 atau X3 = 0, sebab nilai probabilitas untuk objek ke-3 tidak pernah dicari.
Jadi
(P1, P2, P3) = (24, 15, 25)
(W1, W2, W3) = (15, 10, 18)
(X2, X3, X1) = (1, 1/2, 0)
Fungsi Pembatas :
∑ Wi.Xi ≤ M
(W1. X1) + (W2. X2) + (W3. X3) ≤ M
(15.1) + (10.1/2) + (18.0) ≤ 20
20 ≤ 20
Fungsi Tujuan :
∑ Pi.Xi = (P1. X1) + (P2. X2) + (P3. X3)
= (24.1) + (15.1/2) + (25.0)
= 31,5
PROBLEMA DAN MODEL GRAPH DALAM METODE
GREEDY ( Lanjutan )
1. TRAVELLING SALESMAN
Untuk menentukan waktu perjalanan seorang salesman seminimal mungkin.
Permasalahan:
Setiap minggu sekali, seorang petugas kantor telepon berkeliling untuk mengumpulkan coin-coin
pada telepon umum yang dipasang diberbagai tempat. Berangkat dari kantornya, ia mendatangi satu demi satu telepon umum tersebut dan akhirnya kembali ke kantor lagi. Masalahnya ia menginginkan suatu rute perjalanan dengan waktu minimal.
2. MINIMUM SPANNING TREE
Kasus MST Problem = m’cari min.biaya (cost) spanning tree dr setiap ruas (edge) graph yg m’btk pohon (tree).
Solusi dr p’masalah’ ini :
a. Dgn memilih ruas suatu graph yg memenuhi kriteria dr optimisasi yg m’hasilk’ biaya min.
b. Penambah’ dr setiap ruas pd seluruh ruas yg m’btk graph akan m’hasilk’ nilai/biaya yg kecil (minimum cost).
Kriteria2 dr spanning tree, yakni :
1. Setiap ruas pada graph harus terhubung (conected)
2. Setiap ruas pd graph hrs mpy nilai (label graph)
3. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)
3. SHORTEST PATH PROBLEM
Permasalahan : menghitung jalur terpendek dr sbh graph berarah.
Kriteria utk permasalahan jalur terpendek/SP problem tsb :
1. Setiap ruas pd graph hrs mpy nilai (label graph)
2. Setiap ruas pd graph tdk hrs terhubung (unconnected)
3. Setiap ruas pd graph tsb hrs mempunyai arah (graph berarah).
Download Data
Metode Greedy (Klik Disini)Sekian pembahasan dari Metode Greedy. Semoga bermamfaat dan terima kasih.
