Algoritma DIVIDE & CONQUER

Algoritma Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk di selesaikan. Berbeda dengan metode Greedy yang menyeleksi per data. Algoritma Divide and Conquer menyeleksi data per blok-blok besar. Langkah-langkah umum algoritma Divide and Conquer :

1.   Divide = Membagi masalah menjadi beberapa sub-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil. Usahakan sub masalah berukuran sama besar.
2. Conquer = Memecahkan masing-masing sub-masalah berdasarkan kondisi yang di tentukan.
3. Combine = Menggabungkan solusi masing-masing sub-masalah sehingga membentuk solusi masalah semula.

Rumus umum Divide and Conquer :

CONTOH SOAL :

Himpunan A merupakan himpunan pasangan terurut (x,y), yaitu {(3,2),(5,2),(2,0),(4,2)}. Dari data-data tersebut akan ditentukan suatu pasangan terurut yang memiliki jumlah x dan y yang minimum. Adapun batasan dari x dan y masing-masing lebih besar dari nol.

Jawaban

Kita punya 4 data dan kita bagi menjadi 2 sub masalah

{(3,2),(5,2)} dan {(2,0),(4,2)}

Kondisi yang harus terpenuhi untuk masuk ke proses perbandingan adalah x dany > 0 seleksi dari masing-masing sub masalah mana yang tidak memenuhi kondisi di atas. Berarti (2,0) tidak memenuhi kondisi tersebut.

Sisanya {(3,2),(5,2)} dan {(4,2)}

 Berikutnya kita akan mencari nilai minimum dari x+y Tambahkan masing-masing x dan y dari kedua sub masalah tersebut.

{(3+2=5), (5+2=7)} dan {(4+2=6)}

Maka nilai minimum di dapat yaitu 5. Dan pasangan minimum adalah (3,2).