En ciencias de la computación, un algoritmo en línea se caracteriza por procesar los datos de entrada de forma secuencial, es decir, en el orden en que se le introducen, sin tener acceso a todos ellos desde el principio. En cambio, un algoritmo fuera de línea recibe todos los datos del problema desde el inicio y debe generar una solución que lo resuelva.
En investigación de operaciones, el área donde se desarrollan los algoritmos en línea se denomina optimización en línea.
Como ejemplo, se pueden considerar los problemas de ordenamiento, ordenamiento por selección y ordenamiento por inserción: el algoritmo de ordenación por selección elige repetidamente el elemento mínimo del resto sin ordenar y lo coloca al principio, lo que requiere acceso a toda la entrada; por lo tanto, es un algoritmo fuera de línea. Por otro lado, el algoritmo de ordenación por inserción considera un elemento de entrada por iteración y produce una solución parcial sin considerar los elementos posteriores. Por lo tanto, el algoritmo de ordenación por inserción es un algoritmo en línea.
Cabe destacar que el resultado final de un algoritmo de ordenación por inserción es óptimo, es decir, una lista correctamente ordenada. Para 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á acotada, el algoritmo en línea se denomina competitivo.
No todos los algoritmos fuera de línea tienen una contraparte eficiente en línea.
Definición Debido a que se desconoce la totalidad de la entrada, un algoritmo en línea se ve obligado a tomar decisiones que posteriormente podrían no ser óptimas. El estudio de los algoritmos en línea se ha centrado en la calidad de la toma de decisiones posible en este contexto. El análisis competitivo formaliza esta idea comparando el rendimiento relativo de un algoritmo en línea y uno fuera de línea para la misma instancia del problema. Específicamente, la razón de competitividad de un algoritmo se define como la razón en el peor de los casos entre su costo y el costo óptimo, considerando todas las entradas posibles. La razón de competitividad de un problema en línea es la mejor razón de competitividad alcanzada por un algoritmo en línea. Intuitivamente, la razón de competitividad de un algoritmo proporciona una medida de la calidad de las soluciones que produce, mientras que la razón de competitividad de un problema muestra la importancia de conocer el futuro para dicho problema.
Otras interpretaciones Para otros puntos de vista sobre las "entradas en línea a los algoritmos", véase: Algoritmo de transmisión: centrado en la cantidad de memoria necesaria para representar con precisión las entradas pasadas. Algoritmo dinámico: se centra en la complejidad temporal del mantenimiento de soluciones a problemas con entradas en línea.
Ejemplos de algunos algoritmos en línea Ordenamiento por inserción Perceptrón Muestreo de depósito
Algoritmo voraz Algoritmo de probabilidades Algoritmo de reemplazo de páginas Algoritmos para calcular la varianza Algoritmo de Ukkonen
Problemas en línea Un problema que ejemplifica los conceptos de algoritmos en línea es el Problema del viajero canadiense. El objetivo de este problema es minimizar el coste de alcanzar un destino en un grafo ponderado donde algunas aristas no son fiables y pueden haber sido eliminadas del grafo. Sin embargo, que una arista ha sido eliminada ("fallida") solo se revela al "viajero" cuando llega a uno de los extremos de la arista. El peor escenario para este problema es que todas las aristas no fiables fallen y el problema se reduzca al habitual problema del camino más corto. Un análisis alternativo del problema puede realizarse mediante análisis competitivo. En este método, el algoritmo fuera de línea conoce de antemano qué aristas 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.
Existen muchos problemas formales que ofrecen más de un algoritmo en línea como solución: Problema k-server Problema de programación de talleres Problema de actualización de listas Bandido multibrazo Problema de la secretaria Juegos de búsqueda Problema de alquiler de esquís Problema de búsqueda lineal Problema de la selección de cartera Problema del reemplazo de páginas Sistemas de tareas métricas Emparejamiento bipartito en línea
Véase también Modelo adversario (en inglés) Algoritmo dinámico (en inglés) Desigualdad del profeta (en inglés) Sistema de tiempo real Algoritmo de transmisión (en inglés)] Algoritmo secuencial (en inglés) Aprendizaje automático online
Referencias
Enlaces externos Bibliografía de artículos sobre algoritmos en línea
Algoritmos