METODE GREEDY , DIVIDE & CONQUER

1. METODE GREEDY

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)

Sekarang kita lanjut ke contoh soal yang aja ya biar lebih enak membedakan antara soal mengenai optimasi/maksimasi dengan minimum/minimasi.

Contoh Soal (Masalah Penukaran Uang) : 

Diberikan uang senilai A. Tukar A dengan Koin-Koin yang ada. Tersedia banyak Koin dengan jenis nilai koin 1,5,10, dan 25.

1. Persoalan Maksimasi

Berapa Jumlah Maksimum Koin yang diperlukan untuk Penukaran tersebut ?

2. Persoalan Minimasi

Berapa Jumlah Minimum Koin yang diperlukan untuk Penukaran tersebut ?

Penyelesaian :

1.      Maksimasi

Uang senilai A= 32 dapat ditukar dengan banyak cara berikut:

32 = 1 + 1 + …+ 1 (32 koin)

32 = 5 + 5 + 5 + 5 + 10 + 1 + 1 (7 koin)

32 = 10 + 10 + 10 + 1 + 1 (5 koin)… dst

2.     Minimum

32 = 25 + 5 + 1 + 1 (4 koin)

Algoritma greedy dalam menyelesaikan masalah dengan langkah per langkah “bertahap”.

Dengan definisi, Pada setiap langkah algoritma greedy :

1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan (prinsip “take what you can get now!” )
2. Berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global.

2. DEVIDE & CONQUER

Algoritma Divide and Conquer adalah strategi pemecahan masalah yang besar dengan cara melakukan pembagian masalah yang besar tersebut menjadi beberapa bagian yang lebih kecil secara rekursif hingga masalah tersebut dapat dipecahkan secara langsung. Solusi yang didapat dari setiap bagian kemudian digabungkan untuk membentuk sebuah solusi yang utuh.

Langkah-langkah umum algoritma Divide and Conquer :

1. Divide (Memecah): pada langkah ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil dan dapat diselesaikan dengan algoritma sederhana.
2. Conquer (Menaklukkan): dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
3. Combine (Menggabungkan): setelah menjalankan langkah conquer, tentunya kita harus menggabungkan kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.

Contoh Soal ( Persoalan Minimum dan Maksimum ) :

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

 




Penyelesaian :

Pertama, kita pisahkan terlebih dahulu elemen-elemen dari table A menjadi 2 bagian. Setelah itu kita tentukan mana nilai minimum dan maksimum dari tiap bagian. Kemudian gabungkan kembali 2 bagian tersebut menjadi satu. Lalu akan langsung terlihat mana nilai minimum dan maksimum dari table A diatas.

Referensi : 

http://herilovemetallica.blogspot.com/2010/04/algorima-greedy-dan-pembahasan-lengkap.html

http://bertzzie.com/knowledge/analisis-algoritma/DivideAndConquer.html

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