algorithm - pathfinding - Resuelve todos los laberintos 4x4 simultáneamente con menos movimientos

pathfinding algorithm (6)

Encontré este problema bastante interesante, donde tenemos un laberinto 4x4 y un robot tratando de llegar a la meta. El problema es que debes encontrar una secuencia de comandos predefinidos que siempre resultarán en que el robot alcance la meta.

Digamos que tenemos un laberinto como este:

x . . . . # # . . # # . . . . g

Este laberinto en particular se puede resolver con, por ejemplo, las secuencias de comandos DDDRRR o RRRDDD , donde R = derecha, L = izquierda, U = arriba y D = abajo (duh).

Ninguna de esas secuencias, sin embargo, resolvería este laberinto:

x . # . . . . . # . . . . . . g

El robot siempre comienza en la parte superior izquierda, el objetivo siempre está en la parte inferior derecha y el laberinto es siempre una matriz 2D 4x4.

Ya he implementado un algoritmo que me dio una secuencia ganadora de 78 comandos. Sé con certeza que al menos existe una solución para 29 comandos (alguien más logró esto).

De hecho, este problema tiene algunos años y, por lo tanto, perdí el algoritmo que usé en ese momento, pero la idea básica fue realizar una búsqueda en todos los laberintos que generé, y elegir siempre la ruta que resulte en la más resuelta. laberintos Esto realmente me consiguió una secuencia que tenía un poco más de 78 de longitud; Reduje algunos comandos a mano que noté eran redundantes.

Sí, la fuerza bruta tomará años como de costumbre.

Si me sirve la memoria, hay menos de 4000 posibles laberintos (es posible que haya un camino entre la parte superior izquierda y la parte inferior derecha).

¡OH! es suficiente que el robot simplemente visite la meta al menos una vez durante la ejecución de los comandos. Es decir, no tiene que estar sentado en la portería después del último comando.

¿Capté el interés de alguien? ¿Cómo debo abordar este problema para una respuesta más eficiente? Gracias por considerar :)

Algo divertido: Pastebin

Es una pieza de Java (muy) apresuradamente preparada. Debería compilarse y ejecutarse :) El programa juega ~ 4000 laberintos al mismo tiempo. El programa toma una entrada (w, a, s, d) para UP, LEFT, DOWN y RIGHT, y luego simula el movimiento, mostrando algunas estadísticas. Lo que puedes ver en la pantalla, si lo intentas, es la cantidad total de obstáculos en cada laberinto en cada posición y la cantidad total de posiciones actuales de cada laberinto. Es difícil de explicar :) Pregúntame si tienes preguntas.

Una vez más ... no me importa el código horrible. Fue escrito en 20 minutos.

Progreso

Obtuve esta idea indirectamente a partir de la respuesta de este usuario (que se eliminó después, por algún motivo), y la modelé con Mooing Duck en un chat. La idea es encontrar una secuencia que resuelva el lado derecho del laberinto. Es decir, una solución que resuelve al menos la mitad de todos los laberintos, y cuando se refleja y se ejecuta de nuevo desde el principio resuelve los laberintos restantes.

Ilustración:

Primero encuentre una secuencia, cuyo primer comando sea CORRECTO, que resuelva, por ejemplo, este laberinto:

0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0

una de tales secuencias es RDDRRRD . La contraparte reflejada de esta secuencia es una tal que

R -> D D -> R L -> U U -> L

Lo que significa RDDRRRD -> DRRDDDR

Ahora, ¿esta secuencia reflejada resuelve el laberinto? No, se atasca. Por lo tanto, no es una secuencia válida incluso para este laberinto. Tenemos que encontrar una secuencia tal que resuelva al menos la mitad de todos los laberintos, y su contraparte reflejada resuelve el resto cuando se ejecuta de nuevo desde el principio.

Después de simplemente forzar bruta todas las permutaciones posibles de R, D y L, obtuve algunas secuencias posibles.

Una de tales secuencias es RRDRRRDRLDRDR

Ahora el siguiente problema es que, después de ejecutar esta secuencia, los laberintos restantes se encuentran en un caos aleatorio. Necesitamos obtener la secuencia más corta (óptima) posible para que todos los laberintos restantes vuelvan a la posición inicial (0, 0) . Esta parte lo hice simplemente a mano (por ahora). Mi respuesta para esto no es de ninguna manera óptima, pero hace que todos los laberintos vuelvan al principio.

Esta secuencia es LDLUULURUUULULL

Después de esto, simplemente ejecutamos la secuencia duplicada, DDRDDDRDURDRD , y hemos resuelto todos los laberintos.

Esta secuencia particular en su totalidad:

RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD - 41 movimientos

Si bien este es un hito prometedor y premiado, aún faltan 12 pasos para llegar a la solución mejor probada . Cualquier idea es muy bienvenida! También, gracias a todos los que me ayudaron hasta ahora :)

La secuencia se encoge.

Todavía no he podido obtener una respuesta mejor programada que una secuencia larga de 58 movimientos. Sin embargo, con el método descrito anteriormente y simplemente puliendo los caracteres a mano, he podido reducir la secuencia para que tenga solo 33 caracteres. Esta secuencia está abajo:

RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR - 33 movimientos

Si bien la secuencia está ahora muy cerca del objetivo 29, todavía estoy buscando una solución programada del mismo calibre. No hay ninguna lógica que utilicé para eliminar caracteres de la secuencia; simplemente eliminé un carácter y comprobé si resuelve todos los laberintos, enjuaga y repite.

Algunas ideas:

Ninguna de las subcadenas RLR, LRL, UDU o DUD puede aparecer en una solución óptima , ya que en cada laberinto dejan al robot en la misma posición (si el primer movimiento está bloqueado por una pared) o un paso en la dirección de la primer movimiento (de lo contrario), que en cada caso es el mismo que el resultado de realizar solo el primer movimiento en la secuencia. Lo mismo ocurre con RRLLRR, LLRRLL, etc. (y probablemente para todos los patrones más largos, aunque no lo he verificado, y producen rendimientos decrecientes en términos de poda de la búsqueda). [EDIT: Esto no es del todo correcto: solo se aplica si ningún robot que aún no haya alcanzado g alcanzaría g en el segundo de los tres movimientos. ¡Difícil!]
En cualquier solución válida, si se intercambian todos los D y R, y se intercambian todos los L y Nosotros, obtendremos otra solución válida, ya que esta solución "volteada" resolverá todos los laberintos que se "voltearon" alrededor de la diagonal principal, que Es solo el conjunto de todos los laberintos. El resultado es que solo debemos considerar soluciones en las que el primer movimiento sea, digamos, R.
Una forma de proceder con la búsqueda A * (o rama y límite, o enumeración completa) es registrar, en cada nodo del árbol de búsqueda, el estado del robot en todos los ~ 4000 laberintos válidos. Pero podemos ahorrar un poco de tiempo y espacio combinando los estados de todos los laberintos que no pudieron haberse distinguido por nuestros movimientos hasta ahora . Podemos hacer esto grabando un tercer estado de celda "desconocido", * . Cuando intentamos hacer un movimiento en una celda * , este estado se divide en 2 subestados: el estado en el que se convierte en una celda vacía (y nuestro movimiento se completa con éxito), y el estado en el que se convierte en una pared (y nosotros permanecer en la misma posición). Si revelar que esta celda es una pared significa que ya no es posible alcanzar la celda objetivo, entonces ese subestado no se genera.

Entonces, por ejemplo, después de intentar el primer movimiento (R), la información de estado completa en el nodo del árbol de búsqueda consiste en los siguientes dos laberintos parciales:

x # * * . x * * * * * * * * * * * * * * * * * * * * * g * * * g

Si luego intentamos un movimiento D, terminamos con:

. # * * . x * * . . * * x * * * * # * * * x * * * * * * * * * * * * * * * * * g * * * g * * * g

Tenga en cuenta que el movimiento desde el estado de la izquierda tuvo que ser exitoso, porque de lo contrario el robot habría sido encuadrado en la celda (1, 1).

