Creator Media

Pengertian Metode Greedy Adalah :

• Metode Greedy adalah salah satu cara atau teknik merancang suatu algoritma. Metode Greedy digunakan untuk mendapatkan solusi optimal dari suatu permasalahan. Salah satu permasalahan yang dapat diselesaikan dalam metode Greedy adalah masalah Knapsack atau ransel untuk tempat penampungan. Masalah Knapsack atau ransel adalah bagaimana memilih atau menentukan dari sekian banyak objek dari beberapa objek yang ada yang dapat dimuat ke dalam ransel sedemikian sehingga mendapatkan nilai kumulatif yang paling maksimum dan sesuai dengan nilai kapasitas maksimum ransel.

Fungsi Metode Greedy

• Fungsi dari Metode Greedy adalah untuk mendapatkan solusi optimal dr permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain). Metode greedy adalah metode yang digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode greedy kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada. Algoritma Greedy adalah salah satu jenis algoritma yang menggunakan pendekatan penyelesaian masalah dengan mencari nilai maksimum sementara dalam setiaplangkahnya atau local maxium.Algoritma greedy biasanya memberikan solusi yang mendekati nilai optimum dalam waktuyang cukup cepat.

Proses Kerja Metode Greedy :

Untuk menyeselesaikan suatu permasalahan dgn n inputdata 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 :

• Optimal On Tape Storage Problem
• Knapsack Problem
• Minimum Spanning Tree Problem
• Shortest Path Problem.

• 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).

L1 L2 L3. . . Ln

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 S tik maka akan didapat k=1
n

• Mean Retrieval Time (MRT) = S tj /n
  j=1
  n j
• dan Optimal Storage = D(I) = S S lik
  j=1 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)

• 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 berbedabeda.

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 nobyek 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 Kanpsack 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.
  n
• Fungsi Tujuan Maksimum : Σ Pi Xi
  I=1
• 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.
• Fungsi Pembatas : Σ Wi Xi £ M i=1
  dimana : 0 £ Xi £ 1; Pi >0;Wi>0

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

Penyelesaian Dengan Kriteria Greedy.

Konsep dari kriteria yang ditawarkan oleh metode Greedy yaitu :

1. Pilih obyek (barang) dengan nilai Pi maximal atau terbesar
2. Pilih obyek (barang) dengan beratWi minimal dahulu.
3. Pilih obyek (barang) dgn perbandingan nilai & berat yaitu Pi/Wi yang terbesar.

Penyelesaiannya : Dengan KriteriaGreedy.

Diketahui bahwa kapasitas M = 20kg ,
Dengan jumlah barang n=3

• Berat Wi masing-masing barang
  (W , W , W ) = (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.

by Maket Creator

[popup_anything id=”1921″]