Divide y vencerás (informática)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de enero de 2021; las comprobaciones requieren 22 ediciones .

Divide y vencerás en informática es un  paradigma de desarrollo de algoritmos que consiste en dividir recursivamente el problema a resolver en dos o más subtareas del mismo tipo, pero de menor tamaño, y combinar sus soluciones para obtener una respuesta al problema original; Las particiones se realizan hasta que todas las subtareas sean elementales.

Comprender y diseñar algoritmos de divide y vencerás es una habilidad compleja que requiere una buena comprensión de la naturaleza del problema subyacente a resolver. Al igual que con la demostración de un teorema por inducción matemática , a menudo es necesario reemplazar el problema original con un problema más general o complejo para inicializar la recursión, y no existe un método sistemático para encontrar la generalización correcta. Tales complejidades del método Divide and Conquer se ven cuando se optimiza el cálculo del número de Fibonacci con doble recursividad eficiente.

La corrección del algoritmo que sigue el paradigma "Divide y vencerás" se prueba con mayor frecuencia mediante el método de inducción matemática , y el tiempo de ejecución se determina resolviendo directamente la ecuación recurrente correspondiente o aplicando el teorema principal de la relación de recurrencia .

Divide y vencerás

El paradigma divide y vencerás se utiliza a menudo para encontrar la solución óptima a un problema en particular. Su idea principal es descomponer un problema dado en dos o más subproblemas similares pero más simples, resolverlos uno por uno y componer sus soluciones. Por ejemplo, para ordenar una lista dada de n números naturales, debe dividirla en dos listas de aproximadamente n /2 números cada una, ordenar cada uno de ellos por turno y organizar ambos resultados en consecuencia para obtener una versión ordenada de esta lista ( ver figura). 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 una entrada en una lista ordenada (o su caso especial, el algoritmo de bisección para encontrar raíces). [1] Estos algoritmos se pueden implementar de manera más eficiente que los algoritmos generales Divide y vencerás; en particular, si usan recursividad de cola , se pueden convertir en bucles simples . Sin embargo, bajo esta definición amplia, cada algoritmo que usa recursión o bucles puede ser considerado un "algoritmo divide y vencerás". Por lo tanto, algunos autores creen que el nombre "Divide y vencerás" solo debe usarse cuando cada tarea puede generar dos o más subtareas. [2] En cambio, se propuso el nombre reducir y conquistar para la clase de problemas únicos. [3]

Ejemplos

Los primeros ejemplos de tales algoritmos son principalmente "Reducir y conquistar": el problema original se divide secuencialmente en subproblemas separados y, de hecho, se puede resolver de forma iterativa.

La búsqueda binaria, el algoritmo "Reducir y conquistar" en el que los subproblemas tienen aproximadamente la mitad del tamaño original, tiene una larga historia. Aunque una descripción clara del algoritmo en las computadoras apareció ya 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 a Babilonia en el año 200 a. [4] Otro antiguo algoritmo de reducción y conquista es el algoritmo de Euclides 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 se remonta a varios siglos antes de Cristo.

Un ejemplo temprano de un algoritmo Divide y vencerás con múltiples subproblemas es la descripción gaussiana (1805) de lo que ahora se llama la transformada rápida de Fourier de Cooley-Tukey [5] .

Uno de los primeros algoritmos Divide y vencerás de dos subproblemas que se diseñó específicamente para computadoras y se analizó adecuadamente es el algoritmo de clasificación por combinación inventado   por John von Neumann en 1945. [6]

Un ejemplo típico es el algoritmo de clasificación por fusión . Para ordenar una matriz de números en orden ascendente, se divide en dos partes iguales, cada una se ordena y luego las partes ordenadas se fusionan en una sola. Este procedimiento se aplica a cada una de las partes siempre que la parte del arreglo a ordenar contenga al menos dos elementos (para que se pueda dividir en dos partes). El tiempo de ejecución de este algoritmo son las operaciones, mientras que los algoritmos más simples toman tiempo, donde  es el tamaño de la matriz original.

Otro ejemplo notable es el algoritmo inventado por Anatoly Aleksandrovich Karatsuba en 1960 [7] para multiplicar dos números de n dígitos por  el número de operación ( notación grande O ). Este algoritmo refutó la hipótesis de 1956 de Andrey Kolmogorov de que esta tarea requeriría operaciones.

Como otro ejemplo de un algoritmo Divide and Conquer que originalmente no usaba computadoras. Donald Knuth ofrece un método comúnmente utilizado por la oficina de correos para enrutar el correo: las cartas se clasifican en paquetes separados destinados a diferentes áreas geográficas, cada uno de estos paquetes se clasifica en lotes para subregiones más pequeñas, y así sucesivamente hasta que se entregan. [4] Esto está relacionado con la clasificación radix , descrita para las máquinas clasificadoras de tarjetas perforadas desde 1929. [cuatro]

Beneficios

Resolución de problemas complejos

