Struktur Data - Bagilah dan Taklukkan
Dalam pendekatan divide and conquer, masalah yang ada, dibagi menjadi sub-sub masalah yang lebih kecil dan kemudian setiap masalah diselesaikan secara mandiri. Ketika kita terus membagi subproblem menjadi sub-sub masalah yang lebih kecil, pada akhirnya kita mungkin mencapai tahap di mana tidak ada lagi pembagian yang memungkinkan. Sub-masalah (pecahan) sekecil mungkin yang "atomik" terpecahkan. Solusi dari semua sub masalah akhirnya digabungkan untuk mendapatkan solusi dari masalah asli.
Secara luas, kita bisa mengerti divide-and-conquer pendekatan dalam proses tiga langkah.
Bagilah / Pecahkan
Langkah ini melibatkan pemecahan masalah menjadi sub-masalah yang lebih kecil. Sub-masalah harus mewakili bagian dari masalah asli. Langkah ini umumnya mengambil pendekatan rekursif untuk membagi masalah sampai tidak ada sub-masalah yang dapat dibagi lagi. Pada tahap ini, sub-masalah menjadi atom di alam tetapi masih mewakili beberapa bagian dari masalah yang sebenarnya.
Taklukkan / Pecahkan
Langkah ini menerima banyak sub-masalah kecil yang harus diselesaikan. Umumnya, pada level ini, masalah dianggap 'terselesaikan' dengan sendirinya.
Gabung / Gabungkan
Ketika sub-masalah yang lebih kecil diselesaikan, tahap ini secara rekursif menggabungkan mereka sampai mereka merumuskan solusi dari masalah aslinya. Pendekatan algoritmik ini bekerja secara rekursif dan langkah-langkah menaklukkan & menggabungkan bekerja sangat dekat sehingga tampak sebagai satu kesatuan.
Contoh
Algoritme komputer berikut didasarkan pada divide-and-conquer pendekatan pemrograman -
- Gabungkan Sortir
- Sortir Cepat
- Pencarian Biner
- Perkalian Matriks Strassen
- Pasangan terdekat (poin)
Ada berbagai cara yang tersedia untuk menyelesaikan masalah komputer apa pun, tetapi yang disebutkan adalah contoh yang baik dari pendekatan divide and conquer.