3:17 PM
METODE GREEDY
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.
arti kata greedy sendiri adalah RAKUS, namun maksud dari metode grredy adalah kita melihat solusi optimal lokal, atau solusi optimal yang tampak didepan mata, dengan harapan mendapatkan solusi optimal secara global atau secara keseluruhan
Metode greedy dipakai dalam masalah
1.Optimal On tape Storage Problem
2.Knapsack Problem
3.Minimum Spanning Tree Problem
4.Shortest Path Problem
Contohnya adalah :
Contoh Masalah Optimasi:
Penukaran Uang
Diberikan uang senilai X Tukar X dengan koin-koin uang yang ada.
Berapakah jumlah minimum koin yang diperlukan untuk penukaran uang tersebut.
Persoalan Minimasi.
Contoh 1: tersedia banyak koin 5, 10, 20, 25
150 = 5+ 5+ … + 5 (30 koin)
150 = 10+ 10+ ... + 10 (15 koin)
150 = 25 + 25 + ... + 25 (6 koin)
Minimum: 32 = 25 + 25 + ... + 25 (6 koin)
Kelebihan algoritma Greedy:
Prinsip pencarian lintasan terpendek memakai fungsi ” Seleksi” dan itu berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat.Sehingga, kita dapat sampai tepat waktu menuju tempat tujuan. Hasil analisis berdasarkan bobot-bobot yang berbeda, menunjukkan bahwa semakin banyak bobot yang diberikan, maka semakin akurat pula datayang dihasilkan. Sehingga menghasilkan waktu yang efisien.
-Kekurangan algoritma Greedy:
1.Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search).
2.Pemilihan fungsi SELEKSI: Mungkin saja terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja dengan benar dan menghasilkan solusi yang benar-benar optimum. Karena itu, pada sebagian masalah algoritma
Greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.
METODE DIVIDE AND CONGUER
- Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).
- Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).
- Combine : Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Skema Umum Algoritma Divide and Conquer
procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n <= n0 then {ukuran masalah sudah cukup kecil }
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi r upa-masalah, masing-masing berukuran n/k
for masing-masing dari r upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }
endif
Tidak ada komentar
Posting Komentar