Otimização online - Online optimization
A otimização online é um campo da teoria da otimização , mais popular na ciência da computação e na pesquisa operacional , que lida com problemas de otimização sem nenhum conhecimento ou conhecimento do futuro incompleto (online). Esses tipos de problemas são denotados como problemas online e são vistos como opostos aos problemas de otimização clássicos onde informações completas são assumidas (offline). A pesquisa sobre otimização online pode ser diferenciada em problemas online onde várias decisões são feitas sequencialmente com base em uma entrada peça por peça e aqueles em que a decisão é tomada apenas uma vez. Um famoso problema online em que a decisão é tomada apenas uma vez é o problema do aluguel de esqui . Em geral, a saída de um algoritmo online é comparada à solução de um algoritmo offline correspondente, que é necessariamente sempre ótimo e conhece toda a entrada antecipadamente (análise competitiva).
Em muitas situações, as decisões presentes (por exemplo, alocação de recursos) devem ser feitas com conhecimento incompleto do futuro ou as suposições distributivas sobre o futuro não são confiáveis. Nesses casos, a otimização online pode ser usada, o que é diferente de outras abordagens, como otimização robusta , otimização estocástica e processos de decisão de Markov.
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 usual do caminho mais curto . 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 do servidor k
- 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
Referências
 |
Este artigo é um esboço sobre ciência . Você pode ajudar a Wikipedia expandindo-a . |