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 asume que ni el buscador ni el ocultador tienen conocimiento del movimiento del otro jugador hasta que la distancia entre ellos es menor o igual al radio de descubrimiento y en ese mismo momento ocurre la captura. 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 juegos de búsqueda se introdujo en el último capítulo del libro clásico de Rufus Isaacs "Juegos diferenciales" [1]y ha sido desarrollado por Shmuel Gal [2] [3] y Steve Alpern . [3] El juego de princesas y monstruos trata con un objetivo en movimiento.
Estrategia
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 la gráfica es euleriana . 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 en forma de árbol. [4] Un ejemplo engañosamente simple de un gráfico que no pertenece a esta familia consiste en 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]
Dominios ilimitados
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 (denominada razón competitiva en la literatura 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 proporciona 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 la 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 mediante el uso de 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 las vacas". [7]
Referencias
- ^ Rufus Isaacs, Juegos diferenciales , John Wiley and Sons, (1965),
- ↑ a b c S. Gal, Search Games , Academic Press, Nueva York (1980)
- ↑ a b c S. Alpern y S. Gal, The Theory of Search Games and Rendezvous , Springer (2003).
- ^ S. Gal, Sobre la optimización de una estrategia simple para buscar gráficos , Int. J. Teoría de juegos (2000).
- ^ A. Beck y DJ Newman. Aún más sobre el problema de la búsqueda lineal . Israel J. Math. (1970).
- ^ M. Chrobak, Una princesa nadando en la niebla en busca de una vaca monstruosa, ACM Sigact news, 35 (2), 74–78 (2004).
- ^ MY Kao, JH Reif y SR Tate, Buscando en un entorno desconocido: un algoritmo aleatorizado óptimo para el problema del camino de las vacas , SODA 1993.