En informática , un algoritmo en línea [1] es uno que puede procesar su entrada pieza por pieza de manera serial, es decir, en el orden en que la entrada se alimenta al algoritmo , sin tener toda la entrada disponible desde el principio.
Por el contrario, a un algoritmo offline se le proporcionan todos los datos del problema desde el principio y se le exige que genere una respuesta que resuelva el problema en cuestión. En la investigación de operaciones , el área en la que se desarrollan los algoritmos online se denomina optimización online .
Como ejemplo, considere los algoritmos de ordenamiento sort sort y insertion sort : el sort sort selecciona repetidamente el elemento mínimo del resto sin ordenar y lo coloca al frente, lo que requiere acceso a toda la entrada; por lo tanto, es un algoritmo offline. Por otro lado, el sort sort considera un elemento de entrada por iteración y produce una solución parcial sin considerar elementos futuros. Por lo tanto, el sort sort es un algoritmo online.
Tenga en cuenta que el resultado final de una ordenación por inserción es óptimo, es decir, una lista ordenada correctamente. En muchos problemas, los algoritmos en línea no pueden igualar el rendimiento de los algoritmos fuera de línea. Si la relación entre el rendimiento de un algoritmo en línea y un algoritmo fuera de línea óptimo está limitada, el algoritmo en línea se denomina competitivo . [1]
No todos los algoritmos offline tienen una contraparte online eficiente .
En la teoría gramatical se asocian con gramáticas de línea recta .
Como no conoce toda la información de entrada, un algoritmo en línea se ve obligado a tomar decisiones que más tarde pueden resultar no óptimas, y el estudio de los algoritmos en línea se ha centrado en la calidad de la toma de decisiones que es posible en este contexto. El análisis competitivo formaliza esta idea comparando el rendimiento relativo de un algoritmo en línea y fuera de línea para la misma instancia de problema. Específicamente, la relación competitiva de un algoritmo se define como la relación del peor caso de su costo dividido por el costo óptimo, sobre todas las entradas posibles. La relación competitiva de un problema en línea es la mejor relación competitiva lograda por un algoritmo en línea. Intuitivamente, la relación competitiva de un algoritmo da una medida de la calidad de las soluciones producidas por este algoritmo, mientras que la relación competitiva de un problema muestra la importancia de conocer el futuro de este problema.
Para otros puntos de vista sobre las entradas en línea a los algoritmos , consulte
Algunos algoritmos en línea :
Un problema que ejemplifica los conceptos de los algoritmos en línea es el problema del viajero canadiense . El objetivo de este problema es minimizar el costo de alcanzar un objetivo en un gráfico ponderado donde algunos de los bordes no son confiables y pueden haber sido eliminados del gráfico. Sin embargo, que un borde ha sido eliminado ( falló ) solo se revela al viajero cuando alcanza uno de los puntos finales del borde. El peor caso para este problema es simplemente que todos los bordes no confiables fallen y el problema se reduce al problema habitual del camino más corto . Se puede realizar un análisis alternativo del problema con la ayuda del análisis competitivo. Para este método de análisis, el algoritmo fuera de línea sabe de antemano qué bordes fallarán y el objetivo es minimizar la relación entre el rendimiento de los algoritmos en línea y fuera de línea. Este problema es PSPACE-completo .
Hay muchos problemas formales que ofrecen más de un algoritmo en línea como solución: