algorithm - torres - Generación de un laberinto de defensa de torre(el laberinto más largo con paredes limitadas): ¿heurística casi óptima?
juegos de oleadas (8)
En un juego de defensa de torre, tienes una cuadrícula de NxM con un inicio, un acabado y una serie de muros.
Los enemigos toman el camino más corto de principio a fin sin pasar a través de ninguna pared (normalmente no están limitados a la cuadrícula, pero para simplificar, digamos que lo son. En cualquier caso, no pueden moverse a través de "agujeros" diagonales)
El problema (al menos para esta pregunta) es colocar hasta K muros adicionales para maximizar el camino que deben seguir los enemigos. Por ejemplo, para K = 14
Mi intuición me dice que este problema es NP-duro si (como espero hacerlo) lo generalizamos para incluir los puntos de referencia que deben visitarse antes de pasar al final, y posiblemente también sin puntos de referencia.
Pero, ¿hay alguna heurística decente para soluciones casi óptimas?
[Editar] He publicado una pregunta relacionada here .
A riesgo de afirmar lo obvio, aquí hay un algoritmo
1) Find the shortest path
2) Test blocking everything node on that path and see which one results in the longest path
3) Repeat K times
De manera ingenua, esto tomará O (K * (V + E log E) ^ 2) pero con un poco de trabajo podría mejorar 2 solo recalculando rutas parciales.
Como mencionó, simplemente tratar de romper el camino es difícil porque si la mayoría de los descansos simplemente agregan una longitud de 1 (o 2), es difícil encontrar los puntos de estrangulamiento que llevan a grandes ganancias.
Si toma el corte de vértice mínimo entre el inicio y el final, encontrará los puntos de estrangulación para toda la gráfica. Un algoritmo posible es este
1) Find the shortest path
2) Find the min-cut of the whole graph
3) Find the maximal contiguous node set that intersects one point on the path, block those.
4) Wash, rinse, repeat
3) es la parte importante y por qué este algoritmo también puede funcionar mal. También podrías intentar
- El conjunto de nodos más pequeño que se conecta con otros bloques existentes.
- encontrando todas las agrupaciones de vértices contiguas en el corte del vértice, probando cada una de ellas para la ruta más larga a la vez que el primer algoritmo
El último es lo que podría ser más prometedor.
Si encuentra un corte de vértice mínimo en toda la gráfica, encontrará los puntos de estrangulación para toda la gráfica.
Aquí hay un pensamiento. En su cuadrícula, agrupe los muros adyacentes en islas y trate cada isla como un nodo gráfico. La distancia entre nodos es el número mínimo de muros que se necesitan para conectarlos (para bloquear al enemigo).
En ese caso, puede comenzar a maximizar la longitud del camino bloqueando los arcos más baratos.
Creo que podemos reducir el problema múltiple máximo contenido a la satisfacibilidad booleana y mostrar la integridad de NP a través de cualquier dependencia en este subproblema. Debido a esto, los algoritmos spinning_plate proporcionados son razonables, ya que las heurísticas, la precomputación y el aprendizaje automático son razonables , y el truco se convierte en encontrar la mejor solución heurística si deseamos un error aquí.
Considera una tabla como la siguiente:
..S........
#.#..#..###
...........
...........
..........F
Esto tiene muchos de los problemas que causan el fracaso de las soluciones codiciosas y limitadas. Si miramos esa segunda fila:
#.#..#..###
Nuestras compuertas lógicas están, en una matriz 2D basada en 0 ordenada como [row][column] :
[1][4], [1][5], [1][6], [1][7], [1][8]
Podemos volver a renderizar esto como una ecuación para satisfacer el bloque:
if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]):
traversal_cost = INFINITY; longest = False # Infinity does not qualify
Excepto el infinito como un caso insatisfactorio, retrocedemos y reenviamos esto como:
if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]:
traversal_cost = 6; longest = True
Y nuestra relación booleana oculta cae entre todas estas puertas. También puede demostrar que las pruebas geométricas no pueden fractalizar de forma recursiva, porque siempre podemos crear un muro que tenga exactamente el ancho o la altura N-1 , y esto representa una parte crítica de la solución en todos los casos (por lo tanto, dividir y vencer ) t te ayuda).
Además, porque las perturbaciones en diferentes filas son significativas:
..S........
#.#........
...#..#....
.......#..#
..........F
Podemos demostrar que, sin un conjunto completo de identidades geométricas computables, el espacio de búsqueda completo se reduce a N-SAT.
Por extensión, también podemos mostrar que esto es trivial para verificar y no polinomial para resolver a medida que el número de puertas se acerca al infinito. Como era de esperar, esta es la razón por la que los juegos de defensa de la torre siguen siendo tan divertidos para los humanos. Obviamente, es deseable una prueba más rigurosa, pero este es un comienzo esquelético.
Tenga en cuenta que puede reducir significativamente el término n en su relación n-elija-k. Debido a que podemos mostrar recursivamente que cada perturbación debe estar en la ruta crítica, y porque la ruta crítica siempre es computable en tiempo O (V + E) (con algunas optimizaciones para acelerar las cosas para cada perturbación), puede reducir significativamente su espacio de búsqueda a un costo de una búsqueda en primer lugar para cada torre adicional agregada al tablero.
Debido a que podemos asumir tolerablemente O (n ^ k) para una solución determinista, un enfoque heurístico es razonable. Por lo tanto, mi consejo se encuentra entre la respuesta de spinning_plate y la de Soravux , con miras a las técnicas de aprendizaje automático aplicables al problema.
La 0ª solución: use una AI tolerable pero subóptima, en la que spinning_plate proporcione dos algoritmos utilizables. De hecho, estos se aproximan a la cantidad de jugadores ingenuos que se acercan al juego, y esto debería ser suficiente para un juego simple, aunque con un alto grado de explotabilidad.
La solución de primer orden: utilizar una base de datos. Debido a la formulación del problema, no ha demostrado la necesidad de calcular la solución óptima sobre la marcha. Por lo tanto, si relajamos la restricción de acercarnos a un tablero al azar sin información, simplemente podemos calcular el óptimo para todos los K tolerables para cada tablero. Obviamente, esto solo funciona para una pequeña cantidad de tableros: con V! Posibles estados de la placa para cada configuración, no podemos calcular de manera tolerable todos los óptimos a medida que V hace muy grande.
La solución de segundo orden: utilizar un paso de aprendizaje automático. Promueva cada paso a medida que cierra una brecha que resulta en un costo transversal muy alto, ejecutando hasta que su algoritmo converja o no se pueda encontrar una solución más óptima que la codicia. Una gran cantidad de algoritmos son aplicables aquí, así que recomiendo buscar los clásicos y la literatura para seleccionar el correcto que funcione dentro de las restricciones de su programa.
La mejor heurística puede ser un mapa de calor simple generado por un recorrido recursivo, primero la profundidad recursiva, que es consciente del estado local, y clasifica los resultados por más o menos comúnmente atravesados después del recorrido O (V ^ 2). El proceder a través de esta salida identifica con avidez todos los cuellos de botella, y hacerlo sin hacer imposible la revisión es completamente posible (verificar que esto sea O (V + E)).
Juntándolo todo, probaría una intersección de estos enfoques, combinando el mapa de calor y las identidades de la ruta crítica. Supongo que aquí hay suficiente para encontrar una buena prueba geométrica funcional que satisfaga todas las restricciones del problema.
No has demostrado la necesidad de que este algoritmo sea en tiempo real, pero puedo estar equivocado con respecto a este principio. A continuación, podría precalcular las posiciones de bloque.
Si puede hacer esto de antemano y luego simplemente hacer que la IA construya el laberinto roca por roca como si fuera un tipo de árbol, podría usar algoritmos genéticos para aliviar su necesidad de heurística. Necesitaría cargar cualquier tipo de marco de algoritmo genético, comenzar con una población de bloques no móviles (su mapa) y bloques móviles colocados al azar (bloques que la AI colocaría). Luego, evoluciona la población haciendo cruces y transmutaciones sobre bloques móviles y luego evalúa a los individuos dando más recompensa al camino más largo calculado. Entonces simplemente tendría que escribir una calculadora de ruta eficiente en recursos sin la necesidad de tener heurísticas en su código. En su última generación de su evolución, tomaría el individuo de más alto rango, que sería su solución, por lo tanto, su patrón de bloque deseado para este mapa.
Se ha comprobado que los algoritmos genéticos lo llevan, en una situación ideal, a un máximo (o mínimo) local en un tiempo razonable, que puede ser imposible de alcanzar con soluciones analíticas en un conjunto de datos suficientemente grande (es decir, un mapa lo suficientemente grande en su situación).
No ha indicado el idioma en el que va a desarrollar este algoritmo, por lo que no puedo proponer marcos que se adapten perfectamente a sus necesidades.
Tenga en cuenta que si su mapa es dinámico, lo que significa que el mapa puede cambiar con respecto a las iteraciones de defensa de la torre, es posible que desee evitar esta técnica, ya que puede ser demasiado intensivo para volver a evolucionar a una nueva población en cada ola.
No soy un experto en algoritmos, pero al mirar la cuadrícula me pregunto si el juego de la vida de Conway podría ser útil para esto. Con una semilla inicial razonable y reglas bien elegidas sobre el nacimiento y la muerte de las torres, puedes probar muchas semillas y las generaciones posteriores en un corto período de tiempo.
Ya tienes una medida de la forma física en la longitud del camino de los creeps, por lo que puedes elegir el mejor en consecuencia. No sé qué tan bien (en todo caso) se aproximaría al mejor camino, pero sería una cosa interesante de usar en una solución.
No tengo idea de si esto funcionaría, porque podrías crear nuevas islas usando tus puntos. Pero podría ayudar a averiguar dónde poner las paredes.
Sugiero utilizar una primera búsqueda de amplitud modificada con una cola de prioridad de longitud K que rastree las mejores rutas K entre cada isla.
Yo, por cada isla de paredes conectadas, pretendería que es una luz. (una luz especial que solo puede enviar rayos de luz horizontales y verticales)
Usa el trazado de rayos para ver a qué otras islas puede llegar la luz.
diga Island1 (i1) golpea i2, i3, i4, i5 pero no golpea i6, i7 ..
entonces tendrías línea (i1, i2), línea (i1, i3), línea (i1, i4) y línea (i1, i5)
Marque la distancia de todos los puntos de la cuadrícula para ser infinito. Establezca el punto de inicio como 0.
Ahora usa la primera búsqueda de amplitud desde el principio. Cada punto de la cuadrícula, marque la distancia de ese punto de cuadrícula para que sea la distancia mínima de sus vecinos.
Pero ... aquí está la trampa ...
cada vez que llegas a un punto de la cuadrícula que está en una línea () entre dos islas, en lugar de registrar la distancia como el mínimo de sus vecinos, debes convertirla en una cola de prioridad de longitud K. Y registrar las K rutas más cortas a esa línea () desde cualquiera de la otra línea () s
Esta cola de prioridad permanece igual hasta que llegue a la siguiente línea (), donde agrega todas las preguntas de prioridad que entran en ese punto.
Presento un enfoque codicioso y tal vez esté cerca del óptimo (pero no pude encontrar el factor de aproximación). La idea es simple, deberíamos bloquear las celdas que se encuentran en lugares críticos del laberinto. Estos lugares pueden ayudar a medir la conectividad del laberinto. Podemos considerar la conectividad de vértice y encontramos un corte de vértice mínimo que desconecta el inicio y final: (s, f) . Después de eso eliminamos algunas células críticas.
Para convertirlo en la gráfica, toma dual de laberinto. Encuentre el corte del vértice mínimo (s, f) en esta gráfica. Luego examinamos cada vértice en este corte. Eliminamos un vértice, su eliminación aumenta la longitud de todas las rutas s, f o si está en la ruta de longitud mínima de s a f. Después de eliminar un vértice, repite recursivamente el proceso anterior durante k tiempo.
Pero hay un problema con esto, esto es cuando eliminamos un vértice que corta cualquier camino de s a f. Para evitar esto, podemos ponderar el nodo de corte lo más alto posible, lo que significa primero calcular el corte mínimo (s, f), si el resultado del corte es solo un nodo, hágalo ponderado y establezca un peso alto como n ^ 3 en ese vértice, ahora nuevamente calcular el mínimo, s, f corte, vértice de corte único en el cálculo anterior, no pertenece al nuevo corte debido a la espera.
Pero si solo hay un camino entre s, f (después de algunas iteraciones) no podemos mejorarlo. En este caso, podemos utilizar algoritmos codiciosos normales, como eliminar un nodo de uno de los caminos más cortos desde s hasta f, que no pertenece a ningún corte. Después de eso podemos lidiar con el mínimo corte de vértice.
El tiempo de ejecución del algoritmo en cada paso es:
min-cut + path finding for all nodes in min-cut
O(min cut) + O(n^2)*O(number of nodes in min-cut)
Y como el número de nodos en el corte mínimo no puede ser mayor que O (n ^ 2) en una situación muy pesimista, el algoritmo es O (k n ^ 4), pero normalmente no debería tomar más de O (k n ^ 3) Debido a que normalmente el algoritmo de corte mínimo domina la búsqueda de ruta, también normalmente la búsqueda de ruta no toma O (n ^ 2).
Supongo que la elección codiciosa es un buen punto de inicio para los algoritmos de recocido simulados.
PS: el corte mínimo del vértice es similar al corte mínimo del borde , y se puede aplicar un enfoque similar al corte max-flow / min en el corte mínimo del vértice , solo asuma cada vértice como dos vértices , uno V i , uno V o , significa entrada y Las salidas , también la conversión de gráficos no dirigidos a uno dirigido no es difícil.
Se puede mostrar fácilmente (como prueba para el lector) que es suficiente buscar la solución para que cada uno de los bloqueos K se coloque en la ruta actual de longitud mínima. Tenga en cuenta que si hay varias rutas de longitud mínima, todas deben considerarse. La razón es que si no pone ninguno de los bloqueos restantes en la ruta de longitud mínima actual, entonces no cambia; por lo tanto, puede poner el primer bloqueo disponible en él inmediatamente durante la búsqueda. Esto acelera incluso una búsqueda de fuerza bruta.
Pero hay más optimizaciones. También puede decidir siempre que coloque el siguiente bloqueo para que se convierta en el PRIMER bloqueo en la ruta actual de longitud mínima, es decir, trabaje de manera que si coloca el bloqueo en el décimo cuadro de la ruta, marque los cuadrados 1 ..9 como "permanentemente abierto" hasta que retrocedas. Esto guarda de nuevo un número exponencial de cuadrados para buscar durante la búsqueda de seguimiento.
Luego, puede aplicar heurísticas para reducir el espacio de búsqueda o reordenar, por ejemplo, primero intente las ubicaciones de bloqueo que aumentan más la longitud de la ruta actual de longitud mínima. Luego, puede ejecutar el algoritmo de seguimiento por una cantidad limitada de tiempo real y elegir la mejor solución encontrada hasta ahora.