Algoritmo divide y vencerás

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

La técnica divide y vencerás es la base de algoritmos eficientes para muchos problemas, como la clasificación (p. ej., ordenación rápida, ordenación por combinación), la multiplicación de números grandes (p. ej., el algoritmo de Karatsuba), la búsqueda del par de puntos más cercano, análisis sintáctico (por ejemplo, analizadores de arriba hacia abajo) y cálculo de la transformada discreta de Fourier (FFT).

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 corrección de un algoritmo divide y vencerás generalmente se prueba mediante inducción matemática, y su costo computacional a menudo se determina resolviendo relaciones de recurrencia.

Divide y vencerás

Divide-and-conquer approach to sort the list (38, 27, 43, 3, 9, 82, 10) in increasing order. Medio superior: dividirse en sublistas; mitad: a one-element list is trivially classified; mitad inferior: componendo sublistas clasificadas.

El paradigma 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 alrededor de n/2 números cada una, ordene cada uno de ellos por turno e intercale ambos resultados apropiadamente para obtener la versión ordenada de la lista dada (ver la imagen). Este enfoque se conoce como el algoritmo de clasificación por fusió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 encontrar raíces). Estos algoritmos se pueden implementar de manera más eficiente que los algoritmos generales de divide y vencerás; en particular, si usan recursividad de cola, pueden convertirse en bucles simples. Sin embargo, según esta definición amplia, todo algoritmo que utilice recursividad o bucles podría considerarse como un "algoritmo divide y vencerás". Por ello, algunos autores consideran que el nombre "divide y vencerás" debe usarse solo cuando cada problema puede generar dos o más subproblemas. En su lugar, se ha propuesto el nombre disminuir y conquistar para la clase de un solo subproblema.

Una aplicación importante de divide y vencerás es la optimización, donde si el espacio de búsqueda se reduce ("podará") por un factor constante en cada paso, el algoritmo general tiene la misma complejidad asintótica que la poda. paso, con la constante en función del factor de poda (sumando la serie geométrica); esto se conoce como podar y buscar.

Ejemplos históricos tempranos

Los primeros ejemplos de estos algoritmos se reducen y conquistan principalmente: el problema original se divide sucesivamente en subproblemas únicos y, de hecho, se puede resolver iterativamente.

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 las 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. Otro antiguo algoritmo de disminución y conquista es el algoritmo euclidiano para calcular el máximo común divisor de dos números al reducir 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 divide y vencerás con múltiples subproblemas es la descripción de Gauss de 1805 de lo que ahora se llama el algoritmo de transformada rápida de Fourier (FFT) de Cooley-Tukey, aunque no analizó su recuento de operaciones. cuantitativamente, y las FFT no se generalizaron hasta que fueron redescubiertas más de un siglo después.

Un algoritmo temprano de D&C de dos subproblemas que se desarrolló específicamente para computadoras y se analizó adecuadamente es el algoritmo de clasificación por combinació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- números de dígitos en O()nlog2⁡ ⁡ 3){displaystyle O(n^{log _{2}3}} operaciones (en Big O notation). Este algoritmo refutó la conjetura de 1956 de Andrey Kolmogorov que Ω Ω ()n2){displaystyle Omega (n^{2})} se necesitarían operaciones para esa tarea.

Como otro ejemplo de un algoritmo divide y vencerás que originalmente no involucraba computadoras, Donald Knuth ofrece el método que una oficina de correos suele usar 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. Esto está relacionado con una clasificación radix, descrita para las máquinas clasificadoras de tarjetas perforadas ya en 1929.

Ventajas

Resolver problemas difíciles

Divide y conquista es una poderosa herramienta para resolver problemas conceptualmente difíciles: todo lo que requiere es una manera de romper el problema en subproblemas, de resolver los casos triviales, y de combinar subproblemas al problema original. Del mismo modo, disminuir y conquistar sólo requiere reducir el problema a un solo problema más pequeño, como la Torre clásica del rompecabezas Hanoi, que reduce el movimiento de una torre de altura n{displaystyle n} para mover una torre de altura n− − 1{displaystyle n-1}.

Eficiencia del algoritmo

El paradigma divide y vencerás a menudo ayuda en el descubrimiento de algoritmos eficientes. Fue 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 combinada, el algoritmo de Strassen para la multiplicación de matrices y las transformadas rápidas de Fourier.

En todos estos ejemplos, el enfoque del CD llevó a una mejora del costo asintomático de la solución. Por ejemplo, si (a) los casos de base tienen un tamaño constante, el trabajo de dividir el problema y combinar las soluciones parciales es proporcional al tamaño del problema n{displaystyle n}, y b) hay un número consolidado p{displaystyle p} de subproblemas de tamaño ~ n/p{displaystyle No. en cada etapa, entonces el costo del algoritmo de división y conquista será O()nlogp⁡ ⁡ n){displaystyle O(nlog _{p}n)}.

