El 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 un límite máximo de velocidad. Siempre se asume que ni el buscador ni el escondido son conscientes de los movimientos del otro jugador hasta que la distancia entre ellos es menor (o igual) al radio de detección y en ese mismo momento se realiza la captura. Como modelos matemáticos , los juegos de búsqueda se pueden aplicar en áreas tales como juegos de escondite jugados por niños o en algunas circunstancias tácticas militares. Juegos de búsqueda introducidos en el capítulo final del libro clásico de Rufus Isaacs"Juegos diferenciales" [1] y desarrollado posteriormente por Shmuel Gal [2] [3] y Steve Alpern [3] . El juego "La princesa y la bestia " se trata de un objetivo en movimiento.
Una estrategia de búsqueda natural para un objetivo fijo en un gráfico es encontrar la curva cerrada mínima L que pasa por todos los arcos del gráfico. (L se llama la ruta del cartero chino ). Luego damos la vuelta a L con probabilidad 1/2 para cada dirección. Esta estrategia funciona bien si el gráfico de Euler es . En general, la ruta del cartero chino es una estrategia óptima si y solo si el gráfico consiste en un conjunto de gráficos de Euler conectados por 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. Atravesar aleatoriamente el cartero chino (equivalente a pasar tres arcos en orden aleatorio) no es óptimo, y el camino óptimo para encontrar estos tres arcos es complicado [2] .
En el caso general de un área de búsqueda ilimitada, como en el caso del algoritmo en línea , una estrategia aceptable sería utilizar una función de pérdida normalizada (llamada ratio de competencia en la literatura ).
La trayectoria minimax para problemas de este tipo es siempre una secuencia geométrica (o una función exponencial para problemas continuos). Este resultado proporciona un método simple para encontrar una trayectoria minimax minimizando un solo parámetro (el generador de esta secuencia) en lugar de buscar en todo el espacio de trayectorias. Esta herramienta se utiliza en el problema de búsqueda lineal , es decir, el problema de encontrar un objetivo en una línea infinita, que ha recibido mucha atención recientemente y se ha analizado como un juego de búsqueda [5] . También se usó para encontrar una trayectoria minimax para encontrar un conjunto de rayos que convergen en un punto. La búsqueda óptima en el plano se realiza mediante espirales exponenciales [2] [3] [6] .
La búsqueda de rayos convergentes fue redescubierta más tarde en la literatura científica como el "problema del camino de la vaca" [7] .
| Teoría de juego | |
|---|---|
| Conceptos básicos |
|
| tipos de juegos |
|
| Conceptos de solución | |
| Ejemplos de juegos | |