Para otro ejemplo, el siguiente laberinto parcial representa 32 laberintos completos diferentes (correspondientes a las 32 formas diferentes en que se podrían resolver las * celdas), cada una de las cuales tiene la misma solución óptima:

x # * * . # * * . # # * . . . g

Si bien aún es posible utilizar la heurística BFS de templatetypedef para A *, el hecho de que cada celda pueda estar ahora en uno de los 3 estados aumenta el número total de distancias precomputadas a 16 * 3 ^ 14 = 76527504, que aún es manejable. Necesitamos representar conjuntos de elementos que pueden asumir 3 estados como sumas de poderes de 3 para formar índices en tablas de búsqueda, y esto no es tan rápido o conveniente como trabajar con elementos de 2 estados, pero no es tan difícil: el único La operación costosa es la división por 3, lo que se puede hacer multiplicando por 0x55555556 y manteniendo los 32 bits superiores del resultado de 64 bits.

No es exactamente una respuesta, pero a otros les puede resultar útil para llegar a una respuesta.

Parece que el mejor enfoque en general es moverse en diagonal. Sin embargo, me encuentro con una serie de situaciones difíciles, que enumero a continuación que parecen hacer tropezar los enfoques que se me ocurren manualmente.

1 0 0 0 1 0 0 0 1 0 0 0 1 0 # Z 1 0 # Z 0 # X # 0 # # X 0 # # X # 0 X 0 # 0 # Z 0 Z # Z 0 Z Z # 0 0 0 # Z Z # 0 Z 0 X 0 0 0 0 1 0 0 0 1 X # 0 1 Z Z # 1 Z Z # 1

Donde: 1 es el comienzo / final. 0 es un lugar vacío, # es un muro, Z es un muro o está vacío y X es los puntos problemáticos, ya sea por quedarse atascado o por la dificultad de alcanzarlos.

Un enfoque que pueda resolver los laberintos anteriores con el menor número de comandos debe estar bastante cerca de resolver cualquier laberinto.

Parece que podrías usar la búsqueda A * aquí, tomando como heurística la heurística máxima de todos los laberintos. Eso se aproxima de manera conservadora a la distancia de la solución y probablemente daría un primer enfoque razonable.

Como todos los laberintos son pequeños, puede crear una heurística perfecta para cada uno ejecutando BFS en sentido inverso desde el final de cada laberinto para calcular la distancia desde cada punto hasta el objetivo de cada laberinto. Si guardó este caché en las tablas de búsqueda, podría tener una heurística por laberinto que le indicara perfectamente el número mínimo de movimientos restantes.

En realidad no lo he intentado, por lo que aún queda por validar experimentalmente, pero creo que sería un gran punto de partida para una solución.

EDITAR Acabo de leer la nota que dice que cada robot debe visitar el objetivo al menos una vez y no necesariamente terminar con el objetivo. En ese caso, modifique la heurística para que sea la distancia máxima de cualquier robot que aún no haya alcanzado el objetivo.

¡Espero que esto ayude!

Rápidamente lancé una implementación juntos (mira here si estás interesado, aunque es un poco complicado). No estoy seguro de si este es un enfoque similar al descrito por @templatetypedef. Básicamente hago lo siguiente:

Genere todos los laberintos y calcule la distancia desde cada celda hasta la celda final (filtre todos los laberintos que tengan áreas inalcanzables, porque son equivalentes a los laberintos que tienen paredes en esos puntos).
Comienza a caminar por todos los laberintos simultáneamente. El puntaje actual es la distancia total hasta la celda final sobre todos los laberintos que aún no han alcanzado la celda final.
Calcule el puntaje para cada una de las cuatro direcciones posibles. Avanza con avidez a la dirección que tenga la mejor puntuación (la más baja).

Este enfoque converge, pero toma 103 pasos. Luego traté de tener una perspectiva más amplia, así que, en lugar de elegir con avidez el mejor paso, elegir con avidez la mejor secuencia de k próximos pasos.

Corrí este enfoque hasta k = 10 , con los siguientes resultados:

