Algoritma Divide dan 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 independen, dan akhirnya menggabungkan solusi

masing-masing upamasalah sehingga menjadi solusi dari

masalah semula.

Pada algortima Divide and Conquer ini meiliki tiga proses

utama yaitu:

- Divide: membagi masalah menjadi beberapa upamasalah

yang memiliki kemiripan dengan masalah semula namun

berukuran lebih kecil (idealnya berukuran hampir sama),

- Conquer: memecahkan (menyelesaikan) masingmasing

upa-masalah (secara rekursif), dan

- Combine: mengabungkan solusi masing-masing upamasalah

sehingga membentuk solusi masalah semula.

Pada algoritma ini, 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.

Secara umum, algoritma Divide and Conquer memiliki

sekema sbb:

procedure DIVIDE_and_CONQUER(input n :

integer)

{ Menyelesaikan masalah dengan

algoritma Dand-

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

Dalam Algoritma divide dan 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.

STRATEGI DIVIDE DAN CONQUER

Metode

Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.

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. Ukuran dinyatakan 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 submasalah-submasalah 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. Searching

2. Sorting

Sumber : http://pdflost.com/download/5991507/