Algoritma Divide & Conquer

Divide dahulunya adalah strategi militer dengan nama Divide ut imperes, sekarang strategi itu menjadi strategi fundamental didalam ilmu komputer degan nama Divide and conquer.

• Divide yaitu membagi masalah menjadi beberapa sub-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).
• Conquer yaitu memecahkan atau menyelesaikan masing-masing sub-masalah (secara rekursif.

• Combine adalah mengabungkan solusi masing-masing sub-masalah sehingga membentuk solusi masalah semula.

Obyek permasalahan meliputi:
masukan input atau instances yang berukuran n seperti:

• tabel (larik)
• matriks
• eksponen
• dll ( tergantung pada permasalahannya)

Tiap-tiap sub masalah memiliki karaktersristik yang sama (the same type) dengan karakteristik masalah asal sehingga metode devide and conquer lebih natural diungkapkan dalam skema rekursif.

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://www.informatika.org/~rinaldi/Stmik/Algoritma%20Divide%20and%20Conquer.ppt
http://neni_rid.staff.gunadarma.ac.id/Downloads/files/14031/Pertemuan+ke+11+-+Divide+n+Conquer.