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.
fuente
Respuestas:
fuente