Paralelismo

Los algoritmos de divide y vencerás están naturalmente adaptados para la ejecución en máquinas con múltiples procesadores, especialmente en sistemas de memoria compartida donde la comunicación de datos entre procesadores no necesita planificarse con anticipación porque distintos subproblemas pueden ejecutarse en diferentes procesadores

Acceso a memoria

Los algoritmos de divide y vencerás 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 memoria caché, sin acceder a la memoria principal más lenta. Un algoritmo diseñado para explotar el caché de esta manera se llama cache-oblivious, porque no contiene el tamaño del caché como un parámetro explícito. Además, los algoritmos de D&C se pueden diseñar para algoritmos importantes (p. ej., clasificación, FFT y multiplicación de matrices) para que sean óptimos algoritmos ajenos a la memoria caché: utilizan la memoria caché de una manera probablemente óptima, de una manera sentido asintótico, independientemente del tamaño del caché. Por el contrario, el enfoque tradicional para explotar la memoria caché es bloquear, 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 memoria 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.

Existe la misma ventaja 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 determinado del jerarquía, sin acceder a los niveles superiores (más lentos).

Control de redondeo

En cálculos con aritmética redondeada, p. con números de punto flotante, un algoritmo 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 ya sea mediante un bucle simple que suma cada dato a una sola variable, o mediante un algoritmo D&C denominado sumatoria por pares que divide el conjunto de datos en dos mitades, calcula recursivamente la suma de cada mitad, y luego suma las dos sumas. Mientras que el segundo método realiza la misma cantidad de adiciones que el primero y paga la sobrecarga de las llamadas recursivas, por lo general es más preciso.

Problemas de implementación

Recursión

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 divide y vencerás 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, p. en la recursividad primero en amplitud y el método branch-and-bound 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 implementaciones recursivas de algoritmos de D plagaC, se debe asegurarse de que haya suficiente memoria asignada para la pila de recursión, de lo contrario, la ejecución puede fallar debido a la desbordamiento de la pila. Los algoritmos D C que son eficientes en el tiempo a menudo tienen una profundidad de recursión relativamente pequeña. Por ejemplo, el algoritmo de la gama rápida se puede implementar para que nunca requiera más que log2⁡ ⁡ n{displaystyle log _{2}n} llamadas recursivas anidas para ordenar n{displaystyle n} artículos.

Puede ser difícil evitar el desbordamiento de la pila cuando se usan procedimientos recursivos, ya que muchos compiladores asumen que la pila recursiva es un área contigua de la 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 lo estrictamente necesario, 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 puede reducirse minimizando los parámetros y las variables internas del procedimiento recursivo o utilizando una estructura de pila explícita.

Elección de 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 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 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 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 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, si el siguiente paso dará como resultado el caso base se verifica antes de la llamada de función, evitando 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, verificar nulo antes de recurrir; evita la mitad de las llamadas a funciones 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 suelen dominar 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 el compilador o una pila explícita implementan la recursividad.

Así, por ejemplo, muchas implementaciones de biblioteca de quicksort cambiarán a un simple algoritmo de inserción basado en el bucle (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, clasificando una lista con n{displaystyle n} las entradas entrañarían un máximo n{displaystyle n} llamadas rápidas que no harían nada más que volver inmediatamente. Aumentar los casos de base a las listas de tamaño 2 o menos eliminará la mayoría de esas llamadas de no hacer nada, y más generalmente un caso base más grande que 2 se utiliza normalmente para reducir la fracción de tiempo gastado en la sobrecarga de funciones o la manipulación de pilas.

Alternativamente, se pueden emplear casos base grandes que todavía usan un algoritmo divide y vencerás, pero implementas el algoritmo para un conjunto predeterminado de tamaños fijos donde el algoritmo se puede desarrollar completamente en un código que no tiene recursividad, bucles ni condicionales. (relacionado con la técnica de evaluación parcial). Por ejemplo, este enfoque se usa en algunas implementaciones de FFT eficientes, donde los casos base son implementaciones desenrolladas de algoritmos de FFT de divide y vencerás para un conjunto de tamaños fijos. Los métodos de generación de código fuente se pueden usar 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 recursividad "desenrollado" o "engrosamiento", y se han propuesto varias técnicas para automatizar el procedimiento de ampliación del caso base.

Programación dinámica para subproblemas superpuestos

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 comúnmente se conoce como memorización. Si se sigue hasta el límite, conduce a algoritmos ascendentes de divide y vencerás, como la programación dinámica.