En un juego de defensa de la torre, tienes una grilla NxM con un inicio, un final y una serie de paredes.
Los enemigos toman el camino más corto de principio a fin sin atravesar ninguna pared (generalmente no están limitados a la cuadrícula, pero por simplicidad, digamos que lo están. En cualquier caso, no pueden moverse a través de "agujeros" diagonales)
El problema (al menos para esta pregunta) es colocar hasta K paredes adicionales para maximizar el camino que los enemigos deben tomar, sin bloquear completamente el inicio desde el final. Por ejemplo, para K = 14
He determinado que esto es lo mismo que el problema de "k nodos más vitales":
Dado un gráfico no dirigido G = (V, E) y dos nodos s, t ∈ V, los k-nodos más vitales son los k nodos cuya eliminación maximiza la ruta más corta de s a t.
Khachiyan et al 1 mostraron que, incluso si la gráfica no está ponderada y es bipartita, incluso aproximar la longitud de la ruta máxima-más corta dentro de un factor de 2 es NP-Hard (dado k, s, t) .
Sin embargo, no todo está perdido: más tarde, L. Cai et al. 2 demostraron que, para los "gráficos de permutación bipartita", este problema se puede resolver en tiempo pseudo-polinomial utilizando el "modelo de intersección".
No he podido encontrar nada en gráficos de cuadrícula no ponderados específicamente, y no puedo entender cómo se relacionan los "gráficos de permutación bipartita", si es que lo hacen. ¿Se ha publicado alguna investigación relacionada con mi problema , tal vez estoy buscando en el lugar completamente equivocado? Incluso un algoritmo de aproximación pseudo-polinomial decente funcionaría bien. ¡Gracias!
1 L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, G. Rudolf y J. Zhao "Sobre problemas de interdicción de camino corto: interdicción limitada total y sabia de nodos", Teoría de sistemas informáticos 43 ( 2008), 2004-233. enlace .
2 L. Cai y J. Mark Keil, "Encontrar los k nodos más vitales en un gráfico de intervalos". enlace .
Nota: esta pregunta es un seguimiento de mi pregunta de stackoverflow que se encuentra aquí .
fuente
Respuestas:
fuente