Metode Greedy

Metode Greedy digunakan untuk memecahkan persoalan optimasi.

Persoalan optimasi adalah persoalan mencari solusi optimum.

Persoalan optimasi ada 2 yaitu persoalan Maksimasi dan persoalan Minimasi.

 

Contoh Masalah Optimasi:

 

 

 

Pada Kasus Penukaran Uang

Diberikan uang senilai A. Tukar A dengan koin-koin uang yang ada.

Berapakah jumlah minimum koin yang diperlukan untuk penukaran uang tersebut. Ini adalah contoh Persoalan Minimasi.

 

Contoh:

Terdapat koin 5, 10, 25, 50. Jika sejumlah uang sebesar 65 ingin ditukarkan dengan koin, berapa minimal koin yang didapat.

 

65 = 5 + 5 + … + 5                                     (13 koin)

65 = 10 + 5 + 5 + 5 + 5 + .. + 5            (12 koin)

65 = 10 + 10 + 5 + 5 + 5 + .. + 5          (11 koin)

65 = 10 + 10 + .. + 10 + 5                       (7 koin)

65 = 25 + 25 + 10 + 5                              (4 koin)

65 = 50 + 5 + 5 + 5                                   (4 koin)

65 = 50 + 10 + 5                                        (3 koin)

Minimum: 65 = 50 + 10 + 5                (3 koin)

 

Jika pertanyaannya berapa maksimal koin yang didapat maka jawabannya adalah 13 koin dengan kombinasi 5 + 5 + 5 + 5 + .. + 5

 

Greedy = rakus, tamak

Algoritma greedy membentuk solusi langkah  per langkah. Pada setiap langkah terdapat banyak pilihan yang perlu dieksplorasi. Sehingga, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan (keputusan yang telah diambil pada suatu langkah tidak dapat diubah lagi pada langkah selanjutnya). Pada setiap langkah  membuat pilihan optimum lokal dengan harapan bahwa langkah sisanya mengarah kesolusi optimum global.

 

Metode  Greedy dapat digunakan dalam menyelesaikan permasalahan:

• Optimal Storage on Tapes Problem
• Knapsack Problem
• Minimum Spanning Tree Problem
• Shortest Path Problem