Divide and Conquer es una poderosa herramienta para resolver problemas conceptualmente complejos: todo lo que se requiere es encontrar un caso para dividir el problema en subproblemas, resolver casos triviales y combinar los subproblemas en el problema original. Asimismo, Reduce and Conquer solo requiere reducir el problema a un problema más pequeño, como la clásica Torre de Hanoi , que reduce la solución de mover una torre de altura n a mover una torre de altura n − 1.

Eficiencia del algoritmo

El paradigma Divide y vencerás a menudo ayuda a descubrir algoritmos eficientes. Esta ha sido la clave para, por ejemplo, el método de multiplicación rápida de Karatsuba, los algoritmos de clasificación rápida y clasificació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 Divide and Conquer resultó en una mejora en el costo asintótico de la solución en la solución misma. Por ejemplo, si (a) el caso base tiene un tamaño acotado por una constante, entonces el trabajo de dividir el problema y combinar soluciones parciales es proporcional al tamaño del problema n, y (b) hay un número limitado p de subproblemas de tamaño ~n/p en cada etapa, entonces la eficiencia del algoritmo es " Divide y vencerás será O( n  log p n ).

Concurrencia

Los algoritmos Divide and Conquer están naturalmente adaptados para ejecutarse en máquinas multiprocesador, especialmente en sistemas de memoria compartida , en los que las transferencias de datos entre procesadores no necesitan programarse con anticipación, ya que las subtareas individuales pueden ejecutarse en diferentes procesadores.

Acceso a la memoria

Los algoritmos de divide y vencerás naturalmente tienden a usar la memoria caché de manera eficiente . La razón es que una vez que una subtarea es lo suficientemente pequeña, esta y todas sus subtareas pueden, en principio, resolverse en el caché sin acceder a la memoria principal más lenta. El algoritmo para utilizar la memoria caché de esta forma se denomina "olvidar la memoria caché" porque no incluye el tamaño de la memoria caché como parámetro explícito. [8] Además, los algoritmos Divide and Conquer se pueden diseñar para que algoritmos importantes (p. ej., clasificación, FFT y multiplicación de matrices) se conviertan en algoritmos óptimos que ignoran la memoria caché: utilizan la memoria caché de una manera probablemente óptima, en un sentido asintótico, independientemente de tamaño de caché. Por el contrario, el enfoque tradicional del uso de la memoria caché es el bloqueo, como en la optimización de bucle anidado , donde la tarea se divide explícitamente en fragmentos de tamaño apropiado; esto también puede usar la memoria caché de manera óptima, pero solo cuando el algoritmo está ajustado para un tamaño de memoria caché específico. de una máquina en particular.

La misma ventaja existe para otros sistemas de almacenamiento jerárquico como NUMA o memoria virtual , y para múltiples niveles de caché: una vez que un subproblema es lo suficientemente pequeño, se puede resolver dentro de ese nivel de la jerarquía, sin acceso a niveles más altos (más lentos). .

Problemas de aplicación

Recursividad

Los algoritmos Divide and Conquer se aplican naturalmente en forma de métodos recursivos . En este caso, las subtareas privadas que conducen a la que se está resolviendo actualmente se almacenan automáticamente en la pila de llamadas del procedimiento . Una función recursiva es una función numérica de un argumento numérico que se contiene a sí mismo en su notación.

Pila explícita

Los algoritmos de divide y vencerás también se pueden aplicar mediante un programa no recursivo que almacena subproblemas privados en alguna estructura de datos explícita, como una pila , una cola o una cola de prioridad.Este enfoque permite más libertad para elegir qué subproblema debe resolverse a continuación. Una característica que es importante en algunas aplicaciones, por ejemplo, en el método de bifurcación y enlace para optimizar funciones. Este enfoque también es estándar en lenguajes de programación que no brindan soporte para procedimientos recursivos.

Tamaño de pila

En las implementaciones recursivas de los algoritmos Divide and Conquer, uno debe asegurarse de que se asigne suficiente memoria para la pila de recursión; de lo contrario, la ejecución puede fallar debido al desbordamiento de la pila . Los algoritmos de divide y vencerás que son eficientes en el tiempo a menudo tienen profundidades de recursión relativamente bajas. Por ejemplo, un algoritmo de clasificación rápida se puede implementar de tal manera que nunca requiera más de log2 n llamadas recursivas anidadas para clasificar n elementos.

Los desbordamientos de pila pueden ser difíciles de evitar cuando se usan rutinas recursivas porque muchos compiladores asumen que la pila recursiva es contigua en la memoria y algunos le asignan una cantidad fija de espacio. Los compiladores también pueden almacenar más información en la pila de recursión de lo estrictamente necesario, como la dirección de retorno, los parámetros inmutables y las variables internas de los procedimientos. Por lo tanto, el riesgo de desbordamiento de pila se puede reducir minimizando los parámetros y las variables internas del procedimiento recursivo, o usando una estructura de pila explícita.

Elección de opciones básicas

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

