Algoritmo de divide y vencerás - Divide-and-conquer algorithm

En informática , divide y vencerás es un paradigma de diseño de algoritmos . Un algoritmo divide y vencerás de forma recursiva divide un problema en dos o más subproblemas del mismo tipo o de un tipo relacionado, hasta que estos se vuelven lo suficientemente simples como para ser resueltos directamente. Las soluciones a los subproblemas se combinan luego para dar una solución al problema original.

La técnica de divide y vencerás es la base de algoritmos eficientes para muchos problemas, como ordenar (por ejemplo, clasificación rápida , clasificación por fusión ), multiplicar números grandes (por ejemplo, el algoritmo de Karatsuba ), encontrar el par de puntos más cercano , análisis sintáctico ( por ejemplo, analizadores sintácticos de arriba hacia abajo ) y calcular la transformada discreta de Fourier ( FFT ).

Diseñar algoritmos eficientes de divide y vencerás puede resultar difícil. Al igual que en la inducción matemática , a menudo es necesario generalizar el problema para que sea susceptible de una solución recursiva. La corrección de un algoritmo de divide y vencerás generalmente se demuestra por inducción matemática, y su costo computacional a menudo se determina resolviendo relaciones de recurrencia .

Divide y conquistaras

Enfoque de divide y vencerás para ordenar la lista (38, 27, 43, 3, 9, 82, 10) en orden creciente. Mitad superior: división en sublistas; mid: una lista de un elemento se ordena trivialmente; mitad inferior: componiendo sublistas ordenadas.

El paradigma de divide y vencerás se utiliza a menudo para encontrar una solución óptima a un problema. Su idea básica es descomponer un problema dado en dos o más subproblemas similares, pero más simples, para resolverlos a su vez y componer sus soluciones para resolver el problema dado. Los problemas de suficiente sencillez 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 apropiadamente para obtener la versión ordenada de la lista dada (vea la fotografía). Este enfoque se conoce como algoritmo de ordenación por combinación .

El nombre "divide y vencerás" a veces se aplica 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 raíz hallazgo ). Estos algoritmos se pueden implementar de manera más eficiente que los algoritmos generales de divide y vencerás; en particular, si usan la recursividad de cola , se pueden convertir en bucles simples . Sin embargo, bajo esta amplia definición, cada algoritmo que usa recursividad o bucles podría considerarse como un "algoritmo de divide y vencerás". Por ello, algunos autores consideran que el nombre "divide y vencerás" debe utilizarse únicamente cuando cada problema pueda generar dos o más subproblemas. En su lugar, se ha propuesto el nombre disminuir y conquistar para la clase de subproblema único.

Una aplicación importante de divide y vencerás está en la optimización, 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, con la constante dependiendo de la factor de poda (sumando la serie geométrica ); esto se conoce como podar y buscar .

Primeros ejemplos históricos

Los primeros ejemplos de estos algoritmos se reducen y superan principalmente: 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 en el que 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 utilizar una lista ordenada de elementos para facilitar la búsqueda se remonta al menos hasta Babilonia en el 200 a. C. Otro algoritmo antiguo 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 de 1805 de Gauss de lo que ahora se llama el algoritmo de transformada rápida de Fourier (FFT) de Cooley-Tukey , aunque no analizó cuantitativamente su recuento de operaciones , y las FFT sí lo hicieron. no se generalizaron hasta que fueron redescubiertos más de un siglo después.

Uno de los primeros algoritmos de D&C de dos subproblemas que se desarrolló específicamente para computadoras y se analizó adecuadamente es el algoritmo de clasificación por fusión , inventado por John von Neumann en 1945.

Otro ejemplo notable es el algoritmo inventado por Anatolii A. Karatsuba en 1960 que podrí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 requerirían operaciones para esa tarea. ${\ Displaystyle O (n ^ {\ log _ {2} 3})}$ ${\ Displaystyle \ Omega (n ^ {2})}$

Como otro ejemplo de un algoritmo de divide y vencerás que originalmente no involucró computadoras, Donald Knuth da el método que una oficina de correos 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 sí misma. en lotes para subregiones más pequeñas, y así sucesivamente hasta que se entreguen. Esto está relacionado con una clasificación de radix , descrita para las máquinas clasificadoras de tarjetas perforadas ya en 1929.

Ventajas

Resolviendo problemas difíciles

Dividir y conquistar es una herramienta poderosa para resolver problemas conceptualmente difíciles: todo lo que requiere es una forma de dividir el problema en subproblemas, resolver los casos triviales y combinar subproblemas con el problema original. Del mismo modo, disminuir y conquistar solo requiere reducir el problema a un solo problema más pequeño, como el clásico rompecabezas de la Torre de Hanoi , que reduce el movimiento de una torre de altura para mover una torre de altura . ${\ Displaystyle n}$ ${\ Displaystyle n-1}$

Eficiencia del algoritmo

El paradigma de divide y vencerás a menudo ayuda en el descubrimiento de algoritmos eficientes. Era la clave, por ejemplo, para el método de multiplicación rápida de Karatsuba, los algoritmos de ordenación rápida y ordenación por fusión, el algoritmo de Strassen para la multiplicación de matrices y las transformadas rápidas de Fourier.

En todos estos ejemplos, el enfoque de 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, el costo del algoritmo divide y vencerás será . ${\ Displaystyle n}$ ${\ Displaystyle p}$ ${\ Displaystyle n / p}$ ${\ Displaystyle O (n \ log _ {p} n)}$

Paralelismo

Los algoritmos de dividir y conquistar 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 anticipación porque se pueden ejecutar distintos subproblemas en diferentes procesadores.

