algorithm - para - Resolviendo un juego de gráfico

juegos con mejores graficos 2018 pc (2)

He luchado un tiempo con un problema de un concurso de programación ( Andrew Stankevich Contest 21 ) sobre un juego que dice lo siguiente:

A Nick y Peter les gusta jugar el siguiente juego [...]. Dibujan un gráfico bipartito G no dirigido en una hoja de papel, y ponen una ficha en uno de sus vértices. Después de eso, hacen movimientos a su vez. Nick se mueve primero.
Un movimiento consiste en mover el token a lo largo del borde del gráfico. Después de esto, el vértice donde estaba el token antes del movimiento, junto con todos los bordes incidentales, se eliminan del gráfico. El jugador que no tiene movimientos válidos pierde el juego.

El gráfico se da y la tarea ahora es buscar un nodo de inicio dado, si el jugador que comienza gana o pierde si ambos jugadores juegan de manera óptima. Para resumir

Gráfica bipartita
Nos dan el nodo de inicio (por ejemplo, en el lado izquierdo)
Nos movemos por turnos, un movimiento consiste en seguir una ventaja, pero no podemos visitar un nodo que ya fue visitado
El jugador que no puede moverse pierde

Como el gráfico es bipartito, Nick (el primer jugador) siempre eliminará un nodo del lado izquierdo y Peter siempre eliminará un nodo del lado derecho.

El gráfico puede tener hasta 1000 nodos (como máximo 500 en cada lado) y 50000 bordes, por lo que se necesita un buen algoritmo de tiempo polinomial (el límite de tiempo aquí es de 2 segundos para resolver todas las posiciones iniciales, pero creo que podemos compartir mucho de información entre las diferentes posiciones de inicio).

Estoy bastante seguro de que esto se puede reducir a algún tipo de problema de cobertura o empaquetamiento de vértices, porque el gráfico es bipartito, pero no puedo encontrar una estrategia que se corresponda con ninguno de estos.

Conozco la solución para un caso especial: digamos que los lados tienen n ₁ yn ₂ vértices, respectivamente. Si hay una coincidencia de tamaño min (n ₁ , n ₂ ) y si el jugador del lado más pequeño comienza, entonces existe una estrategia ganadora: solo tiene que seguir los bordes combinados y automáticamente gana.

¿Algunas ideas?

Lindo problema. Creo que la solución prevista es calcular una coincidencia máxima y luego determinar qué vértices izquierdos pertenecen a cada coincidencia máxima. Estas son las victorias para el jugador uno.

La estrategia ganadora es elegir los bordes que pertenecen a una coincidencia máxima. Si el vértice de inicio v pertenece a cada coincidencia máxima, entonces el otro punto final w del borde e elegido por el jugador uno no pertenece a cada coincidencia máxima del gráfico menos v (ya que v pertenece a cada coincidencia máxima, la cardinalidad del máximo la coincidencia disminuye en uno después de la eliminación, por lo que, dado que e pertenece a una coincidencia máxima M, tenemos que M - e es máximo en el nuevo gráfico y deja el otro extremo de e sin concordar). Por el contrario, si existe una coincidencia máxima a la que v no pertenece, todos sus vecinos w pertenecen a todos los emparejamientos máximos del gráfico menos v (de lo contrario, encuentre una coincidencia máxima sin w y agregue el borde de v a w, contradiciendo la suposición de que la cardinalidad máxima de un emparejamiento no disminuía cuando eliminamos v).

Proposición. Nick (el primer jugador) gana comenzando desde el vértice v si este vértice pertenece a cada coincidencia máxima posible del gráfico dado. Lo probaremos en dos pasos.

Si hay una coincidencia máxima sin v , Nick pierde.
De hecho, dado que la coincidencia es máxima, no hay un camino de aumento desde v . Eso significa que cada ruta simple de longitud impar desde v puede prolongarse por un borde de la coincidencia. En términos de nuestro problema, significa que Peter puede continuar el juego después de cada jugada de Nick.
Si no hay coincidencia máxima sin v , Nick gana.
Considere cualquier posible coincidencia máxima. Muévete por el borde de esta coincidencia de v a, por ejemplo, u . Ahora, la coincidencia inicial menos el borde uv es una coincidencia máxima del gráfico restante que no incluye a u . Como sabemos por el paso 1, el jugador que se mueve ahora (que es Peter) está perdido.

En cuanto a la implementación, primero podemos construir una coincidencia máxima en O (VE) utilizando el algoritmo directo ( ver aquí una implementación de ejemplo) - resulta que el nombre común es el algoritmo de rutas de aumento de Kuhn.

Después de eso, mantienes una coincidencia máxima y observas todos los vértices. Si el vértice, digamos v , no está actualmente en la coincidencia, Nick pierde. Si es así, elimine el borde correspondiente, digamos vu , del emparejamiento, prohíba el vértice v temporalmente y ejecute una búsqueda de un camino de aumento desde u en O (E). Si no encuentra ese camino, Nick gana, y debe restaurar el borde que eliminó. De lo contrario, Nick pierde de nuevo, y la nueva coincidencia máxima puede dejarse intacta. El tiempo total de ejecución es O (VE) nuevamente.