Metode Greedy

Metode Greedy

Metode ini sering digunakan untuk memecahkan persoalan optimasi, ada 2 macam persoalan optimasi, yaitu maksimasi dan minimasi, artinya dengan metode ini kita bemaksud mencari solusi terbaik, yaitu solusi yang benilai minimum atau maksimum dari sekumpulan alternatif solusi yang ada.

Arti kata greedy sendiri adalah Rakus atau Serakah, namun maksud dari metode ini adalah kita melihat solusi optimal lokal, atau solusi optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal secara global atau secara keseluruhan.

Contohnya adalah pada kasus penukaran uang, misalkan kita memiliki uang senilai 37 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.

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 + 10 + 1 + 1 = 37 (4 Koin) Sebenarnya ada beberapa alternatif solusi pemecahan masalah diatas sebagai berikut :

37 = 1 + 1 + 1 + 1 + ... (37 Koin)

37 = 10 + 10 + 10 + 5 + 1 + 1 (6 Koin)

37 = 5 + 5 + 5 + 5 + 5 + 10 + 1 + 1 (8 Koin)

Dalam hal ini metode greedy berhasil mendapat kan hasil maksimal secara global atau secara keseluruhan dengan mengambil koin yang terbesar terlebih dahulu.

Metode greedy dipakai dalam masalah
1.Optimal On tape Storage Problem
2.Knapsack Problem
3.Minimum Spanning Tree Problem
4.Shortest Path Problem

Source : http://bloglogika.blogspot.com/2010/12/metode-greedy.html