En el enfoque de divide y vencerás, el problema en cuestión, se divide en subproblemas más pequeños y luego cada problema se resuelve de forma independiente. Si seguimos dividiendo los subproblemas en subproblemas aún más pequeños, es posible que lleguemos a una etapa en la que no sea posible realizar más divisiones. Se resuelven esos subproblemas «atómicos» más pequeños posibles (fracciones). La solución de todos los subproblemas se fusiona finalmente para obtener la solución de un problema original.
En términos generales, podemos entender el enfoque de dividir y conquistar en un proceso de tres pasos.
Dividir/Romper
Este paso implica romper el problema en subproblemas más pequeños. Los subproblemas deben representar una parte del problema original. Este paso generalmente adopta un enfoque recursivo para dividir el problema hasta que ningún subproblema sea más divisible. En esta etapa, los subproblemas se convierten en atómicos por naturaleza, pero siguen representando alguna parte del problema real.
Conquistar/Solucionar
Este paso recibe una gran cantidad de subproblemas más pequeños para ser resueltos. Generalmente, en este nivel, los problemas se consideran «resueltos» por sí mismos.
Fusionar/Combinar
Cuando los subproblemas más pequeños están resueltos, esta etapa los combina recursivamente hasta formular una solución del problema original. Este enfoque algorítmico funciona de forma recursiva y conquistar & pasos de fusión funciona tan cerca que aparecen como uno.
Ejemplos
Los siguientes algoritmos informáticos se basan en el enfoque de programación divide y vencerás.conquer programming approach –
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (points)
Hay varias formas disponibles para resolver cualquier problema informático, pero las mencionadas son un buen ejemplo de enfoque de divide y vencerás.