Algoritma Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. 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 :
- Divide = Membagi masalah menjadi beberapa sub-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil. Usahakan sub masalah berukuran sama besar.
- Conquer = Memecahkan (menyelesaikan) masing-masing sub-masalah berdasarkan kondisi yang ditentukan.
- Combine = Menggabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.
Untuk lebih jelas mari masuk ke contoh soal
Himpunan A merupakan himpunan pasangan terurut (x,y), yaitu {(2,1),(3,2),(7,1),(1,0)}. 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.
Penyelesaian
Kita punya 4 data kita bagi menjadi 2 sub-masalah
{(2,1),(3,2)} dan {(7,1),(1,0)}
Kondisi yang harus terpenuhi untuk masuk ke prosess perbandingan adalah x dan y > 0
Seleksi dari masing-masing sub-masalah mana yang tidak memenuhi kondisi di atas.
Berarti (1,0) tidak memenuhi kondisi tersebut.
Sisanya
{(2,1),(3,2)} dan {(7,1)}
Langkah selanjutnya kita akan mencari nilai minimum dari x+y
Tambahkan masing-masing x dan y dari kedua sub-masalah tersebut.
{(2+1 = 3), (3+2 = 5)} dan {(7+1 = 8)}
Maka nilai minimum didapat yaitu 3
Jadi pasangan minimum adalah (2,1)
Begitulah cara menerapkan metode divide and conquer pada soal. Sekian =D
0 komentar:
Posting Komentar