En informática , el algoritmo divide y vencerás es un paradigma de diseño de algoritmos . Un algoritmo divide y vencerás divide recursivamente un problema en dos o más subproblemas del mismo tipo o de tipos relacionados, hasta que estos se vuelven lo suficientemente simples como para resolverlos directamente. Las soluciones a los subproblemas se combinan luego para dar una solución al problema original.
La técnica de dividir y vencer es la base de algoritmos eficientes para muchos problemas, como la ordenación (por ejemplo, quicksort , merge sort ), la multiplicación de números grandes (por ejemplo, el algoritmo Karatsuba ), la búsqueda del par de puntos más cercano , el análisis sintáctico (por ejemplo, los analizadores de arriba hacia abajo ) y el cálculo de la transformada de Fourier discreta ( FFT ). [1]
Diseñar algoritmos eficientes de divide y vencerás puede ser difícil. Como en la inducción matemática , a menudo es necesario generalizar el problema para que sea susceptible de una solución recursiva. La exactitud de un algoritmo de divide y vencerás suele demostrarse mediante inducción matemática, y su coste computacional suele determinarse mediante la resolución de relaciones de recurrencia .
El paradigma de divide y vencerás se utiliza a menudo para encontrar una solución óptima de un problema. Su idea básica es descomponer un problema dado en dos o más subproblemas similares, pero más simples, resolverlos uno por uno y componer sus soluciones para resolver el problema dado. Los problemas de suficiente simplicidad se resuelven directamente. Por ejemplo, para ordenar una lista dada de n números naturales , divídala en dos listas de aproximadamente n /2 números cada una, ordene cada una de ellas por turno e intercale ambos resultados de manera apropiada para obtener la versión ordenada de la lista dada (vea la imagen). Este enfoque se conoce como algoritmo de ordenación por fusión .
El nombre "divide y vencerás" se aplica a veces a algoritmos que reducen cada problema a un solo subproblema, como el algoritmo de búsqueda binaria para encontrar un registro en una lista ordenada (o su análogo en computación numérica , el algoritmo de bisección para encontrar la raíz ). [2] Estos algoritmos se pueden implementar de manera más eficiente que los algoritmos generales de divide y vencerás; en particular, si utilizan recursión de cola , se pueden convertir en bucles simples . Sin embargo, bajo esta definición amplia, todo algoritmo que utilice recursión o bucles podría considerarse un "algoritmo de divide y vencerás". Por lo tanto, algunos autores consideran que el nombre "divide y vencerás" debería usarse solo cuando cada problema pueda generar dos o más subproblemas. [3] En cambio, se ha propuesto el nombre de decremento y vencerás para la clase de un solo subproblema. [4]
Una aplicación importante de dividir y vencer es en la optimización, [ ejemplo necesario ] donde si el espacio de búsqueda se reduce ("poda") por un factor constante en cada paso, el algoritmo general tiene la misma complejidad asintótica que el paso de poda, y la constante depende del factor de poda (sumando las series geométricas ); esto se conoce como podar y buscar .
Los primeros ejemplos de estos algoritmos son principalmente de disminución y conquista: el problema original se divide sucesivamente en subproblemas individuales y, de hecho, se puede resolver de forma iterativa.
La búsqueda binaria , un algoritmo de disminución y conquista donde los subproblemas tienen aproximadamente la mitad del tamaño original, tiene una larga historia. Si bien una descripción clara del algoritmo en computadoras apareció en 1946 en un artículo de John Mauchly , la idea de usar una lista ordenada de elementos para facilitar la búsqueda se remonta al menos a Babilonia en el año 200 a. C. [5] Otro antiguo algoritmo de disminución y conquista es el algoritmo euclidiano para calcular el máximo común divisor de dos números reduciendo los números a subproblemas equivalentes cada vez más pequeños, que data de varios siglos antes de Cristo.
Un ejemplo temprano de un algoritmo de divide y vencerás con múltiples subproblemas es la descripción que hizo Gauss en 1805 de lo que ahora se denomina algoritmo de transformada rápida de Fourier (FFT) de Cooley-Tukey, [6] aunque no analizó cuantitativamente su número de operaciones y las FFT no se generalizaron hasta que fueron redescubiertas más de un siglo después.
Un algoritmo D&C de dos subproblemas temprano que fue desarrollado específicamente para computadoras y analizado adecuadamente es el algoritmo de ordenamiento por fusión , inventado por John von Neumann en 1945. [7]
Otro ejemplo notable es el algoritmo inventado por Anatolii A. Karatsuba en 1960 [8] que podía multiplicar dos números de n dígitos en operaciones (en notación Big O ). Este algoritmo refutó la conjetura de Andrey Kolmogorov de 1956 de que se necesitarían operaciones para esa tarea.
Como otro ejemplo de un algoritmo de divide y vencerás que originalmente no involucraba computadoras, Donald Knuth da el método que una oficina postal usa típicamente para enrutar el correo: las cartas se clasifican en bolsas separadas para diferentes áreas geográficas, cada una de estas bolsas se clasifica en lotes para subregiones más pequeñas, y así sucesivamente hasta que se entregan. [5] Esto está relacionado con una clasificación por radix , descrita para máquinas clasificadoras de tarjetas perforadas ya en 1929. [5]
Divide y vencerás es una herramienta poderosa para resolver problemas conceptualmente difíciles: todo lo que requiere es una forma de dividir el problema en subproblemas, de resolver los casos triviales y de combinar los subproblemas para formar el problema original. De manera similar, decrementar y vencerás solo requiere reducir el problema a un único problema más pequeño, como el clásico rompecabezas de la Torre de Hanoi , que reduce mover una torre de altura a mover una torre de altura .
El paradigma de dividir y vencer suele ayudar a descubrir algoritmos eficientes. Fue la clave, por ejemplo, para el método de multiplicación rápida de Karatsuba , los algoritmos quicksort y mergesort, el algoritmo de Strassen para la multiplicación de matrices y las transformadas rápidas de Fourier.
En todos estos ejemplos, el enfoque D&C condujo a una mejora en el costo asintótico de la solución. Por ejemplo, si (a) los casos base tienen un tamaño acotado constante, el trabajo de dividir el problema y combinar las soluciones parciales es proporcional al tamaño del problema , y (b) hay un número acotado de subproblemas de tamaño ~ en cada etapa, entonces el costo del algoritmo de divide y vencerás será .
Los algoritmos de divide y vencerás están naturalmente adaptados para su ejecución en máquinas multiprocesador , especialmente sistemas de memoria compartida donde la comunicación de datos entre procesadores no necesita ser planificada de antemano porque los distintos subproblemas pueden ejecutarse en diferentes procesadores.
Los algoritmos de divide y vencerás naturalmente tienden a hacer un uso eficiente de las cachés de memoria . La razón es que una vez que un subproblema es lo suficientemente pequeño, este y todos sus subproblemas pueden, en principio, resolverse dentro de la caché , sin acceder a la memoria principal más lenta . Un algoritmo diseñado para explotar la caché de esta manera se llama ajeno a la caché , porque no contiene el tamaño de la caché como un parámetro explícito . [9] Además, los algoritmos de D&C pueden diseñarse para algoritmos importantes (por ejemplo, ordenamiento, FFT y multiplicación de matrices) para que sean algoritmos ajenos a la caché óptimos : utilizan la caché de una manera probablemente óptima, en un sentido asintótico, independientemente del tamaño de la caché. Por el contrario, el enfoque tradicional para explotar la caché es el bloqueo , como en la optimización de anidación de bucles , donde el problema se divide explícitamente en fragmentos del tamaño apropiado; esto también puede utilizar la caché de manera óptima, pero solo cuando el algoritmo está ajustado para los tamaños de caché específicos de una máquina en particular.
La misma ventaja existe con respecto a otros sistemas de almacenamiento jerárquicos, como NUMA o la memoria virtual , así como para múltiples niveles de caché: una vez que un subproblema es lo suficientemente pequeño, se puede resolver dentro de un nivel determinado de la jerarquía, sin acceder a los niveles superiores (más lentos).
En los cálculos con aritmética redondeada, por ejemplo, con números de punto flotante , un algoritmo de dividir y vencer puede producir resultados más precisos que un método iterativo superficialmente equivalente. Por ejemplo, se pueden sumar N números mediante un simple bucle que suma cada dato a una sola variable, o mediante un algoritmo de D&C llamado suma por pares que divide el conjunto de datos en dos mitades, calcula recursivamente la suma de cada mitad y luego suma las dos sumas. Si bien el segundo método realiza la misma cantidad de sumas que el primero y paga la sobrecarga de las llamadas recursivas, generalmente es más preciso. [10]
Los algoritmos de divide y vencerás se implementan naturalmente como procedimientos recursivos . En ese caso, los subproblemas parciales que conducen al que se está resolviendo actualmente se almacenan automáticamente en la pila de llamadas de procedimiento . Una función recursiva es una función que se llama a sí misma dentro de su definición.
Los algoritmos de divide y vencerás también pueden implementarse mediante un programa no recursivo que almacena los subproblemas parciales en alguna estructura de datos explícita, como una pila , una cola o una cola de prioridad . Este enfoque permite una mayor libertad en la elección del subproblema que se resolverá a continuación, una característica que es importante en algunas aplicaciones, por ejemplo, en la recursión en amplitud y en el método de ramificación y acotación para la optimización de funciones. Este enfoque también es la solución estándar en los lenguajes de programación que no admiten procedimientos recursivos.
En las implementaciones recursivas de los algoritmos D&C, se debe asegurar que haya suficiente memoria asignada para la pila de recursión; de lo contrario, la ejecución puede fallar debido a un desbordamiento de pila . Los algoritmos D&C que son eficientes en términos de tiempo a menudo tienen una profundidad de recursión relativamente pequeña. Por ejemplo, el algoritmo quicksort se puede implementar de modo que nunca requiera más que llamadas recursivas anidadas para ordenar elementos.
El desbordamiento de pila puede ser difícil de evitar cuando se utilizan procedimientos recursivos, ya que muchos compiladores suponen que la pila de recursión es un área contigua de memoria y algunos le asignan una cantidad fija de espacio. Los compiladores también pueden guardar más información en la pila de recursión de la que es estrictamente necesaria, como la dirección de retorno, los parámetros inmutables y las variables internas del procedimiento. Por lo tanto, el riesgo de desbordamiento de pila se puede reducir minimizando los parámetros y las variables internas del procedimiento recursivo o utilizando una estructura de pila explícita.
En cualquier algoritmo recursivo, existe una considerable libertad en la elección de los casos base , los pequeños subproblemas que se resuelven directamente para terminar la recursión.
La elección de los casos base más pequeños o más simples posibles es más elegante y, por lo general, conduce a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo de transformada rápida de Fourier podría detener la recursión cuando la entrada es una sola muestra, y el algoritmo de ordenamiento por lista de ordenamiento rápido podría detenerse cuando la entrada es la lista vacía; en ambos ejemplos, solo hay un caso base a considerar y no requiere procesamiento.
Por otra parte, la eficiencia a menudo mejora si la recursión se detiene en casos base relativamente grandes, y estos se resuelven de forma no recursiva, lo que da como resultado un algoritmo híbrido . Esta estrategia evita la sobrecarga de las llamadas recursivas que hacen poco o ningún trabajo y también puede permitir el uso de algoritmos no recursivos especializados que, para esos casos base, son más eficientes que la recursión explícita. Un procedimiento general para un algoritmo recursivo híbrido simple es cortocircuitar el caso base , también conocido como recursión de plena competencia . En este caso, se comprueba si el siguiente paso dará como resultado el caso base antes de la llamada de función, lo que evita una llamada de función innecesaria. Por ejemplo, en un árbol, en lugar de recurrir a un nodo secundario y luego verificar si es nulo, comprobar si es nulo antes de recurrir evita la mitad de las llamadas de función en algunos algoritmos en árboles binarios. Dado que un algoritmo D&C finalmente reduce cada instancia de problema o subproblema a una gran cantidad de instancias base, estas a menudo dominan el costo general del algoritmo, especialmente cuando la sobrecarga de división/unión es baja. Tenga en cuenta que estas consideraciones no dependen de si la recursión la implementa el compilador o una pila explícita.
Por ejemplo, muchas implementaciones de bibliotecas de quicksort cambiarán a un algoritmo de ordenamiento por inserción basado en bucles (o similar) simple una vez que el número de elementos a ordenar sea lo suficientemente pequeño. Tenga en cuenta que, si la lista vacía fuera el único caso base, ordenar una lista con entradas implicaría llamadas de quicksort máximas que no harían nada más que regresar inmediatamente. Aumentar los casos base a listas de tamaño 2 o menos eliminará la mayoría de esas llamadas que no hacen nada y, de manera más general, se suele utilizar un caso base mayor que 2 para reducir la fracción de tiempo empleado en la sobrecarga de llamadas de función o la manipulación de la pila.
Como alternativa, se pueden emplear casos base grandes que aún utilizan un algoritmo de divide y vencerás, pero implementan el algoritmo para un conjunto predeterminado de tamaños fijos donde el algoritmo se puede desenrollar completamente en código que no tiene recursión, bucles o condicionales (relacionado con la técnica de evaluación parcial ). Por ejemplo, este enfoque se utiliza en algunas implementaciones FFT eficientes, donde los casos base son implementaciones desenrolladas de algoritmos FFT de divide y vencerás para un conjunto de tamaños fijos. [11] Se pueden utilizar métodos de generación de código fuente para producir la gran cantidad de casos base separados deseables para implementar esta estrategia de manera eficiente. [11]
La versión generalizada de esta idea se conoce como "desenrollado" o "engrosamiento" de la recursión, y se han propuesto varias técnicas para automatizar el procedimiento de ampliación del caso base. [12]
En algunos problemas, la recursión ramificada puede terminar evaluando el mismo subproblema muchas veces. En tales casos, puede ser conveniente identificar y guardar las soluciones de estos subproblemas superpuestos, una técnica que se conoce comúnmente como memorización . Si se aplica hasta el límite, conduce a algoritmos de división y conquista de abajo hacia arriba, como la programación dinámica .
