Algoritma Divide and Conquer
Algoritma
Divide and 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.
Divide dan conquer
secara umum terbagi menjadi tiga fase yaitu....
- Divide: membagi persoalan menjadi beberapa sub sub masalah yang memiliki kemiripan dengan persoalan semula namun berukuran lebih kecil(idealnya berukuran hampir sama)
- Conquer (solve): dalam langkah ini kita mencoba menyelesaikan masalah atau data yang telah dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
- Combine: menggabungkan solusi masing-masing sub sub masalah sehingga membentuk solusi atau hasil akhir dari persoalan semula.
Obyek
permasalahan yang dibagi adalah masukan (input)
atau instances yang berukuran n:
tabel (larik), matriks, eksponen, dan sebagainya, bergantung pada
masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik
masalah asal, sehingga metode Divide and
Conquer lebih natural diungkapkan dalam skema rekursif.
Ada 4 hal penting yang
harus dipahami dalam strategi ini :
· Branching Factor
Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2.
Branching factor dalam algoritma divide and conquer adalah jumlah dari subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah nyata dari algoritma divide and conquer, didalam proses pembagian yang sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma komputasi geometric yang memiliki branching factor berjumlah 2.
· Balance
Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance).
Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and conquer yang seimbang (balance).
·
Data Dependence of Divide Function
Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah Pseudocode untuk model algoritma n-way divide and conquer subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide.
Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah Pseudocode untuk model algoritma n-way divide and conquer subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort yang akan membagi subproblem dengan fungsi data-dependent divide.
· Control Parallelism or Sequentiality
Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program.
Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem dieksekusi sesuai dengan perintah program.
Algoritma Divide and Conquer memiliki kelebihan yang
membuatnya banyak diterapkan dan digunakan dalam aplikasi-aplikasi dunia nyata,
diantaranya :
o 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.
o 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).
o Algoritma ini dapat bekerja secara paralel dan
dapat memaksimalkan penggunaan dari cache memory.
·
Contoh algoritma devide and conquer adalah pada
merge sort
o
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.
o
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.
o
Persoalan Minimum dan Maksimum ( MinMaks ), dan
o
Optimasi Konversi Bilangan Desimal Ke Biner
o
Mencari Pasangan titik yang jaraknya dekat (close pair)
sumber :
0 komentar