Generar un laberinto de defensa de la torre, también conocido como Encontrar los K nodos más vitales ("interdicción de nodo a nodo") en un gráfico de cuadrícula no ponderado

22

En un juego de defensa de la torre, tienes una grilla NxM con un inicio, un final y una serie de paredes.

Imagen1

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)

Imagen2

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

Imagen3


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í .

BlueRaja - Danny Pflughoeft
fuente
3
Una aclaración: ¿no tiene permiso para eliminar un conjunto de nodos que desconectarían completamente el inicio del final?
David Eppstein
@David: Sí editado, perdón por la confusión. Todavía debe haber una solución.
BlueRaja - Danny Pflughoeft

Respuestas:

12

sfsfnmm(n1)sf(n1)l+(n2)sfsf

David Eppstein
fuente
Buena reducción!
Marzio De Biasi
Claro, eso es lo que pensé dadas las referencias en la pregunta; pero todavía necesito alguna solución, y esperaba algo mejor que el simple "usar recocido / algoritmos genéticos / similares". Mi pregunta es, ¿existe (como el caso del gráfico de permutación bipartita anterior) alguna solución pseudo-polinomial conocida, o incluso una aproximación medio decente que garantice algún límite?
BlueRaja - Danny Pflughoeft
3
O(n/polylog)Ω(n1ϵ)
No puedo seguir ese rastro de lógica, pero tomaré su palabra y le daré una marca de verificación muy triste :( ✓. ¡Gracias por tomarse el tiempo para pensar y responder esta pregunta, Profesor Eppstein!
BlueRaja - Danny Pflughoeft
Un año y mucho aprendizaje (de mi parte) más tarde, ahora entiendo y estoy de acuerdo con esta prueba. Gracias de nuevo :)
BlueRaja - Danny Pflughoeft