Definisi, Sejarah dan Cara Kerja Algoritma Divide and Conquer

 

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, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat digeneralisasi untuk permasalahan convex hull yang berdimensi lebih dari 3.

 

Definisi Devide and Conquer

• Divide: membagi persoalan menjadi beberapaupa-masalah yang memiliki kemiripan denganpersoalan semula namun berukuran lebih kecil(idealnya berukuran hampir sama)
• Conquer (solve): menyelesaikan masing-masingupa-masalah (secara langsung atau secararekursif).

Pengertian Algoritma Divide

• 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.
• 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 : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama ).

2.    Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara rekursif ).

3.    Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Algoritma Divide And Conquer ditemukan oleh seorang ilmuwan Rusiabernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya, Anatoliimenemukan algoritma yang lebih cepat untuk mengalikan dua buah bilangan bulatyang besar dengan kompleksitas O(nlog 3).

Algoritma Divide and Conquer memiliki kelebihan yang membuatnya banyak diterapkan dan digunakan dalam aplikasi-aplikasi dunia nyata, diantaranya :

• Mampu menyelesaikan masalah yang sulit, algoritma ini mampu menyelesaikan masalah rumit yang hingga kini masih cukup sulit dipecahkan oleh komputer biasa, seperti Tower of Hanoi Problem.
• Algoritma lebih efisien untuk beberapa kasus tertentu, misalnya kasus Fast Fourier Transform maupun Sorting dapat dilakukan dengan kompleksitas algoritma O(n log n) dari algoritma lainnya yang hanya mampu mencapai kompleksitas O (n2).
• Algoritma ini dapat bekerja secara paralel dan dapat memaksimalkan penggunaan dari cache memory.

Contoh algoritma devide and conquer adalah pada merge sort :

• Merge sort, seperti namanya, merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total yang telah kita lakukan sebelumnya, yaitu membagi-bagikan keseluruhan list menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan menggabungkannya kembali menjadi sebuah list besar.
• Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer : Permasalahan convex hull adalah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi desain, pengenalan pola (pattern recognition), dan penelitian operasi.
• Persoalan Minimum dan Maksimum ( MinMaks ), dan
• Optimasi Konversi Bilangan Desimal Ke Biner
• Mencari Pasangan titik yang jaraknya dekat (close pair)

Algoritma Divide and Conquer

Pemrogram bertanggung jawab atas implementasi solusi. Pembuatan
program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi
sub masalah – sub masalah yang dapat dikelola.
Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1.    Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2.    Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3.    Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:
a. Memenuhi keterhubungan logik antara elemen-elemen data.
b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.
4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

 

Strategy Divide and Conquer

Algoritma Divide and Conquer (DANDC) memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah–submasalah dapat diperoleh secara mudah. Solusi dari submasalah–submasalah kemudian digabung menjadi solusi dari seluruh masalah.

Prinsip dasar dari algoritma ini adalah dengan membagi n input menjadi k subset input yang berbeda (1 < k ≤n). Dari k subset input yang berbeda akan terdapat k subproblem. Setiap subproblem mempunyai solusinya masing-masing, sehingga akan diperoleh k subsolusi. Kemudian, dari k subsolusi akan diperoleh solusi yang optimal atau solusi yang diharapkan.

Jika subproblem dianggap masih terlalu besar, maka metode DANDCdapat digunakan lagi. Dalam keadaan tersebut, pemakaian ulang metodeDANDC dinyatakan menggunakan teknik rekursif.

Pemecahan n input menjadi k input sehingga menimbulkan k subproblem dapat dilakukan apabila k subproblem tersebut mempunyai sifat yang sama terhadap persoalan semula atau awalnya.

Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )
Var K : integer ;
If SMALL (i,j) then SOLVE (i,j)
Else begin
K : = DIVIDE (i,j)
COMBINE (DNC(i,k),DNC(k+1,j))
End if

Keterangan :

1.     SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukurandinyatakan sebagai telah berukuran kecil bergantung masalah.

2.    DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.

3.    COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.

Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :
T(n) = g (n), n kecil
2 T (n/2) + f (n), selainnya

dimana :

• T(n) adalah waktu untuk DNC dengan n masukan,
• g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan
• f(n) adalah waktu COMBINE.

 

Untuk algoritma divide dan conquer yang menghasilkan submasalahsubmasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.

Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :

1.    Sorting/Pengurutan > Quick Sort

2.    Searching/Pencarian > Binary Search

 

Kelebihan Metode Divide and Conquer

Algoritma divide and conquer mempunyai kelebihan yang dapat mengurangi kompleksitas pencarian solusi suatu masalah karena prinsip kerjanya yang membagi-bagi masalah menjadi upmasalah-upmasalah yang lebih kecil. Kelebihan tersebut banyak menguntungkan dari segi waktu, tenaga, dan sumberdaya. Salah satu penerapan dari algoritma ini adalah pada mekanisme komputer (atau mesin) paralel. Algoritma Divide And Conquer terbukti menampilkan hasil yang paling baik dan paling sesuai untuk komputer dengan hirarki memori tinggiserta memiliki cache.

