Algoritmo de divide y vencerás

Divide y vencerás es una herramienta poderosa para resolver problemas conceptualmente difíciles: solo requiere una forma de dividir el problema en subproblemas, resolver los casos triviales y combinar los subproblemas con el problema original. De manera similar, disminuir 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 el movimiento de una torre de altura${\displaystyle n}$mover una torre de altura${\displaystyle n-1}$.

El paradigma de divide y vencerás suele ser útil para descubrir algoritmos eficientes. Fue 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 constante y acotado, el trabajo de dividir el problema y combinar las soluciones parciales es proporcional al tamaño del problema.${\displaystyle n}$y (b) hay un número acotado${\displaystyle p}$de subproblemas de tamaño ~${\displaystyle {\frac {n}{p}}}$En cada etapa, el costo del algoritmo de divide y vencerás será${\displaystyle O(n\log _{p}n)}$.

Para otros tipos de enfoques de divide y vencerás, los tiempos de ejecución también se pueden generalizar. Por ejemplo, cuando a) el trabajo de dividir el problema y combinar las soluciones parciales lleva${\displaystyle cn}$tiempo, donde${\displaystyle n}$es el tamaño de entrada y${\displaystyle c}$es alguna constante; b) cuando${\displaystyle n<2}$, el algoritmo tarda un tiempo limitado superiormente por${\displaystyle c}$y c) hay${\displaystyle q}$subproblemas donde cada subproblema tiene un tamaño ~${\displaystyle {\frac {n}{2}}}$Los tiempos de ejecución son los siguientes:

• si el número de subproblemas${\displaystyle q>2}$, entonces el tiempo de ejecución del algoritmo divide y vencerás está limitado por${\displaystyle O(n^{\log _{2}q})}$.
• Si el número de subproblemas es exactamente uno, entonces el tiempo de ejecución del algoritmo divide y vencerás está acotado por${\displaystyle O(n)}$. ^{[ 10 ]}

Si, en cambio, el trabajo de dividir el problema y combinar las soluciones parciales lleva${\displaystyle cn^{2}}$tiempo, y hay 2 subproblemas donde cada uno tiene tamaño${\displaystyle {\frac {n}{2}}}$, entonces el tiempo de ejecución del algoritmo divide y vencerás está limitado por${\displaystyle O(n^{2})}$. ^{[ 10 ]}

Los algoritmos de divide y vencerás se adaptan naturalmente para su ejecución en máquinas multiprocesador , especialmente en sistemas de memoria compartida donde la comunicación de datos entre procesadores no necesita planificarse con antelación, ya que los distintos subproblemas pueden ejecutarse en diferentes procesadores.

Los algoritmos de divide y vencerás tienden naturalmente 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 , que es más lenta . Un algoritmo diseñado para explotar la caché de esta manera se denomina ajeno a la caché , porque no contiene el tamaño de la caché como un parámetro explícito . ^{[ 11 ]} Además, los algoritmos de D&C pueden diseñarse para algoritmos importantes (por ejemplo, ordenación, FFT y multiplicación de matrices) para que sean algoritmos óptimos ajenos a la caché; utilizan la caché de una manera probablemente óptima, en un sentido asintótico, independientemente del tamaño de la caché. En contraste, el enfoque tradicional para explotar la caché es bloqueante , como en la optimización de anidamiento de bucles , donde el problema se divide explícitamente en fragmentos del tamaño apropiado; esto también puede usar 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 se aplica a otros sistemas de almacenamiento jerárquico, como NUMA o la memoria virtual , así como a 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 cálculos con aritmética redondeada, por ejemplo, con números de coma flotante , un algoritmo de divide y vencerás puede producir resultados más precisos que un método iterativo superficialmente equivalente. Por ejemplo, se pueden sumar N números mediante un bucle simple que suma cada dato a una sola variable, o mediante un algoritmo de divide y vencerás 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 conlleva la sobrecarga de las llamadas recursivas, suele ser más preciso. ^{[ 12 ]}

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 se almacenan automáticamente en la pila de llamadas del 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 una estructura de datos explícita, como una pila , una cola o una cola de prioridad . Este enfoque permite mayor libertad en la elección del subproblema a resolver, una característica importante en algunas aplicaciones, como la recursión en amplitud y el método de ramificación y acotación para la optimización de funciones. Este enfoque es también la solución estándar en lenguajes de programación que no admiten procedimientos recursivos.