Elegir los casos base más pequeños o simples posibles es más elegante y, por lo general, da como resultado programas más simples porque hay menos casos que considerar y más fáciles de resolver. Por ejemplo, la FFT puede detener la recursividad cuando la entrada es una sola muestra, y el algoritmo de ordenación rápida para una lista puede detenerse cuando la entrada es una lista vacía; en ambos ejemplos solo hay un caso base a considerar y no es necesario procesarlo.

Por otro lado, la eficiencia suele mejorar 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 superposición de llamadas recursivas que hacen poco o ningún trabajo y también puede permitir el uso de algoritmos no recursivos especializados que, para estos casos básicos, son más eficientes que la recursividad explícita. El 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 llamar a la función, se comprueba si el siguiente paso conducirá al registro base, evitando una llamada de función innecesaria. Debido a que el algoritmo Divide y vencerás eventualmente reduce cada instancia de un problema o subproblema a una gran cantidad de instancias base, a menudo dominan la eficiencia general del algoritmo, especialmente cuando la sobrecarga de dividir/unir es baja. Además, estas consideraciones no dependen de si el compilador o una pila explícita implementan la recursividad.

Así, por ejemplo, muchas aplicaciones de biblioteca de ordenación rápida se convertirán en un simple algoritmo de ordenación por inserción basado en bucles (o similar) tan pronto como el número de elementos a ordenar sea lo suficientemente pequeño. Además, si una lista vacía fuera el único caso base, ordenar una lista con n entradas daría como resultado un número máximo de n llamadas de clasificación rápida que no harían nada más que regresar de inmediato. Aumentar los casos base a listas de tamaño 2 o menos eliminará la mayoría de estas llamadas de "no hacer nada" y, en general, el caso base mayor que 2 se usa típicamente para reducir la proporción de tiempo dedicado a la limpieza o manipulación de pilas.

Alternativamente, se pueden usar casos base grandes, que todavía usan el algoritmo Divide y vencerás pero implementan el algoritmo para un conjunto predefinido de tamaños fijos, donde el algoritmo se puede expandir completamente en código que no tiene recursividad, bucles o convenciones (asociados). con método de evaluación parcial ). Por ejemplo, este enfoque se usa en algunas aplicaciones FFT eficientes, donde los casos base son implementaciones extendidas de algoritmos FFT Divide and Conquer para un conjunto de tamaños fijos. [9] Las técnicas de generación de código fuente se pueden utilizar para generar la gran cantidad de casos base distintos deseados para implementar de manera efectiva esta estrategia.

Una versión generalizada de esta idea se conoce como recursividad de "expandir" o "crecer", y se han propuesto varios métodos para automatizar el procedimiento de expansión del caso base. [9]

Compartir subtareas recurrentes

Para algunas tareas, la recursividad de bifurcación puede dar como resultado múltiples evaluaciones de la misma subtarea. En tales casos, puede valer la pena identificar y almacenar soluciones a estos subproblemas superpuestos, una técnica comúnmente conocida como memorización . Siguiendo hasta el límite, esto conduce a algoritmos ascendentes de divide y vencerás, como la programación dinámica y el análisis de diagramas .

Véase también

Notas

  1. ↑ Thomas H.Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introducción a los Algoritmos  (neopr.) . - MIT Press , 2009. - ISBN 978-0-262-53305-8 .
  2. ↑ Brassard, G. y Bratley, P. Fundamental of Algorithmics, Prentice-Hall, 1996.
  3. ↑ Anany V. Levitin, Introducción al diseño y análisis de algoritmos (Addison Wesley, 2002).
  4. ↑ 1 2 3 Donald E. Knuth, El arte de la programación informática: Volumen 3, Clasificación y búsqueda , segunda edición (Addison-Wesley, 1998).
  5. ↑ Heideman, MT, DH Johnson y CS Burrus, " Gauss y la historia de la transformada rápida de Fourier Archivado el 31 de julio de 2020 en Wayback Machine ", IEEE ASSP Magazine, 1, (4), 14–21 (1984).
  6. ↑ Donald Knuth . El arte de la programación informática : Volumen 3 Clasificación y búsqueda  . - 1998. - Pág. 159. - ISBN 0-201-89685-0 .
  7. ↑ Karatsuba, Anatolii A .; Yuri P. Ofman . Multiplicación de números de valores múltiples en autómatas  (neopr.)  // Informes de la Academia de Ciencias . - 1962. - T. 146 . - S. 293-294 . Traducido en Multiplicación de números de varios dígitos en autómatas   // Física soviética Doklady : diario. - 1963. - vol. 7 . - Pág. 595-596 .
  8. ↑ M. Frigo; CE Leiserson; H. Prokop. Algoritmos ajenos a la memoria caché  (neopr.)  // Proc. 40º sim. sobre los Fundamentos de la Informática. — 1999.
  9. ↑ 1 2 Frigo, M.; Johnson, SG  El diseño e implementación de FFTW3  // Actas del IEEE : diario. - 2005. - febrero ( vol. 93 , no. 2 ). - pág. 216-231 . -doi : 10.1109/ JPROC.2004.840301 .

Literatura

Enlaces