Estructuras de datos: divide y vencerás
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. Cuando seguimos dividiendo los subproblemas en subproblemas aún más pequeños, es posible que finalmente lleguemos a una etapa en la que no sea posible más división. Se resuelven esos subproblemas (fracciones) más pequeños "atómicos". La solución de todos los subproblemas finalmente se fusiona para obtener la solución de un problema original.
En general, podemos entender divide-and-conquer enfoque en un proceso de tres pasos.
Dividir / romper
Este paso implica dividir el problema en subproblemas más pequeños. Los subproblemas deben representar una parte del problema original. Este paso generalmente toma un enfoque recursivo para dividir el problema hasta que ningún subproblema sea más divisible. En esta etapa, los subproblemas se vuelven de naturaleza atómica pero aún representan una parte del problema real.
Conquistar / Resolver
Este paso recibe muchos subproblemas más pequeños que deben resolverse. Generalmente, en este nivel, los problemas se consideran "resueltos" por sí mismos.
Fusionar / Combinar
Cuando se resuelven los subproblemas más pequeños, esta etapa los combina recursivamente hasta que formulan una solución del problema original. Este enfoque algorítmico funciona de forma recursiva y los pasos de conquistar y fusionar funcionan tan cerca que parecen uno solo.
Ejemplos
Los siguientes algoritmos informáticos se basan en divide-and-conquer enfoque de programación -
- Combinar ordenar
- Ordenación rápida
- Búsqueda binaria
- Multiplicación de matrices de Strassen
- Par más cercano (puntos)
Hay varias formas disponibles para resolver cualquier problema informático, pero las mencionadas son un buen ejemplo del enfoque de divide y vencerás.