Un juego de búsqueda es un juego de suma cero para 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 supone que ni el buscador ni el que se esconde tienen conocimiento alguno sobre el movimiento del otro jugador hasta que su distancia entre ellos es menor o igual al radio de descubrimiento y en ese mismo momento se produce la captura. El juego es de suma cero y la recompensa es el tiempo dedicado a la búsqueda. Como modelos matemáticos, los juegos de búsqueda se pueden aplicar a áreas como los juegos de escondite que practican los niños o las representaciones de algunas situaciones tácticas militares. El área de los juegos de búsqueda se introdujo en el último capítulo del libro clásico de Rufus Isaacs "Juegos diferenciales" [1] y ha sido desarrollada aún más por Shmuel Gal [2] [3] y Steve Alpern . [3] El juego de la princesa y el monstruo trata con un objetivo en movimiento.
Una estrategia natural para buscar un objetivo estacionario en un gráfico (en el que los arcos tienen longitudes) es encontrar una curva cerrada mínima L que cubra todos los arcos del gráfico. (L se llama gira del cartero chino ). Luego, recorra L con probabilidad 1/2 para cada dirección. Esta estrategia parece funcionar bien si la gráfica es euleriana . En general, este recorrido aleatorio del cartero chino es de hecho una estrategia de búsqueda óptima si y sólo si el gráfico consta de un conjunto de gráficos eulerianos conectados en una estructura en forma de á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 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 utilizar una función de costo normalizada (llamada relación competitiva en la literatura sobre informática). 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 atraído mucha 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 mediante espirales exponenciales. [2] [3] [6] La búsqueda de un conjunto de rayos concurrentes se redescubrió más tarde en la literatura de informática como el "problema del camino de la vaca". [7]