Problema de pesquisa linear - Linear search problem
Na teoria da complexidade computacional , o problema de busca linear é um problema de busca ótima introduzido por Richard E. Bellman e considerado independentemente por Anatole Beck .
O problema
"Um ocultador imóvel está localizado na linha real de acordo com uma distribuição de probabilidade conhecida. Um buscador, cuja velocidade máxima é um, começa na origem e deseja descobrir o ocultador em um tempo mínimo esperado. Supõe-se que o buscador pode alterar o direção de seu movimento sem qualquer perda de tempo. Também é assumido que o pesquisador não pode ver o escondedor até que ele realmente alcance o ponto em que o escondedor está localizado e o tempo decorrido até esse momento é a duração do jogo. " Para encontrar o ocultador, o pesquisador deve percorrer uma distância x 1 em uma direção, retornar à origem e percorrer a distância x 2 na outra direção, etc., (o comprimento do n-ésimo passo sendo denotado por x n ) , e fazê-lo de forma otimizada. (No entanto, uma solução ótima não precisa ter um primeiro passo e pode começar com um número infinito de pequenas 'oscilações'.) Esse problema é normalmente chamado de problema de busca linear e um plano de busca é chamado de trajetória. Ele atraiu muitas pesquisas, algumas delas bastante recentes.
O problema de pesquisa linear para uma distribuição de probabilidade geral não foi resolvido. No entanto, existe um algoritmo de programação dinâmica que produz uma solução para qualquer distribuição discreta e também uma solução aproximada, para qualquer distribuição de probabilidade, com qualquer precisão desejada.
O problema de busca linear foi resolvido por Anatole Beck e Donald J. Newman (1970) como um jogo de soma zero para duas pessoas. Sua trajetória minimax é dobrar a distância em cada etapa e a estratégia ótima é uma mistura de trajetórias que aumentam a distância em alguma constante fixa. Esta solução fornece estratégias de pesquisa que não são sensíveis às suposições sobre a distribuição do alvo. Portanto, também apresenta um limite superior para o pior cenário. Esta solução foi obtida no framework de um algoritmo online de Shmuel Gal , que também generalizou este resultado para um conjunto de raios concorrentes. A melhor razão competitiva online para a pesquisa na linha é 9, mas pode ser reduzida para 4,6 usando uma estratégia aleatória. Demaine et al. deu uma solução online com um custo de retorno.
Esses resultados foram redescobertos na década de 1990 por cientistas da computação como o problema do caminho das vacas .