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 :

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:

Veja também

Referências

links externos