Cache merupakan memori sementara komputer yang berfungsi untuk mempersingkat pengaksesan data. Masalah yang dihadapi komputer paralel antara lain adalah bagaimana membuat cache bekerja lebihefisien pada tiap-tiap komputer yang terhubung secara paralel. Tanpa strategi tertentu, kinerja cache pada komputer paralel akan memakan waktu yang lama karena ketika menemui suatu masalah, pemecahan harus dilakukan secara bergantian, satu per satu. Sedangkan komputer paralel menuntut semuaperangkatnya mampu bekerja secara paralel. Paralelitas tersebut dapat diatasi dengan penerapan algoritma Divide And Conquer yang memungkinkan pemecahan masalah secara independen, namun tetap konkuren.

 

Penerapan Algoritma

A) Pemecahan Masalah Convex Hull dengan Algoritma Divide and Conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma Divide and Conquer, hal ini dapat dipandangsebagai generalisasi dari algoritma pengurutan merge sort. Berikut ini merupakan garis besar gambaran dari algoritmanya:

• Pertama-tama lakukan pengurutan terhadap titik-titik dari himpunan S yang diberika berdasarkan koordinat absis-X, dengan kompleksitas waktu O(n log n).

• Jika |S| ≤ 3, maka lakukan pencarian convex hull secara brute-force dengan kompleksitas waktu O(1). (Basis).

• Jika tidak, partisi himpunan titik-titik pada S menjadi 2 buah himpunan A dan B, dimana A terdiri dari setengah jumlah dari |S| dan titik dengan koordinat absix-X yang terendah dan B terdiri dari setengah dari jumlah |S| dan titik dengan koordinat absis-X terbesar.

• Secara rekursif lakukan penghitungan terhadap HA = conv(A) dan HB = conv(B).

• Lakukan penggabungan (merge) terhadap kedua hull tersebut menjadi convex hull, H, dengan menghitung da mencari upper dan lower tangents untuk HA dan HB dengan mengabaikan semua titik yang berada diantara dua buah tangen ini.

 

Permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafika komputer, otomasi 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, dan akhirnya menggabungkan solusi masing-masing upa-masalah sehingga menjadi solusi dari masalah semula.

Algoritma Divide and Conquer merupakan salah satu solusi dalam penyelesaian masalah convex hull. Algoritma ini ternyata memiliki kompleksitas waktu yang cukup kecil dan efektif dalam menyelesaikan permasalahan ini (jika dibandingkan algoritma lain). Selain itu juga, algoritma ini dapat suntuk permasalahan convex hull yang berdimensi lebih dari 3.

 

B) Persoalan Minimum dan Maksimum (MinMaks)

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

Ide dasar algoritma secara Divide and Conquer :

 

Ukuran table hasil pembagian dapat dibuat cukup kecil sehingga mencari minimum dan maksimum dapat diselesaikan (SOLVE) secara lebih mudah. Dalam hal ini, ukuran kecil yang dipilih adalah 1 elemen atau 2 elemen.

Algoritma MinMaks :

1. Untuk kasus n = 1 atau n = 2,
SOLVE : Jika n = 1, maka min = maks = An. Jika n = 2, maka bandingkan kedua elemen untuk menentukan min dan maks.

2. Untuk kasus n > 2,

• DIVIDE : Bagi dua table A secara rekursif menjadi dua bagian yang berukuran sama, yaitu bagian kiri dan bagian kanan.
• CONQUER : Terapkan algoritma Divide and Conquer untuk masing-masing bagian, dalam hal ini min dan maks dari table bagian kiri dinyatakan dalam peubah min1 dan maks1, dan min dan maks dari table bagian kanan dinyatakan dalam peubah min2 dan maks2.
• COMBINE : Bandingkan min1 dan min2 untuk menentukan min table A, serta bandingkan maks1 dan maks2 untuk menentukan maks table A.

 

C) Optimasi Konversi Bilangan Desimal Ke Biner

Salah satu cara optimasi yang bias kita lakukan adalah membagi bilangan decimal yang hendak diubah dengan angka 8 ( bukan 2 ). Di sinilah prinsip algoritma Divide and Conquer kita gunakan untuk melakukan optimasi. Kita pecah-pecah angka decimal yang akan kita gunakan dengan cara membaginya dengan angka 8 secara berulang. Angka-angka sisa pembagian yang kita peroleh kemudian kita ubah ke dalam bilangan biner sebelum kita gabungkan menjadi hasil jawaban.

Karena angka pembagi yang kita pakai adalah 8 (23), maka kita dapat mengurangijumlah pembagian yang kita lakukan menjadi ± 1/3 dari jumlah semula. Hal ini tentu saja akan sangat berpengaruh pada kinerja dan waktu yang diperlukan oleh computer mengingat proses pembagian merupakan salah satu proses yang cukup rumit.

Tentu saja optimasi ini harus kita bayar dengan menangani konversi bilangan octal ke biner. Akan tetapi jika kita gunakan teknik perbandingan ( tanpa harus melakukan konversi secara manual ), maka proses ini akan menjadi sangat cepat dan mudah. Penerapan algoritma ini adalah dengan menggunakan sintaks case of. Begitu juga dengan permasalahan pemakaian memori ( kompleksitas ruang ) yang lebih besar yang muncul akibat penggunaan algoritma rekursif. Karena pada proses rekursif-nya kita tidak banyak menggunakan variable yang memerlukan tempat yang begitu besar, maka hal ini bias kita abaikan. Dengan penggunaan optimasi ini, maka seharusnya proses konversi akan lebih cepat karena pemangkasan jumlah pembagian yang dilakukan.

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 :

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