Algoritmo híbrido

Un algoritmo híbrido es uno que combina dos o más algoritmos que solucionan el mismo problema, ya sea escogiendo uno (a merced de los datos), o cambiando entre ellos sobre el curso del algoritmo. Esto se hace generalmente para combinar características deseadas de cada uno, a fin de que el algoritmo global sea mejor que los componentes individuales.

"Algoritmo híbrido" no se refiere a combinar algoritmos para resolver un problema–muchos algoritmos son las combinaciones de pedazos más simples–pero si combinar algoritmos que resuelven el mismo problema y que difieren en características particulares como el tiempo de ejecución para un tamaño de entrada dado.

Ejemplos

En la ciencia de la computación, los algoritmos híbridos son muy comunes en implementaciones del mundo real para optimizar algoritmos recursivos, en particular implementaciones que usan técnicas como divide y vencerás, donde el tamaño de los datos decrece a medida que la profundidad de la recursión aumenta. En este caso, un algoritmo es usado para el aprovechamiento global (en datos grandes), pero en lo profundo de la recursión, se cambia y se usa un algoritmo diferente, el cual es más eficiente para entradas pequeñas. Un ejemplo común se da en los algoritmos de ordenación, como es el caso del algoritmo InsertionSort, el cual es ineficiente para grandes entradas de datos, pero muy eficiente para pequeñas entradas (cinco a diez elementos), este es utilizado como el paso final, después de primordialmente aplicado otro algoritmo, como MergeSort u QuickSort; MergeSort o QuickSort son asintóticamente óptimos para grandes entradas, pero su tiempo de ejecución puede ser significativo para entradas pequeñas, por lo que el uso de un algoritmo diferente al final de la recursión es una idea original. Un algoritmo híbridos altamente optimizado es el TimSort el cual combina MergeSort, InsertionSort, conjuntamente con la lógica adicional (incluyendo búsqueda binaria) en la lógica de unión.

Un procedimiento general para un algoritmo recursivo híbrido simple es saltarse el caso base. En este caso, si el siguiente paso dará como resultado el caso base es comprobado antes de la llamada de función, evitando una llamada innecesaria de función. Por ejemplo, en un árbol, en vez de hacer recursión hacia un nodo hijo y luego inspeccionar si es nulo, se chequea nulidad antes de hacer el llamado recursivo. Esto es útil para la eficiencia cuando el algoritmo usualmente encuentra el caso de base muchas veces, en muchos algoritmos de árboles pasa esto, pero por otro lado es escasamente considerado, en particular por académicos, debido a la complejidad añadida. Otra uso de algoritmos híbridos por el tiempo de ejecución son IntroSort e IntroSelect. IntroSort comienza con un QuickSort, pero hace cambios para un HeapSort si el QuickSort no progresa bien; análogamente el IntroSelect empieza con QuickSelect, pero cambia a mediana de medianas si QuickSelect no progresa bien.

Los algoritmos distribuidos centralizados a menudo pueden ser considerados como algoritmos híbridos, consistiendo de un algoritmo individual (corrido en cada procesador distribuido), respectivamente y un algoritmo (corrido en un distribuidor centralizado) que combina – éstos corresponden a correr el algoritmo entero en un procesador, o correr la computación entera en el distribuidor y combinar resultados. Un ejemplo básico de estos algoritmos son los repartidores de ordenaciones, en particular usados para la ordenación externa, cuál divide los datos en subconjuntos separados, ordena los subconjuntos, y luego combina los subconjuntos en datos completamente ordenados, ejemplos son Bucket y FlashSort.

Sin embargo, en general los algoritmos distribuidos no tienen porque ser necesariamente híbridos. Por ejemplo, en los modelos como MapReduce, el Map y Reduce solucionan problemas diferentes, y están combinados para solucionar un problema diferente, tercer problema.

Referencias

Esta página se editó por última vez el 15 feb 2021 a las 18:47.