k | length | sequence -------------------- 1 | 103 | RDRDRDRDRLDDRRDRURRDLLDDRURURRDDLLLDDRRDRURRUURRRDDDULLLDDDRRRDLLDDRRLURRLLUDRRDDRRRLUUURRRDDDULLDDRDRR 2 | 86 | RDRDRDRDRLDDRRDRURRDLLDDRUURRDRDLLLDDRDRURRUURRDRDDULLLDDDRRDRRLULLDDRDRURRLUURURRDDRD 3 | 79 | RDRDRDRDRLDDRRDRURURDRDLLDDLDRDRRDRURURURRDDDULLLDDRDRRRLULLDDRDRRLURURDRURRDDD 4 | 70 | RDRDRDRDRLDDRRDRUURRDLLDLDDRDRURUURRDRDDLULLLDDRDRRRDLLDDRRRLUURURRDDD 5 | 73 | RDRDRDRDRLLDDRRDRURRURRDDDULLLDDRDRDRUURURRDDRDLULLDDRDRRLUURURRDLLLDDRRR 6 | 70 | RDRDRDRLDRDRDUURRDLLLDDRDRDRURUURRDDULLLDDRDRRRLUUURRRDRLLDDULLDDRDRRR 7 | 64 | RDRDRDRLDDRRDRLLDDRURUURDRDDULLLDDRDRRDRLURURURRDLDULLDDLLDRDRRR 8 | 67 | RDRDRDRDLLDDRRDRURUURRDDULLLDDRDDRUURRDRURRDLLLDULLDDRDRRLUURURRDDD 9 | 64 | RDRDRDRDRLLDDRURRDDRUUURRDDULLLDDRDRDRRLUUURRRDLDULLDDLLDRDRURRD 10 | 58 | RDRDRDRDRLLLDDRURDRDRUUURRDDDLULLLDRDDRRURRDRRLDDUURURRDDD

Por supuesto, este enfoque se vuelve inviable para grandes k . Como el OP establece que el problema se puede resolver con solo 29 movimientos, este enfoque codicioso no parece ser el mejor camino a seguir ...

Tomé la cuerda larga de 41 de la publicación original y traté de minimizarla. Encontré que se pueden quitar 4 caracteres. No mucho, pero creo que vale la pena señalar. Así que a partir de este RRDRRRDRLDRDRLDLUULURUUULULLDDRDDDRDURDRD llegué a este RRDRRDRLDRDRLDLUULRULULLDDRDDDRDURDRD . Pasa cada laberinto generado por el método de @ Vincent.

También verifiqué otros resultados de este hilo, pero no hubo ninguna diferencia significativa.

Usé un poco del código de @ Vincent para generar laberintos.

Aquí hay un enlace a código y ejemplo. http://ideone.com/9OFr5E

Por favor, hágamelo saber si cometí un error en alguna parte.

Usando un algoritmo meta A * y C #, encontré las siguientes secuencias de 32 y 31 caracteres (hasta ahora):

RRDRRDRLDRDLDLULLLDDRDDRDRURRDRD (32 characters) RRDRRDRLDRDLDLULLLDDRDDRDURRDRRD (32 characters) RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 characters)

Yo bifurqué el ideone de Olavi con la secuencia de 31 caracteres para asegurarme de que no cometiera errores.

Con respecto al conteo de laberintos, obtengo 3828 laberintos válidos usando un algoritmo de relleno de inundación.

El código fuente del proyecto C # y el archivo binario compilado (en la carpeta bin / release) en Google Drive .

Puede ingresar una cadena de inicio para la búsqueda A * allí y una longitud máxima de búsqueda. Ha habido algunas optimizaciones de velocidad en el código, pero todavía hay lugar para más. Por ejemplo, para cada expansión, crea 4 instancias de la clase de Candidate , creando nuevos laberintos que ejecutan cada movimiento del candidato anterior, seguidos de las 4 direcciones diferentes (izquierda, derecha, arriba, abajo). Con un método Candidate.Clone() , el rendimiento podría mejorarse mucho, el generador de perfiles muestra el hotspot actual exactamente allí. Además, hasta ahora no hay subprocesos múltiples y el programa usa más y más memoria para la lista visitada (alrededor de 2 GB después de 10 minutos en mi PC). Tenga en cuenta que ejecutar el programa dentro del IDE lo ralentiza bastante incluso en el modo de lanzamiento, por lo que es mejor iniciarlo afuera.

