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.