Metode Greedy & Algoritma Divide and Conquer

1.     Metode Greedy

A.    Pengertian

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.

B.     Contoh Persoalan dan Penyelesaiannya

Misalkan tersedia koin : 1, 3, 5.

Uang senilai X=8 dapat di tukar dengan cara :

1+1+1+1+1+1+1+1 = 8 (8 koin)

1+1+1+1+1+3=8 (6 koin)

1+1+1+5=8 (4 koin)

1+1+3+3=8 (4 koin)

3+5=8 (2 koin)      

Maka solusi optimal dari kasus penukaran koin di atas adalah 2 koin.

2.     Algoritma Divide and Conquer

A.    Pengertian

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. 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:

A.    Divide

Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).

B.     Conquer

Memecahkan ( menyelesaikan ) masing-masing upa-masalah  (secara rekursif).

C.     Combine

Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

B.     Contoh Persoalan dan Penyelesaiannya

Diberikan himpunan titik, P, yang terdiri dari n buah titik, (xi,yi), pada bilangan 2-D. Tentukan jarak terdekat antara dua buah titik di dalam himpunan P. Jarak dua buah titik p1 = (x1, y1) dan p2 = (x2, y2) :

Penyelesaian dengan Algoritma Divide and Conquer :

a. Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b. Algoritma Closest Pair :

·         SOLVE : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Euclidean.

·         DIVIDE : Bagi titik-titik itu ke dalam dua bagian, PLeft dan PRight, setiap bagian mempunyai jumlah titik yang sama

·         CONQUER :Secara rekursif, terapkan algoritma D-and-C pada masingmasing bagian.

·          Pasangan titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

1.      Pasangan titik terdekat terdapat di bagian PLeft.

2.      Pasangan titik terdekat terdapat di bagian PRight.

3.    Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di PLeft dan satu titik di PRight.

Jika kasusnya adalah (c), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.