El meta algoritmo básico que conduce a las secuencias anteriores es:

A * busca una cadena conocida de longitud N con longitud máxima M, eliminando cada vez más caracteres del final, por ejemplo
Una búsqueda * para RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD (32 caracteres), M = 33
Una búsqueda * para RRDRRDRLDRDLDLULLLDDRDDRDRURRRD (31 caracteres), M = 33
Una búsqueda * para RRDRRDRLDRDLDLULLLDDRDDRDRURRR (30 caracteres), M = 33
Una búsqueda * para RRDRRDRLDRDLDLULLLDDRDDRDRURR (29 caracteres), M = 33
...
Una vez que se encuentra una cadena más corta que N, use esto como la nueva longitud máxima para la búsqueda A * para hacerlo más rápido y tener menos memoria.

Las combinaciones reales que probé se pueden ver en el código fuente, consulte el fragmento de código a continuación. Los tiempos son de una versión anterior no optimizada y la versión actual debería ser aproximadamente 6 veces más rápida.

//// 33 char solution //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDDR", 33); // 33 chars, 00:00:00.0032911 Finished, 1 solution, best 33, visitedList length 0 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRDD", 33); // 32 chars, 00:00:00.0308543 Finished, 1 solution, best 33, visitedList length 3 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRRD", 33); // 31 chars, 00:00:00.0871429 Finished, 2 solutions, best 33, visitedList length 14 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURRR", 33); // 30 chars, 00:00:00.2536057 Finished, 2 solutions, best 33, visitedList length 49 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 33); // 29 chars, 00:00:01.0540762 Finished, 8 solutions, best 32, visitedList length 205 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 33); // 28 chars, 00:00:03.8993877 Finished, 7 solutions, best 32, visitedList length 771 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 33); // 27 chars, 00:00:10.4225150 Finished, 7 solutions, best 32, visitedList length 2069 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 33); // 26 chars, 00:00:24.2552908 Finished, 7 solutions, best 32 visitedList length 4484 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 33); // 25 chars, 00:01:44.3295165 Finished, 14 solutions, best 32, visitedList length 16600 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 33); // 24 chars, 00:16:18.6666045 Finished, 14 solutions, best 32, visitedList length 77106 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRURR", 32); // 29 chars, 00:00:00.3134699 Finished, 1 solution, best 32, visitedList length 66 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRUR", 32); // 28 chars, 00:00:01.1053798 Finished, 1 solution, best 32, visitedList length 238 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDRU", 32); // 27 chars, 00:00:03.5172143 Finished, 1 solution, best 32, visitedList length 730 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRDR", 32); // 26 chars, 00:00:07.1336796 Finished, 1 solution, best 32, visitedList length 1413 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDRD", 32); // 25 chars, 00:00:26.4906874 Finished, 2 solutions, best 32, visitedList length 5084 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDDR", 32); // 24 chars, 00:02:52.8134463 Finished, 2 solutions, best 32, visitedList length 24623 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 32); // 23 chars, cancelled after 6 seconds, finds RRDRRDRLDRDLDLULLLDDRDDDURDRRDR (31 chars) //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRDD", 31); // 23 chars, 00:01:58.4861802 Finished, 1 solution, best 31, visitedList length 18835 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDRD", 30); // 22 chars, 00:00:34.6602434 Finished, 0 solution, best distance 44, visitedList length 21084 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDDR", 30); // 21 chars, 00:04:32.2439241 Finished, 0 solution, best distance 44, visitedList length 78500 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLDD", 30); // 20 chars, cancelled after 10 minutes, found no solution, best distance 44 //var aStarSearch = new AStarSearch("RRDRRDRLDRDLDLULLLD", 30); // 19 chars, cancelled after 10 minutes, found no solution, best distance 44 //var aStarSearch = new AStarSearch("R", 29); // Complete search, would take waaay too long and consume much memory