Algoritmo en línea - Online algorithm
En ciencias de la computación , un algoritmo en línea es aquel que puede procesar su entrada pieza por pieza en serie, 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, un algoritmo fuera de línea recibe todos los datos del problema desde el principio y se requiere para generar una respuesta que resuelva el problema en cuestión. En la investigación de operaciones , el área en la que se desarrollan los algoritmos en línea se denomina optimización en línea .
Como ejemplo, considere los algoritmos de clasificación clasificación por selección y clasificación por inserción : la clasificación por selección selecciona repetidamente el elemento mínimo del resto sin clasificar y lo coloca al frente, lo que requiere acceso a toda la entrada; por tanto, es un algoritmo fuera de línea. Por otro lado, la ordenación por inserción considera un elemento de entrada por iteración y produce una solución parcial sin considerar elementos futuros. Por tanto, la ordenación por inserción es un algoritmo en línea.
Tenga en cuenta que el resultado final de una ordenación por inserción es óptimo, es decir, una lista ordenada correctamente. 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á limitada, el algoritmo en línea se denomina competitivo .
No todos los algoritmos fuera de línea tienen una contraparte en línea eficiente .
Definición
Al no conocer toda la entrada, un algoritmo online se ve obligado a tomar decisiones que luego pueden resultar no óptimas, y el estudio de los algoritmos online se ha centrado en la calidad de la toma de decisiones que es posible en este escenario. El análisis competitivo formaliza esta idea al comparar 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 todos los insumos 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.
Otras interpretaciones
Para conocer otros puntos de vista sobre entradas en línea a algoritmos , consulte
- algoritmo de transmisión : se centra en la cantidad de memoria necesaria para representar con precisión las entradas pasadas;
- algoritmo dinámico : se centra en la complejidad temporal de mantener soluciones a problemas con entradas en línea.
Ejemplos
Algunos algoritmos en línea :
- Tipo de inserción
- Perceptrón
- Muestreo de yacimientos
- Algoritmo codicioso
- Modelo adversario
- Sistemas de tareas métricas
- Algoritmo de probabilidades
- Algoritmo de reemplazo de página
- 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 costo de alcanzar un objetivo en un gráfico ponderado donde algunos de los bordes no son confiables y pueden haberse eliminado del gráfico. Sin embargo, que un borde ha sido eliminado ( fallido ) solo se revela al viajero cuando llega a uno de los puntos finales del borde. El peor de los casos para este problema es simplemente que todos los bordes no fiables fallan y el problema se reduce al problema habitual de la ruta más corta . 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 está completo en PSPACE .
Hay muchos problemas formales que ofrecen más de un algoritmo en línea como solución:
- k- problema del servidor
- Problema de programación del taller de trabajo
- Problema de actualización de lista
- Problema de bandido
- Problema de secretaria
- Buscar juegos
- Problema de alquiler de esquís
- Problema de búsqueda lineal
- Problema de selección de cartera
Ver también
- Algoritmo dinámico
- Algoritmo de transmisión
- API simple para XML
- Computación en tiempo real
- Algoritmo secuencial
- Aprendizaje automático en línea / Aprendizaje fuera de línea
Referencias
- Borodin, A .; El-Yaniv, R. (1998). Computación en línea y análisis competitivo . Prensa de la Universidad de Cambridge. ISBN 0-521-56392-5 .