Algoritma Devide and Conquer - @ D and C

D ann C

(Devide and Conquer)

                  Buat para sobat blogger kali ini saya membahas lagi sedikit mengenai D and C ini. Padahal sudah pernah saya bahas juga sih di Algoritma Devide and Conquer, Namun saya rasa blom lengkap dengan bahasan dibawah ini. Saya harap bahasan saya yang kali ini bermanfaat bagi para blogger. :)
                  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.

Pada algoritma Divide and Conquer ini memiliki tiga proses utama yaitu :
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), dan
3. Combine: mengabungkan solusi masing-masing upa masalah sehingga membentuk solusi masalah semula.

Ada 4 hal penting yang harus dipahami dalam strategi ini :
Yakni branching factor, balance, data dependence of divide function dan sequentiality.

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

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

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

4. Control Parallelism or Sequentiality
                 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 :

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

Skema Umum Algoritma Divide and Conquer

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n <= n0 then {ukuran masalah sudah cukup kecil }
        SOLVE upa-masalah yang berukuran n ini
else
        Bagi menjadi r upa-masalah, masing-masing berukuran n/k
        for masing-masing dari r upa-masalah do
           DIVIDE_and_CONQUER(n/k)
        endfor
     COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }
endif