En informática, un algoritmo en línea es uno que puede procesar pieza por pieza el input (entrada) de una manera en serie, es decir, en el orden que la entrada se alimenta al algoritmo, sin tener toda la entrada disponible desde el principio.
Por el contrario,en un algoritmo sin conexión se dan enteros los datos del problema desde el principio y no se requiere para emitir una respuesta que resuelve el problema en cuestión.
Debido a que no sabe toda la entrada, un algoritmo en línea se ve obligado a tomar decisiones que pueden más tarde resultan no ser óptima, 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 entorno. El análisis de la competencia formaliza esta idea comparando el rendimiento relativo de un algoritmo en línea y fuera de línea para la misma instancia 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 posibles entradas. La relación competitiva de un problema en línea es la mejor relación competitiva conseguida 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 para este problema.
No comments:
Post a Comment