De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

Un algoritmo híbrido es un algoritmo que combina dos o más algoritmos que resuelven el mismo problema, ya sea eligiendo uno (según los datos) o cambiando entre ellos en el transcurso del algoritmo. Esto generalmente se hace para combinar las características deseadas de cada uno, de modo que el algoritmo general sea mejor que los componentes individuales.

"Algoritmo híbrido" no se refiere simplemente a combinar múltiples algoritmos para resolver un problema diferente - muchos algoritmos pueden considerarse como combinaciones de piezas más simples - sino solo a combinar algoritmos que resuelven el mismo problema, pero difieren en otras características, notablemente en desempeño.

Ejemplos [ editar ]

En ciencias de la computación , los algoritmos híbridos son muy comunes en implementaciones optimizadas de algoritmos recursivos en el mundo real , particularmente implementaciones de algoritmos dividir y conquistar o disminuir y conquistar , donde el tamaño de los datos disminuye a medida que uno avanza en la recursividad. En este caso, se usa un algoritmo para el enfoque general (en datos grandes), pero en el fondo de la recursividad, cambia a un algoritmo diferente, que es más eficiente en datos pequeños. Un ejemplo común es el de los algoritmos de clasificación., donde la ordenación por inserción, que es ineficiente en datos grandes, pero muy eficiente en datos pequeños (digamos, de cinco a diez elementos), se utiliza como paso final, después de aplicar principalmente otro algoritmo, como la ordenación combinada o la ordenación rápida . La ordenación por combinación y la ordenación rápida son asintóticamente óptimas en datos grandes, pero la sobrecarga se vuelve significativa si se aplican a datos pequeños, de ahí el uso de un algoritmo diferente al final de la recursividad. Un algoritmo de ordenación híbrido altamente optimizado es Timsort , que combina ordenación por fusión, ordenación por inserción, junto con lógica adicional (incluida la búsqueda binaria ) en la lógica de fusión.

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 a la función, evitando una llamada a la 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. Esto es útil para la eficiencia cuando el algoritmo generalmente se encuentra con el caso base muchas veces, como en muchos algoritmos de árbol, pero por lo demás se considera un estilo deficiente, particularmente en el mundo académico, debido a la complejidad adicional.

Otro ejemplo de algoritmos híbridos por razones de rendimiento son introsort e introselect , que combinan un algoritmo para un rendimiento promedio rápido, recurriendo a otro algoritmo para garantizar (asintóticamente) un rendimiento óptimo en el peor de los casos. Introsort comienza con una ordenación rápida , pero cambia a una ordenación de montón si la ordenación rápida no progresa bien; de manera análoga, la introselect comienza con la selección rápida , pero cambia a la mediana de las medianas si la selección rápida no progresa bien.

Los algoritmos distribuidos centralizados a menudo se pueden considerar como algoritmos híbridos, que consisten en un algoritmo individual (que se ejecuta en cada procesador distribuido) y un algoritmo de combinación (que se ejecuta en un distribuidor centralizado); estos corresponden respectivamente a ejecutar el algoritmo completo en un procesador o ejecutar todo el cálculo en el distribuidor, combinando resultados triviales (un conjunto de datos de un elemento de cada procesador). Un ejemplo básico de estos algoritmos son los tipos de distribución , particularmente utilizados para la clasificación externa , que dividen los datos en subconjuntos separados, clasifican los subconjuntos y luego combinan los subconjuntos en datos totalmente clasificados; los ejemplos incluyen la clasificación de cubos y la clasificación flash .

Sin embargo, en general, los algoritmos distribuidos no necesitan ser algoritmos híbridos, ya que los algoritmos individuales o los algoritmos de combinación o comunicación pueden resolver diferentes problemas. Por ejemplo, en modelos como MapReduce , los pasos Map y Reduce resuelven diferentes problemas y se combinan para resolver un tercer problema diferente.

Ver también [ editar ]