En la teoría de la complejidad computacional , el problema de búsqueda lineal es un problema de búsqueda óptima introducido por Richard E. Bellman [1] y considerado independientemente por Anatole Beck . [2] [3] [4]
"Un objeto escondido inmóvil se encuentra en la línea real según una distribución de probabilidad conocida . Un buscador, cuya velocidad máxima es uno, parte del origen y desea descubrir al objeto escondido en el tiempo mínimo esperado. Se supone que el buscador puede cambiar la dirección de su movimiento sin ninguna pérdida de tiempo. También se supone que el buscador no puede ver al objeto escondido hasta que llega realmente al punto en el que se encuentra y el tiempo transcurrido hasta ese momento es la duración del juego."
El problema consiste en encontrar al que se esconde en el menor tiempo posible. En general, dado que el que se esconde puede estar a ambos lados del que busca y a una distancia arbitraria, el que busca tiene que oscilar de un lado a otro, es decir, tiene que recorrer una distancia x 1 en una dirección, regresar al origen y recorrer una distancia x 2 en la otra dirección, etc. (la longitud del paso n-ésimo se denota por x n ). (Sin embargo, una solución óptima no necesita tener un primer paso y podría comenzar con un número infinito de pequeñas "oscilaciones"). Este problema suele denominarse problema de búsqueda lineal y un plan de búsqueda se denomina trayectoria.
El problema de búsqueda lineal para una distribución de probabilidad general no está resuelto. [5] Sin embargo, existe un algoritmo de programación dinámica que produce una solución para cualquier distribución discreta [6] y también una solución aproximada, para cualquier distribución de probabilidad, con cualquier precisión deseada. [7]
El problema de búsqueda lineal fue resuelto por Anatole Beck y Donald J. Newman (1970) como un juego de suma cero para dos personas. Su trayectoria minimax es duplicar la distancia en cada paso y la estrategia óptima es una mezcla de trayectorias que aumentan la distancia en una constante fija. [8] Esta solución proporciona estrategias de búsqueda que no son sensibles a suposiciones sobre la distribución del objetivo. Por lo tanto, también presenta un límite superior para el peor escenario posible. Esta solución se obtuvo en el marco de un algoritmo en línea de Shmuel Gal , quien también generalizó este resultado a un conjunto de rayos concurrentes. [9] La mejor relación competitiva en línea para la búsqueda en la línea es 9, pero se puede reducir a 4,6 utilizando una estrategia aleatoria. Demaine et al. dieron una solución en línea con un costo de turno. [10]
Estos resultados fueron redescubiertos en la década de 1990 por científicos informáticos como el problema del camino de la vaca .