Entre las diferentes técnicas algorítmicas que existen, divide y conquistarás es una de las fiables para la resolución de distintos problemas en tres etapas importantes: separar, analizar y resolver. Con esto, se puede lograr una solución de una forma más entendible y fácil de mantener.
Es una práctica muy común que siempre se intente buscar la solución a un problema pensando en este como uno solo, cuando puede ser visto como un conjunto de pequeños problemas que juntos resuelvan el problema general. Es importante tener en cuenta que, cuando es posible tomar un problema entero y encontrar su solución, es un mejor hábito; tanto para mayor compresión y mantenimiento, reducirlo, solucionar varios problemas pequeños y finalmente juntar los resultados de estos.
Para divide y vencerás, se reduce el problema en partes más pequeñas para resolverlas en el momento que sea adecuado según corresponda. La forma de ejercer esta técnica algorítmica consiste en tres etapas:
-
Separar: Separa la entrada inicial en subconjuntos más pequeños donde cada uno de ellos es analizado y si para estos es posible ejecutar acciones específicas.
-
Resolver: Se resuelven cada una de las partes o subconjuntos que fueron encontrados en la primera etapa.
-
Combinar: Se combinan todos los resultados de los subconjuntos anteriores para dar una respuesta final al problema entero.
Existe, también, una forma similar con unas ligeras diferencias. Este es denominado reduce y vencerás. Este toma aquello que no se puede resolver en un solo paso, y lo convierte en un problema de un tamaño más sencillo para poder resolverlo.
Es una variación de divide y vencerás en donde lo que se quiere hacer es tomar un conjunto de datos de entrada que es muy grande e ir eliminando candidatos en grupos lo más grande posible de forma que al eliminarlos se vaya reduciendo el subconjunto de candidatos disponibles, que son posibles candidatos a solución, hasta que encuentre la solución específica. De la misma forma que divide y vencerás, se divide en tres etapas:
-
Descartar: Se debe determinar si el problema permite hacer descarte. Se debe tomar el conjunto inicial de entradas posibles y aplicar un proceso de análisis sobre ese conjunto que permita eliminar la mayor cantidad de opciones posibles sin tener que analizarlas todas.
-
Analizar: Establece si es posible aplicar el proceso de determinación de la solución, en otras palabras, si es posible ejecutar la acción específica para su resolución.
-
Resolver: Este busca una solución sobre con el conjunto de datos pequeño del final.
Es entendible la importancia que posee esta técnica al estar debidamente estructurada y evidencia resultados. Aunque no nos demos cuenta, es posible que día a día apliquemos esta técnica para distintos escenarios ya que a veces se siente como un flujo natural.
Referencias
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Upper Saddle River, NJ, Estados Unidos: Prentice Hall.
Khan Academy. (s. f.). Algoritmos de divide y vencerás (artículo). Recuperado 19 de diciembre de 2020, de https://es.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithms
Peña, R. (s. f.). El Esquema «Divide y vencerás». En Algoritmos y Estructuras de Datos (pp. 97-118). https://www.cartagena99.com/recursos/alumnos/apuntes/Capitulo5.pdf