En la teoría de la complejidad computacional , el problema de búsqueda lineal es un problema de búsqueda óptimo presentado por Richard E. Bellman [1] (considerado independientemente por Anatole Beck ). [2] [3] [4]
El problema
"Un ocultador inmóvil se ubica en la línea real de acuerdo con una distribución de probabilidad conocida. Un buscador, cuya velocidad máxima es uno, comienza desde el origen y desea descubrir el ocultador en el tiempo mínimo esperado. Se supone que el buscador puede cambiar el dirección de su movimiento sin ninguna pérdida de tiempo. También se supone que el buscador no puede ver al ocultador hasta que llega al punto en el que se encuentra el ocultador y el tiempo transcurrido hasta ese momento es la duración del juego ". Para encontrar el ocultador, el buscador debe 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 n-ésimo paso se denota por x n ) , y hacerlo de forma óptima. (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 generalmente se denomina problema de búsqueda lineal y un plan de búsqueda se llama trayectoria. Ha atraído mucha investigación, algunas de ellas bastante recientes. [ cuando? ]
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 la 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 ofrece estrategias de búsqueda que no son sensibles a los supuestos relacionados con la distribución del objetivo. Por lo tanto, también presenta un límite superior para el peor de los casos. Esta solución fue obtenida en el marco de un algoritmo en línea por 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 línea es 9, pero se puede reducir a 4,6 mediante una estrategia aleatoria. Demaine y col. dio una solución en línea con un costo de turno. [10]
Estos resultados fueron redescubiertos en la década de 1990 por los informáticos como el problema del camino de las vacas .
Ver también
Referencias
- ^ R. Bellman. Un problema de búsqueda óptima, SIAM Rev. (1963).
- ^ A. Beck. Sobre el problema de búsqueda lineal, Israel J. Mathematics (1964).
- ^ A. Beck. Más sobre el problema de búsqueda lineal, Israel J. Mathematics (1965).
- ^ A. Beck y M. Beck. El problema de la búsqueda lineal vuelve a surgir, Israel J. Mathematics (1986).
- ^ Alpern, Steve; Gal, Shmuel (2003), "Capítulo 8. Búsqueda en la línea infinita", La teoría de los juegos de búsqueda y las citas, Parte 2 , Serie internacional en Investigación de operaciones y ciencia de la gestión, 55 , pp. 123-144, doi : 10.1007 / 0-306-48212-6_8. En P. 124, Alpern y Gal escriben "no se ha encontrado ningún algoritmo para resolver el problema de una función de distribución de probabilidad general durante aproximadamente 37 años desde que se presentó por primera vez el LSP".
- ^ FT Bruss y JB Robertson. Una encuesta sobre el problema de la búsqueda lineal. Matemáticas. Sci. 13, 75 - 84, (1988).
- ^ S. Alpern y S. Gal. La teoría de los juegos de búsqueda y las citas . Springer (2003): 139-143.
- ^ A. Beck y DJ Newman. Aún más sobre el problema de la búsqueda lineal. Israel J. Math. (1970).
- ^ S. Gal. BÚSQUEDA DE JUEGOS, Academic Press (1980).
- ^ E. Demaine, S. Fekete y S. Gal. Búsqueda online con coste de turno. Informática Teórica (2006).