Un juego de búsqueda es un juego de suma cero para dos personas que se desarrolla 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 supone que ni el buscador ni el que se esconde tienen conocimiento alguno sobre el movimiento del otro jugador hasta que la distancia entre ellos sea menor o igual al radio de descubrimiento y en ese mismo momento se produzca la captura. El juego es de suma cero y la recompensa es el tiempo empleado en la búsqueda. Como modelos matemáticos, los juegos de búsqueda se pueden aplicar a áreas como los juegos de escondite que juegan los niños o las representaciones de algunas situaciones militares tácticas. El área de los juegos de búsqueda se introdujo en el último capítulo del clásico libro de Rufus Isaacs "Juegos diferenciales" [1] y ha sido desarrollada posteriormente por Shmuel Gal [2] [3] y Steve Alpern . [3] El juego de la princesa y el monstruo trata sobre un objetivo en movimiento.
Una estrategia natural para buscar un objetivo estacionario en un grafo (en el que los arcos tienen longitudes) es encontrar una curva cerrada mínima L que cubra todos los arcos del grafo. (L se llama recorrido del cartero chino ). Luego, recorra 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 grafo consiste en un conjunto de grafos eulerianos conectados en una estructura similar a un árbol. [4] Un ejemplo engañosamente simple de un grafo que no está en esta familia consiste en dos nodos conectados por tres arcos. El recorrido aleatorio del cartero chino (equivalente a recorrer 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 un dominio ilimitado, como en el caso de un algoritmo en línea , es utilizar una función de costo normalizada (llamada razó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 sobre un solo parámetro (el generador de esta secuencia) en lugar de buscar sobre todo el espacio de 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 atraído mucha atención durante varias décadas y se ha 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]