Metode Greedy Dan Divide and Conguer

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 and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

• 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

http://herdijulianto.blogspot.com/2011/12/algoritma-devide-and-conquer-d-and-c.html

http://wawanhermawan74.blogspot.com/2012/10/contoh-kasus-algoritma-divide-and.html