Una variante de el Caballero de la gira del problema

Question

El caballero de la gira del problema es un famoso problema en el ajedrez y ciencia de la computación que pide a la siguiente pregunta: ¿se puede mover el caballo en un $n \ \times \ n$ tablero de ajedrez que visitas cada cuadrado exactamente una vez? La respuesta es sí iff $n\geq5$. Además, hay algoritmos que se pueden resolver en $O(n^2)$ del tiempo.

Tengo dos variaciones de la que se discute a continuación.

Fijar un $n \ \times \ n$ tablero de ajedrez. En esta variante, en lugar de un caballero tenemos $m$ caballeros. Estos caballeros se turnan en movimiento (es decir., un caballero se mueve, después de que otro, una vez que todos ellos se han movido, la primera que uno se mueve de nuevo y el ciclo se repite).

¿Cuál es el mayor $m$ tal que para algún posición inicial, cada caballero puede recorrer la junta (como se describe en el primer párrafo) sin poner en peligro cualquier otro caballero? Tenga en cuenta que es evidente que hay un límite superior en $m$ (por ejemplo, $n^2$).

En esencia, estoy buscando una función de $f:\mathbb{N}_{\geq 5} \to \mathbb{N}$ que se asigna a cada una de las $n$ mayor $m$.

Mi segunda variación es exactamente el mismo, salvo que ahora no hay restricciones en las vueltas. Después de un caballero se mueve, cualquier caballero puede mover, incluyendo la que se ha movido antes. No sé cómo estas variaciones se relacionan entre sí; tal vez son equivalentes.

También, como una función de la $n$ ¿cuál sería el tiempo de la complejidad de un algoritmo óptimo? Puede cualquiera de estas variantes pueden resolverse en el polinomio de tiempo?

Answer 1

Incluso $n$, $n \ge 6$, la respuesta es $m = n^2 - 1$ para ambas preguntas y el tiempo es $O(n^2)$.

Obviamente $m \le n^2 - 1$ es un límite superior, porque al menos una celda debe ser inicialmente libre. Veamos por qué es accesible.

Es posible construir un sistema cerrado (cíclico) recorrido por un caballero en el momento de la $O(n^2)$. El tour tiene la propiedad adicional de simetría, y el algo tiene la propiedad de buena paralelización (he. e. se tarda $O(1)$ $n^2$ procesadores).

Deje $C = v_1 v_2 \ldots v_n v_1$ ser la secuencia de las células en tales cerrado tour. A continuación, ponemos el primer caballero en $v_n,$ el segundo en $v_{n - 1}$, y así sucesivamente, la colocación de la última, $m$th caballero, en $v_2$. En la primera vuelta de la primera caballo mueve a $v_1$, el segundo se mueve a $v_n$, y así sucesivamente, el último que uno se mueve a $v_3$. Luego la primera a la que uno se mueve a $v_2$ y así sucesivamente y así sucesivamente. Cada caballero camina a través de todo el recorrido.

Por extraño $n$ hay también un más apretado límite superior: $m \le \frac{n^2 + 1}{2}$. De ello se desprende de una nota que nuestro grafo es bipartito y tiene una extraña orden, así que debemos empezar todo gira en la mayor parte de la gráfica (de $\frac{n^2 + 1}{2}$ de las células). Para la primera cuestión, el límite superior es aún menos por $1$, porque después de la primera vuelta todos los caballeros deben estar en la parte más pequeña de la gráfica (de $\frac{n^2 - 1}{2}$ de las células).

Puede ser algún tiempo más tarde voy a investigar el extraño caso de forma más precisa.