Pasos que garantizan salir de un laberinto.

14

Dado un laberinto bidimensional donde puede dar 4 comandos "mover hacia arriba / abajo / derecha / izquierda". Conociendo el laberinto pero no dónde está la persona, ¿cómo encontrar la secuencia mínima de comandos que garantiza salir del laberinto? Estoy buscando una secuencia única de comandos que funcionen sin importar en qué parte del laberinto comiencen.

Suponga que si a nuestro compañero se le da el comando "moverse a la derecha" cuando hay un muro a la derecha, simplemente se quedará donde está.

En otras palabras, tenemos un laberinto y debemos elegir una secuencia de comandos. Luego, nuestro compañero será ubicado en algún lugar del laberinto y seguirá la secuencia de comandos que hemos elegido de antemano. Queremos que esta secuencia garantice que nuestro compañero se escape, sin importar dónde se ubicó inicialmente. Tenga en cuenta que los comandos permitidos no tienen ninguna declaración condicional, por lo que no pueden seguir una secuencia diferente dependiendo de su compañero.

¿Existe un algoritmo de tiempo polinómico para construir tal secuencia, dada una descripción del laberinto?

Yuval Filmus menciona que este es un caso especial de un problema de palabras sincronizadas , y podría estar relacionado con secuencias transversales universales. También encontré un artículo que parece relevante:

El problema simultáneo de resolución de laberintos . Stefan Funke, André Nusser, Sabine Storandt. AAAI 2017.

Desafortunadamente para los gráficos generales, esto parece ser un problema no resuelto, pero me pregunto si podría haber un buen algoritmo para este caso específico. Se me ocurrió un enfoque candidato: etiquete cada posición con el número de pasos mínimos que requiere para salir y realice un seguimiento de cada agente en el laberinto. Es posible hacer una búsqueda A * de esta manera.

seilgu
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Lagarto discreto
La estrategia de Eppstein para autómatas monótonos es agrupar estados para que, en lugar de buscar una ruta en el conjunto completo de estados de potencia, busque una ruta en un gráfico con solo muchos vértices polinómicos. La generalización más natural de intervalos a 2D que se me ocurre es el casco convexo, pero desafortunadamente no está claro que su número crezca polinomialmente .
Peter Taylor

Respuestas:

-1

UN

vonbrand
fuente
No puede codificar el seguimiento de la pared como una secuencia fija de direcciones cardinales. Las opciones dependen de los muros que te rodean, lo que la pregunta no permite específicamente.
Curtis F
Si conoce el camino más corto, puede codificarlo como "moverse hacia la izquierda, luego en línea recta y luego ...". Si no conoce el camino más corto, no puede dar esas instrucciones para la salida más corta. Si no conoce un camino, no puede dar instrucciones para salir.
vonbrand