PENGERTIAN METODE DIVIDE AND CONQUER

METODE

DIVIDE AND CONQUER

     1. 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 :

·         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 reurtfi ).

·         Combine : Menghubungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

     2.      Penerapan Algoritma

Pemecahan masalah Convex Hull dengan algoritma divide and conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma divide and conquer, sebagai generalisasi dari algoritma pengurutan mergesort.

            Adapun permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafik komputer, otomatis desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide And Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent.

    3.      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 Eculidean.

ü  Divide : bagi titik-titik itu ke dalam dua bagian, Pleft dan Pright, setiap bagian mempunyai jumlah titik yang sam.

ü  Conquer : secara rekurtif, terapkan algoritma D-and-C pada masing-masing bagian.

c.       Pasang titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

ü  Pasangan titik terdekat terdapat di bagian Pleft.

ü  Pasangan titik terdekat terdapat di bagian Pright;

ü  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.