Un juego de búsqueda es un juego de suma cero de dos personas que tiene lugar en un conjunto llamado espacio de búsqueda. El buscador puede elegir cualquier trayectoria continua sujeta a una restricción de velocidad máxima. Siempre se asume que ni el buscador ni el escondido tienen conocimiento sobre el movimiento del otro jugador hasta que su distancia es menor o igual al radio de descubrimiento y en este mismo momento ocurre la captura. Como modelos matemáticos, los juegos de búsqueda se pueden aplicar a áreas tales como juegos de escondite que juegan los niños o representaciones de algunas situaciones militares tácticas. El área de los juegos de búsqueda se introdujo en el último capítulo del libro clásico de Rufus Isaacs "Differential Games" [1]y ha sido desarrollado más por Shmuel Gal [2] [3] y Steve Alpern . [3] El juego de la princesa y el monstruo se trata de un objetivo en movimiento.
Una estrategia natural para buscar un objetivo estacionario en un gráfico es encontrar una curva cerrada mínima L que cubra todos los arcos del gráfico. (L se llama gira del cartero chino ). Luego, atraviesa L con probabilidad 1/2 para cada dirección. Esta estrategia parece funcionar bien si el grafo es euleriano . En general, este recorrido aleatorio del cartero chino es de hecho una estrategia de búsqueda óptima si y solo si el gráfico consiste en un conjunto de gráficos eulerianos conectados en una estructura similar a un árbol. [4] Un ejemplo engañosamente simple de un gráfico que no pertenece a esta familia consta de dos nodos conectados por tres arcos. El recorrido aleatorio del cartero chino (equivalente a atravesar los tres arcos en un orden aleatorio) no es óptimo, y la forma óptima de buscar estos tres arcos es complicada.[2]
En general, el marco razonable para buscar en un dominio ilimitado, como en el caso de un algoritmo en línea , es usar una función de costo normalizada (llamada relación competitiva en la literatura de Ciencias de la Computación). La trayectoria minimax para problemas de este tipo es siempre una secuencia geométrica (o función exponencial para problemas continuos). Este resultado produce un método fácil para encontrar la trayectoria minimax minimizando un solo parámetro (el generador de esta secuencia) en lugar de buscar en todo el espacio de la trayectoria. Esta herramienta se ha utilizado para el problema de búsqueda lineal., es decir, encontrar un objetivo en la línea infinita, que ha llamado mucho la atención durante varias décadas y ha sido analizado como un juego de búsqueda. [5] También se ha utilizado para encontrar una trayectoria minimax para buscar un conjunto de rayos concurrentes. La búsqueda óptima en el plano se realiza utilizando espirales exponenciales. [2] [3] [6] La búsqueda de un conjunto de rayos concurrentes fue redescubierta más tarde en la literatura de Ciencias de la Computación como el 'problema del camino de la vaca'. [7]