En las implementaciones recursivas de algoritmos D&C, es necesario asegurarse de que se asigne suficiente memoria para la pila de recursión; de lo contrario, la ejecución podría fallar debido a un desbordamiento de pila . Los algoritmos D&C que son eficientes en tiempo suelen tener una profundidad de recursión relativamente pequeña. Por ejemplo, el algoritmo quicksort se puede implementar de manera que nunca requiera más de${\displaystyle \log _{2}n}$llamadas recursivas anidadas para ordenar${\displaystyle n}$elementos.

El desbordamiento de pila puede ser difícil de prevenir al usar procedimientos recursivos, ya que muchos compiladores tratan la pila de recursión como un bloque de memoria contiguo y algunos le reservan una cantidad fija de espacio. Además, los compiladores pueden almacenar más información en la pila de recursión de la estrictamente necesaria, incluyendo la dirección de retorno, los parámetros sin modificar y las variables locales del procedimiento. Por lo tanto, la probabilidad de desbordamiento de pila puede reducirse limitando el número de parámetros y variables locales en el procedimiento recursivo, o reemplazando la recursión con una estructura de datos 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 finalizar la recursión.

Elegir los casos base más pequeños o sencillos posibles es más elegante y suele dar lugar a programas más simples, ya que hay menos casos que 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 ordenación rápida de listas podría detenerse cuando la entrada es una lista vacía; en ambos ejemplos, solo hay un caso base que considerar y no requiere ningún procesamiento.

Por otro lado, la eficiencia suele mejorar 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 realizan 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 el cortocircuito del caso base , también conocido como recursión de longitud de brazo . En este caso, se comprueba si el siguiente paso dará como resultado el caso base antes de la llamada a la función, evitando una llamada innecesaria. Por ejemplo, en un árbol, en lugar de recurrir a un nodo hijo y luego comprobar si es nulo, comprobar la nulidad antes de recurrir evita la mitad de las llamadas a funciones en algunos algoritmos sobre árboles binarios. Dado que un algoritmo D&C finalmente reduce cada instancia de problema o subproblema a un gran número de instancias base, estas suelen dominar el coste total del algoritmo, especialmente cuando la sobrecarga de división/unión es baja. Cabe señalar que estas consideraciones no dependen de si la recursión se implementa mediante el compilador o mediante una pila explícita.

Así, por ejemplo, muchas implementaciones de biblioteca de quicksort cambiarán a un algoritmo de ordenación por inserción simple basado en bucles (o similar) una vez que el número de elementos a ordenar sea suficientemente pequeño. Tenga en cuenta que, si la lista vacía fuera el único caso base, ordenar una lista con${\displaystyle n}$Las entradas implicarían como máximo${\displaystyle n}$Llamadas a quicksort que no harían nada más que devolver un valor 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, en general, se suele utilizar un caso base mayor que 2 para reducir la fracción de tiempo dedicado a la sobrecarga de llamadas a funciones o a la manipulación de la pila.

Alternativamente, se pueden emplear casos base grandes que aún utilizan un algoritmo de divide y vencerás, pero implementando el algoritmo para un conjunto predeterminado de tamaños fijos donde el algoritmo se puede desplegar completamente en código sin recursión, bucles ni condicionales (relacionado con la técnica de evaluación parcial ). Por ejemplo, este enfoque se utiliza en algunas implementaciones eficientes de FFT, donde los casos base son implementaciones desplegadas de algoritmos FFT de divide y vencerás para un conjunto de tamaños fijos. ^{[ 13 ]} Se pueden utilizar métodos de generación de código fuente para producir la gran cantidad de casos base separados que se desean para implementar esta estrategia de manera eficiente. ^{[ 13 ]}

La versión generalizada de esta idea se conoce como "desenrollamiento" o "engrosamiento" de la recursión, y se han propuesto varias técnicas para automatizar el procedimiento de ampliación del caso base. ^{[ 14 ]}

En algunos problemas, la recursión ramificada puede terminar evaluando el mismo subproblema varias veces. En tales casos, puede ser útil identificar y guardar las soluciones de estos subproblemas superpuestos, una técnica conocida como memorización . Llevada al extremo, esta técnica da lugar a algoritmos de divide y vencerás de abajo hacia arriba , como la programación dinámica .