Acceso a la memoria

Los algoritmos de dividir y conquistar naturalmente tienden a hacer un uso eficiente de las memorias caché . La razón es que una vez que un subproblema es lo suficientemente pequeño, él 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 denomina caché inconsciente , porque no contiene el tamaño de la caché como un parámetro explícito. Por otra parte, D & C algoritmos pueden ser diseñados para los algoritmos importantes (por ejemplo, clasificación, FFT, y la multiplicación de matrices) para ser óptimos de caché-ajeno algoritmos que utilizan la memoria 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 el caché es el bloqueo , como en la optimización del nido de bucles , donde el problema se divide explícitamente en fragmentos del tamaño apropiado; esto también puede usar el caché de manera óptima, pero solo cuando el algoritmo está ajustado para el tamaños de caché de una máquina en particular.

La misma ventaja existe con respecto a otros sistemas de almacenamiento jerárquico, como NUMA o 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 dado de la jerarquía, sin acceder a los niveles más altos (más lentos).

Control de redondeo

En cálculos con aritmética redondeada, por ejemplo, con números de punto 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 agrega 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 agrega las dos sumas. Si bien el segundo método realiza la misma cantidad de adiciones que el primero y paga la sobrecarga de las llamadas recursivas, generalmente es más preciso.

Problemas de implementación

Recursividad

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 al procedimiento . Una función recursiva es una función que se llama a sí misma dentro de su definición.

Pila explícita

Los algoritmos de dividir y conquistar también se pueden implementar 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 más libertad en la elección del subproblema que se va a resolver a continuación, una característica que es importante en algunas aplicaciones, por ejemplo, en la recursividad primero en amplitud y el método de ramificación y vinculación para la optimización de funciones. Este enfoque también es la solución estándar en lenguajes de programación que no brindan soporte para procedimientos recursivos.

Tamaño de la pila

En las implementaciones recursivas de los algoritmos de D&C, uno debe asegurarse de que haya suficiente memoria asignada para la pila de recursividad; de lo contrario, la ejecución puede fallar debido a un desbordamiento de la pila . Los algoritmos de D&C que son eficientes en el tiempo a menudo tienen una profundidad de recursividad relativamente pequeña. Por ejemplo, el algoritmo de ordenación rápida se puede implementar para que nunca requiera más que llamadas recursivas anidadas para ordenar elementos. ${\ Displaystyle \ log _ {2} n}$ ${\ Displaystyle n}$

El desbordamiento de la pila puede ser difícil de evitar cuando se utilizan procedimientos recursivos, ya que muchos compiladores asumen que la pila recursiva 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 recursividad de la estrictamente necesaria, como la dirección de retorno, los parámetros que no cambian y las variables internas del procedimiento. Por lo tanto, el riesgo de desbordamiento de la pila se puede reducir minimizando los parámetros y las variables internas del procedimiento recursivo o utilizando una estructura de pila explícita.

Elegir los casos base

En cualquier algoritmo recursivo, existe una libertad considerable en la elección de los casos base , los pequeños subproblemas que se resuelven directamente para terminar la recursividad.

Elegir los casos base más pequeños o simples posibles es más elegante y generalmente conduce a programas más simples, porque hay menos casos a considerar y son más fáciles de resolver. Por ejemplo, un algoritmo FFT podría detener la recursividad cuando la entrada es una sola muestra, y el algoritmo de clasificación de listas de clasificación rápida 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 otro lado, la eficiencia a menudo mejora si la recursividad 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 llamadas recursivas que hacen poco o ningún trabajo y también puede permitir el uso de algoritmos especializados no recursivos que, para esos casos base, son más eficientes que la recursividad 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, antes de la llamada a la función se comprueba si el siguiente paso dará como resultado el caso base, evitando una llamada de función innecesaria. Por ejemplo, en un árbol, en lugar de recurrir a un nodo hijo y luego verificar si es nulo, verificar nulo antes de recurrir; evita la mitad de las llamadas a funciones en algunos algoritmos en árboles binarios. Dado que un algoritmo de D&C eventualmente reduce cada problema o instancia de 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 recursividad la implementa el compilador o una pila explícita.

Así, por ejemplo, muchas implementaciones de biblioteca de clasificación rápida cambiarán a un algoritmo de clasificación de inserción basado en bucle simple (o similar) una vez que el número de elementos a clasificar 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 clasificación rápida 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 de no hacer nada y, de manera más general, se usa un caso base mayor que 2 para reducir la fracción de tiempo invertida en la sobrecarga de llamadas de función o la manipulación de la pila. ${\ Displaystyle n}$ ${\ Displaystyle n}$

Alternativamente, se pueden emplear casos base grandes que todavía usan 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 un código que no tiene recursividad, bucles o condicionales (relacionados con la técnica de evaluación parcial ). Por ejemplo, este enfoque se utiliza en algunas implementaciones de FFT eficientes, donde los casos base son implementaciones desenrolladas de algoritmos FFT de divide y vencerás para un conjunto de tamaños fijos. 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.

La versión generalizada de esta idea se conoce como "desenrollado" o "engrosamiento" de recursividad, y se han propuesto varias técnicas para automatizar el procedimiento de ampliación del caso base.

Compartir subproblemas repetidos

Para algunos problemas, la recursividad ramificada puede terminar evaluando el mismo subproblema muchas veces. En tales casos, puede valer la pena identificar y guardar las soluciones a estos subproblemas superpuestos, una técnica que se conoce comúnmente como memorización . Seguido hasta el límite, conduce a algoritmos ascendentes de divide y vencerás, como la programación dinámica y el análisis de gráficos .

Languages

In other projects