METODE GREEDY

Metode Greedy digunakan 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 dan input data yang terdiri dari beberapa fungsi pembatas & 1 fungsi tujuan yang diselesaikan dengan memilih beberapa solusi yang 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

a.     Permasalahan Bagamana mengoptimalisasi storage/memory dalam komputer agar data yg disimpan dapat termuat dgn optimal.

b.     Misalkan terdapat n program yang akan disimpan didalam pita (tape).Pita tersebut mempunyai panjang maksimal sebesar L, masing-masing program yang akan disimpan mempunyai panjang L1,L2,L3...,Ln. Cara penyimpanan adalah penyimpanan secara terurut (sequential).

Persoalannya :

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

Pemecahannya :

 jika program-program tersebut disimpan dlm Order, dimisalkan adalah Order I, yaitu : jsama dengan Σtik maka akan didapat k=1.

Contoh soal :

Misal terdapat 3 buah program.(n=3) yg masing-masing mempunyai panjang program (I1,I2,I3)=(5,10,3). Tentukan urutan penyimpanannya secara berurutan (sequential) agar optimal....?

          Penyelesaiannya :

Dari 3 program tersebut akan didapat 6 buah kemungkinan order, yg didapat dari 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

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 yang akan dimuat dr N obyek yang ada sehingga nilai obyek termuat jumlahnya sesuai dengan kapasitas (≤M).

    Jika semua obyek harus dimuat kedalam ransel maka berapa bagian dr setiap obyek yang ada dapat dimuat kedalam ransel sedemikian sehingga nilai kum. maks. & sesuai dengan kapasitas ransel.

Penyelesaian Knapsack Problem :

1. Dengan Secara Matematika

2. Dengan Kriteria Greedy.

3. Dengan Algoritma Pemrograman Greedy

Penyelesaian Knapsack Dengan SecaraMatematika :

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 kapasitas nya tdk melebihi dr jumlah maks.daya tampung ransel.

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 terbesa

Penyelesaiannya

:

Dengan Kriteria

Greedy.

Diketahui bahwa kapasitas M = 20kg ,Dengan jumlah barang n=3 ,Berat Wi masing-masing barang (1, W2, W3) = (18, 15, 10),Nilai Pi masing-masing barang (P1, P2, P3) = (25, 24, 15).

Pilih barang dengan Nilai Profit Maksimal

v P1 = 25       X1 = 1, dimisalkan sebagai batas atas nilai

v P2 = 24       X2 = 2/15, dihitung dengan Fungsi Pembatas

v P3 = 15       X3 = 0, dimisalkan sebagai batas bawah nilai

Pilih barang dengan Berat Minimal

v W1 = 18

X1 = 0, sebagai batas bawah

v W2 = 15

X2 = 2/3,dihitung dgn Fungsi Pembatas

v 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 :

v P1/W1 = 25/18

karena terkecil maka X1 = 0

v P2/W2 = 24/15

karena terbesar maka X2 = 1

v P3/W3 = 15/10

dengan Fungsi pembatas X3 = 1/2

Dibuatkan tabel berdasarkan elemen dr

ke-3 kriteria metode Greedy

Solusi ke

Nilai profit maksimal = 31.5 dengan komposisi

yang sama

soal & penyelesaian menggunakan metode greedy

1. Kita diberikan sebuah knapsack (ransel) yang dapat menampung berat maksimum 15 Kg dan sehimpunan benda A = {a₀, a₁, a₂, a₃} yang berbobot (dalam Kg) W = {5,9,2,4}. Setiap benda tersebut diberikan nilai profit P = {100, 135, 26, 20}. Jika kita diperbolehkan memasukkan zi 

bagian dari benda ai yang ada ke dalam knapsack dimana 0 ≤ zi ≤ 1 , maka tentukanlah Z = {z0,z1,z2,z3} agar diperoleh total profit yang maksimal !

Jawab :

dik : n = 4; M = 15;

        W = { 5,9,2,4 };

        P = { 100,135,26,20 },

 dit : total profit yang maksimal ?

Barang ke -	Berat(Wi)	Keuntungan(Pi)	Pi/Wi
Z0	5	100	20
Z1	9	135	15
Z2	2	26	13
Z3	4	20	5

Z ← 0

cu ← 15

i = 0

karena W(0) 〈 cu yaitu : 5 〈 15 berarti : Z(0) ← 1

cu ← 15 - 5 = 10

i = 1

karena W(1) 〈 cu yaitu : 9 〈 10 berarti : Z(1) ← 1

cu ← 10 - 9 = 1

i = 2

karena W(2) 〉 cu yaitu : 2 〉 1 berarti : keluar dari loop (exit)

Karena 2 ≤ 3 maka Z(2) ← cu/W(2) = 1/2 = 0,5

Jadi optimisasi masalah knapsack diperoleh bila Z = { 1; 1; 0,5; 0 }

Sehingga Q = 1 x 100 + 1 x 135 + 0,5 x 26 + 0 x 20

= 100 + 135 + 13 + 0

= 248

ALGORITMA DIVIDE DAN CONQUER

Divide: membagi persoalan menjadi beberapa upa-masalah yang memiliki kemiripan dengan  persoalan semula namun berukuran lebih kecil (idealnya berukuran hampir sama).

Conquer (solve): memecahkan (menyelesaikan) masing-masing upa-masalah secara rekursif

Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi  persoalan semula

 Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.

      

Skema umum Algoritma Divide and Conquer

>> Persoalan Minimum dan Maksimum (MinMaks)

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

Ide dasar algoritma secara Divide and Conquer :

Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,

SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.

CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.

COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

Penyelesaian dengan Algoritma Divide and Conquer secara umum :

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

- SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.

- DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama

- CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

- Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

Pasangan titik terdekat terdapat di bagian PLeft.

Pasangan titik terdekat terdapat di bagian PRight.

Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

http://www.academia.edu/8719785/Modul_11._Algoritma_Divide_and_Conquer