MATERI LOGIKA DAN ALGORITMA PERTEMUAN KE-12

METODE GREEDY

Untuk mendapatkan solusi optimal dr permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain)

Proses Kerja Metode Greedy :
Untuk menyeselesaikan suatu permasalahan dgn n input data yg terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yg diselesaikan dgn memilih beberapa solusi yg mungkin (feasible solution/feasible sets), yaitu bila telah memenuhi fungsi tujuan/obyektif


Metode GREEDY digunakan dlm penyelesaian masalah - masalah :

1. Optimal On Tape Storage Problem

2. Knapsack Problem

3. Minimum Spanning Tree Problem

4. Shortest Path Problem.




1. Optimal Storage On Tapes Problem

Permasalahan Bagamana mengoptimalisasi storage/memory dalam komputer agar data yg disimpan dapat termuat dgn optimal.
Misalkan terdapat n program. yg akan disimpan didalam pita (tape).Pita tsb mempunyai panjang maks. sebesar L, masing2 prg. yg akan disimpan mempunyai panjang L1 ,L2 ,L3 ...,Ln . Cara penyimpanan adalah penyimpanan secara terurut (sequential).

Persoalan = Bagamana susunan penyimpanan program2 tersebut sehingga 
L1 + L2 + L3 + ... + Ln = L ? 

Pemecahannya = jika program. 2 tersebut disimpan dlm Order, dimisalkan adalah Order I, yaitu : j sama dengan ∑ tik maka akan didapat k=1

Contoh,
 Misal terdapat 3 buah prg.(n=3) yg masing2 mpy panjang prg. (I1 ,I2 ,I3 )=(5,10,3). Tentukan urutan penyimpanannya scr berurutan (sequential) agar optimal....!

Penyelesaiannya : Dari 3 program tersebut akan didapat 6 buah kemungkinan order, yg didapat dr nilai faktorial 3 3! (ingat faktorial n!).

Dari tabel tersebut, didapat Susunan / order yg optimal,sbb : 

susunan pertama untuk program ke tiga 

susunan kedua untuk program kesatu 

susunan ketiga untuk program kedua

METODE GREEDY (lanjutan) 

2. KNAPSACK Problem 
Kasus : Terdapat n obyek (Xi;i=1,2,3,....n) yang masing-masing mempunyai berat (weight)/ Wi & masing-masing memiliki nilai (profit)/Pi yg berbeda-beda. 

Masalah : 
*Bagamana obyek-obyek tersebut dimuat / dimasukan kedalam ransel (knapsack) yg mempunyai kapasitas maks. = M. Sehingga timbul permasalahan sbb: 
Bagaimana memilih obyek yg akan dimuat dr n obyek yg ada sehingga nilai obyek termuat jumlahnya sesuai dgn kapasitas(≤ M) 
*Jika semua obyek harus dimuat kedalam ransel maka berapa bagian dr setiap obyek yg ada dapat dimuat kedalam ransel sedemikian shg nilai kum. maks. & sesuai dgn kapasitas ransel ?

Penyelesaian Knapsack Problem : 
1.Dengan Secara Matematika 
2.Dengan Kriteria Greedy. 
3.Dengan Algoritma Pemrograman Greedy.

Penyelesaian Knapsack Dengan Secara Matematika 

Fungsi tujuan = fungsi utama/obyektif = fungsi yg mjd penyelesaian permasalahan dgn mendptkan solusi yg optimal. 

Solusi dimaksud = menemukan nilai/profit yg maks. utk jml obyek yg dimuat dlm ransel shg sesuai kapasitas. 

Fungsi pembatas = fungsi subyektif = fungsi yg bertujuan untuk memberikan batas maks. dr setiap obyek untuk dapat dimuat dalam ransel sehingga kapasitasnya tdk melebihi dr jumlah maks.daya tampung ransel.

Catatan : karena dengan menggunakan Matematikan sangat sulit dan rumit maka tidak dibahas lebih mendalam.

Penyelesaian Dengan Kriteria Greedy. 

Konsep dr kriteria yg ditawarkan oleh metode Greedy yaitu : 

*Pilih obyek (barang) dengan nilai Pi maximal atau terbesar 

*Pilih obyek (barang) dengan berat Wi minimal dahulu. 

*Pilih obyek (barang) dgn perbandingan nilai & berat yaitu Pi/Wi yang terbesar.

Penyelesaiannya : Dengan Kriteria Greedy. 
Diketahui bahwa kapasitas M = 20kg , Dengan jumlah barang n=3 
*Berat Wi masing-masing barang 
(W1 , W2 , W3 ) = (18, 15, 10) 

*Nilai Pi masing-masing barang 
(P1 , P2 , P3 ) = (25, 24, 15)

Pilih barang dengan Nilai Profit Maksimal 
P1 = 25 > X1 = 1, dimisalkan sebagai batas atas nilai 
P2 = 24 > X2 = 2/15, dihitung dengan Fungsi Pembatas 
P3 = 15 > X3 = 0, dimisalkan sebagai batas bawah nilai

Pilih barang dengan Berat Minimal 
W1 = 18 > X1 = 0, sebagai batas bawah 
W2 = 15 > X2 = 2/3,dihitung dgn Fungsi Pembatas 
W3 = 10 > X3 = 1, sebagai batas atas

Pilih barang dgn menghitung perbandingan yg terbesar dr Profit dibagi Berat (Pi/Wi) yg diurut secara tidak naik, yaitu : 
P1/W1 = 25/18 > karena terkecil maka X1 = 0 
P2/W2 = 24/15 > karena terbesar maka X2 = 1 
P3/W3 = 15/10 >dengan Fungsi pembatas X3 = 1/2.

Dibuatkan tabel berdasarkan elemen dr ke-3 kriteria metode Greedy

Nilai profit maksimal = 31.5 dengan komposisi yang sama