Metode Greedy

Nama :  Rahman Azis
Npm   : 58414787
Kelas  : 1IA24

Algoritma greedy merupakan salah satu dari sekian banyak algoritma yang sering di pakai dalam implementasi sebuah system atau program yang menyangkut mengenai pencarian “optimasi” Di dalam mencari sebuah solusi (optimasi) algoritma greedy hanya memakai 2 buah macam persoalan Optimasi,yaitu: 

1. Maksimasi (maxizimation) 

2. Minimasi (minimization)

Skema Umum Algoritma Greedy

Skema Umum Algoritma Greedy

Algoritma greedy disusun oleh elemen-elemen berikut:

1. Himpunan kandidat: Berisi elemen-elemen pembentuk solusi.

2. Himpunan solusi: Berisi kandidat-kandidat yang terpilih sebagai solusi  persoalan.

3. Fungsi seleksi (selection function): Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

4. Fungsi kelayakan (feasible): Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak dibuang dan tidak pernah dipertimbangkan lagi.

5. Fungsi obyektif: yaitu fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain)..

Latihan :

Diketahui 3 buah benda dan sebuah knapsack dengan kapasitas maksimum 20. Berat dan profit dari masing-masing benda tersebut adalah (18, 15, 10) dan (25, 24, 15). Tentukanlah Z agar diperoleh total profit yang maksimal !

Jawab :

Pertama, kita periksa apakah rasio pi/wi -nya tidak menaik.

p0/w0 = 25/18

p1/w1 = 24/15

p2/w2 = 15/10

Terlihat bahwa syarat rasio pi/wi -nya tidak menaik belum terpenuhi. Jadi susunan (urutan) -nya untuk sementara kita ubah, agar syarat rasio pi/wi -nya tidak menaik terpenuhi dan kita dapat menyelesaikan masalah tersebut dengan procedure GREEDY_KNAPSACK.

Untuk itu, kita ubah sementara urutan benda-bendanya (setelah diperoleh jawaban sementara, kita kembalikan urutan ke susunan semula). Perubahan yang kita lakukan adalah sebagai berikut :

urutan ke- (yang lama)	urutan ke- (yang baru)
0	2
1	0
2	1

sehingga syaratnya terpenuhi ;

24/15 〉 15/10 〉 25/18 → rasio pi/wi -nya tidak menaik

Sekarang kita sudah dapat menggunakan procedure GREEDY_KNAPSACK untuk menyelesaikan masalah tersebut. Adapun hasil trace-nya adalah sebagai berikut :

Z ← 0

cu ← 20

i = 0

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

cu ← 20 - 15 = 5

i = 1

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

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

Jadi diperoleh : Z(0) = 1 ; Z(1) = 0,5 ; Z(2) = 0

Sekarang urutannya kita kembalikan seperti semula, yakni :

Logika

urutan ke- (yang saat ini)	urutan ke- (yang semula)	Z(i)
2	0	0
1	1	1
0	2	0,5

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

Sehingga Q = 0 x 25 + 1 x 24 + 0,5 x 15

= 0 + 24 + 7,5

= 31,5