Algoritmo online - Online algorithm
Em informática , um algoritmo online é aquele que pode processar sua entrada peça a peça de forma serial, ou seja, na ordem em que a entrada é enviada ao algoritmo , sem ter toda a entrada disponível desde o início.
Em contraste, um algoritmo offline recebe todos os dados do problema desde o início e é necessário para produzir uma resposta que resolve o problema em questão. Na pesquisa operacional , a área em que os algoritmos online são desenvolvidos é chamada de otimização online .
Como exemplo, considere os algoritmos de classificação classificação por seleção e classificação por inserção : a classificação por seleção seleciona repetidamente o elemento mínimo do restante não classificado e o coloca na frente, o que requer acesso a toda a entrada; é, portanto, um algoritmo offline. Por outro lado, a classificação por inserção considera um elemento de entrada por iteração e produz uma solução parcial sem considerar os elementos futuros. Portanto, a ordenação por inserção é um algoritmo online.
Observe que o resultado final de uma classificação por inserção é ótimo, ou seja, uma lista classificada corretamente. Para muitos problemas, os algoritmos online não podem corresponder ao desempenho dos algoritmos offline. Se a razão entre o desempenho de um algoritmo online e um algoritmo offline ótimo for limitada, o algoritmo online é chamado de competitivo .
Nem todo algoritmo offline tem uma contraparte online eficiente .
Definição
Por não conhecer toda a entrada, um algoritmo online é forçado a tomar decisões que podem posteriormente não ser ideais, e o estudo de algoritmos online tem se concentrado na qualidade da tomada de decisão possível nesse ambiente. A análise competitiva formaliza essa ideia comparando o desempenho relativo de um algoritmo online e offline para a mesma instância de problema. Especificamente, a razão competitiva de um algoritmo é definida como a razão de pior caso de seu custo dividido pelo custo ótimo, sobre todas as entradas possíveis. A razão competitiva de um problema online é a melhor razão competitiva alcançada por um algoritmo online. Intuitivamente, a razão competitiva de um algoritmo dá uma medida sobre a qualidade das soluções produzidas por esse algoritmo, enquanto a razão competitiva de um problema mostra a importância de se conhecer o futuro desse problema.
Outras interpretações
Para outros pontos de vista sobre entradas online para algoritmos , consulte
- algoritmo de streaming : focando na quantidade de memória necessária para representar com precisão as entradas anteriores;
- algoritmo dinâmico : com foco na complexidade do tempo de manutenção de soluções para problemas com entradas online.
Exemplos
Alguns algoritmos online :
- Classificação de inserção
- Perceptron
- Amostragem de reservatório
- Algoritmo ganancioso
- Modelo adversário
- Sistemas de tarefas métricas
- Algoritmo de probabilidades
- Algoritmo de substituição de página
- Algoritmos para calcular a variância
- Algoritmo de Ukkonen
Problemas online
Um problema que exemplifica os conceitos de algoritmos online é o Problema do Viajante Canadense . O objetivo deste problema é minimizar o custo de atingir uma meta em um gráfico ponderado onde algumas das arestas não são confiáveis e podem ter sido removidas do gráfico. No entanto, se uma aresta foi removida ( falhou ), só é revelado ao viajante quando ele atinge um dos pontos finais da aresta. O pior caso para esse problema é simplesmente que todas as arestas não confiáveis falham e o problema se reduz ao problema do caminho mais curto usual . Uma análise alternativa do problema pode ser feita com a ajuda da análise competitiva. Para este método de análise, o algoritmo offline sabe com antecedência quais arestas irão falhar e o objetivo é minimizar a relação entre o desempenho dos algoritmos online e offline. Este problema é PSPACE completo .
Existem muitos problemas formais que oferecem mais de um algoritmo online como solução:
- problema k -server
- Problema de agendamento da oficina
- Problema de atualização de lista
- Problema de bandido
- Problema de secretária
- Jogos de busca
- Problema de aluguel de esqui
- Problema de pesquisa linear
- Problema de seleção de portfólio
Veja também
- Algoritmo dinâmico
- Algoritmo de streaming
- API simples para XML
- Computação em tempo real
- Algoritmo sequencial
- Aprendizado de máquina online / aprendizado offline
Referências
- Borodin, A .; El-Yaniv, R. (1998). Computação online e análise competitiva . Cambridge University Press. ISBN 0-521-56392-5 .