Juego de persecución-evasión

El juego diferencial de persecución-evasión (variante del juego conocido como policías y ladrones y búsquedas gráficas) es una familia de problemas en matemáticas y ciencias de la computación en el que un grupo intenta localizar a los miembros de otro grupo en un entorno cerrado. Los primeros trabajos sobre los problemas de este tipo modelaron el entorno geométricamente.​ En 1976, Torrence Parsons introdujo una formulación en el que el movimiento se ve limitada por un gráfico.​ La formulación geométrica es a veces llamada persecución-evasión continua, y la formulación gráfica pos-evasión discreta (también llamada búsqueda gráfica).​ La investigación actual se limita típicamente a una de estas dos formulaciones.

Formulación discreta

En la formulación discreta del problema pos-evasión, el medio ambiente se modela como un gráfico.

Definición del problema

Hay variantes innumerables posibles de persecución-evasión, aunque tienden a compartir muchos elementos. Un ejemplo típico básico, es el siguiente (policías y ladrones)​ juegos: Perseguidores y evasores ocupan los nodos de un grafo. Las dos partes tienen alternativas o decisiones posible, que consisten en que cada miembro se quede donde está o se mueve a lo largo de un borde a un nodo adyacente. Si un perseguidor ocupa el mismo nodo que un evasor el evasor es capturado y se le retira del gráfico. La pregunta que se plantea es por lo general el número de perseguidores que son necesarios para asegurar la eventual captura de todos los evasores.​

A menudo, las reglas de movimiento cambian la velocidad de los evasores. Esta velocidad es el número máximo de aristas en las que un evasor puede moverse a lo largo de en un solo turno. En el ejemplo anterior, los evasores tienen una velocidad de uno. En el otro extremo es el concepto infinito de velocidad, que permite que un evasor para moverse a cualquier nodo en el gráfico siempre y cuando haya un camino entre sus posiciones originales y finales que no contenga nodos ocupados por un perseguidor. Del mismo modo algunas variantes arman a los perseguidores con "helicópteros", que les permiten moverse a cualquier vértice en su turno sin recorrer un punto previo.

Otras variantes ignoran la restricción de que los perseguidores y evasores siempre deben ocupar un nodo y permitir la posibilidad de que se encuentren a algún lugar a lo largo de un borde. Estas variantes se refieren a menudo a problemas tan amplios, mientras que las variantes anteriores entrarían en la categoría de búsqueda de problemas.

Variantes

Existen varias variantes que son equivalentes a los parámetros de gráfico importantes. En concreto, la búsqueda del número de perseguidores necesarios para capturar un solo evasor con velocidad infinita en un grafo G (cuando perseguidores y evasor no tienen manera de moverse giro a giro, sino que se mueven al mismo tiempo) es equivalente a encontrar el punto de la gráfica.

Referencias

• Datos: Q7261573