Algoritmo para resolver laberintos

Un algoritmo para resolver laberintos es un método automatizado para resolver un laberinto . Los algoritmos de ratón aleatorio, seguidor de pared, Pledge, Tarry y Trémaux están diseñados para ser utilizados dentro del laberinto por un viajero sin conocimiento previo del mismo, mientras que los algoritmos de relleno de callejones sin salida y de camino más corto están diseñados para ser utilizados por una persona o un programa informático que puede ver todo el laberinto a la vez.

Los laberintos sin bucles se conocen como laberintos "simplemente conectados" o "perfectos", y son equivalentes a un árbol en la teoría de grafos. Los algoritmos para resolver laberintos están estrechamente relacionados con la teoría de grafos . Intuitivamente, si se estiraran y alargaran los caminos del laberinto de la manera adecuada, el resultado podría asemejarse a un árbol. ^{[ 1 ]}

Este método sencillo puede ser implementado por un robot poco inteligente o incluso por un ratón, ya que no requiere memoria. El robot avanza siguiendo el camino actual hasta llegar a una bifurcación y, a continuación, toma una decisión aleatoria sobre la siguiente dirección a seguir. Si bien este método siempre encontraría la solución correcta , el algoritmo puede ser muy lento. ^{[ 2 ]}

Una regla eficaz para recorrer laberintos es la regla de la mano en la pared , también conocida como regla de la mano izquierda o regla de la mano derecha . Si el laberinto es simplemente conexo , es decir, todas sus paredes están conectadas entre sí o al límite exterior del laberinto, entonces al mantener una mano en contacto con una pared del laberinto, el solucionador tiene la garantía de no perderse y llegará a una salida diferente si la hay; de lo contrario, el algoritmo regresará a la entrada después de haber recorrido cada corredor junto a esa sección de paredes conectadas al menos una vez. El algoritmo es un recorrido de árbol en orden en profundidad .

Otra perspectiva sobre por qué funciona el seguimiento de paredes es topológica. Si las paredes están conectadas, pueden deformarse formando un bucle o círculo. ^{[ 3 ]} Entonces, el seguimiento de paredes se reduce a caminar en círculo desde el principio hasta el final. Para profundizar en esta idea, observe que al agrupar los componentes conectados de las paredes del laberinto, los límites entre estos son precisamente las soluciones, incluso si hay más de una.

Si el laberinto no es simplemente conexo (es decir, si los puntos de inicio o final están en el centro de la estructura rodeados de bucles de paso, o si los caminos se cruzan por encima y por debajo unos de otros y dichas partes del camino de la solución están rodeadas de bucles de paso), este método no necesariamente alcanzará el objetivo.

Otra preocupación es que se debe tener cuidado al comenzar a seguir las paredes en la entrada del laberinto. Si el laberinto no es simplemente conexo y se comienza a seguir las paredes en un punto arbitrario dentro del laberinto, se podría quedar atrapado en una pared separada que se repite sobre sí misma y no tiene entradas ni salidas. Si se comienza a seguir las paredes tarde, intente marcar la posición donde comenzó. Dado que seguir las paredes siempre lo llevará de regreso al punto de partida, si se encuentra con su punto de partida por segunda vez, puede concluir que el laberinto no es simplemente conexo y debe cambiar a una pared alternativa que aún no haya seguido. Consulte el Algoritmo de Compromiso , a continuación, para una metodología alternativa.

El seguimiento de paredes se puede realizar en laberintos 3D o de dimensiones superiores si sus pasajes de dimensiones superiores se pueden proyectar en el plano 2D de forma determinista. Por ejemplo, si en un laberinto 3D se asume que los pasajes "hacia arriba" conducen al noroeste y los pasajes "hacia abajo" al sureste, entonces se pueden aplicar las reglas estándar de seguimiento de paredes. Sin embargo, a diferencia de lo que ocurre en 2D, esto requiere conocer la orientación actual para determinar qué dirección es la primera a la izquierda o a la derecha.

Aquí se puede encontrar una simulación del funcionamiento de este algoritmo .

Los laberintos disjuntos (donde las paredes no están conectadas al límite exterior/el límite no está cerrado) se pueden resolver con el método del seguidor de pared, siempre que la entrada y la salida del laberinto estén en las paredes exteriores. Sin embargo, si el solucionador comienza dentro del laberinto, podría estar en una sección disjunta de la salida, y los seguidores de pared irán continuamente alrededor de su anillo. El algoritmo Pledge (llamado así en honor a Jon Pledge de Exeter) puede resolver este problema. ^{[ 4 ] [ 5 ]}

El algoritmo Pledge, diseñado para sortear obstáculos, requiere una dirección elegida arbitrariamente, que será la preferida. Al encontrar un obstáculo, una mano (por ejemplo, la derecha) se mantiene junto a él mientras se cuentan los ángulos girados (un giro en el sentido de las agujas del reloj es positivo, un giro en sentido contrario es negativo). Cuando el algoritmo vuelve a mirar hacia la dirección preferida original y la suma angular de los giros realizados es cero, el algoritmo abandona el obstáculo y continúa moviéndose en su dirección original.

La mano se retira de la pared solo cuando tanto la "suma de giros realizados" como la "dirección actual" son cero. Esto permite que el algoritmo evite trampas con forma de letra "G" mayúscula. Suponiendo que el algoritmo gira a la izquierda en la primera pared, se da un giro completo de 360 ​​grados por las paredes. Un algoritmo que solo registra la "dirección actual" entra en un bucle infinito, ya que deja la pared inferior derecha dirigiéndose a la izquierda y vuelve a encontrarse con la sección curva del lado izquierdo. El algoritmo Pledge no deja la pared más a la derecha porque la "suma de giros realizados" no es cero en ese punto (nótese que 360 ​​grados no es igual a 0 grados ). Sigue la pared hasta el final, dejándola dirigiéndose a la izquierda fuera y justo debajo de la forma de la letra.

Este algoritmo permite a una persona con una brújula encontrar el camino desde cualquier punto dentro de un laberinto bidimensional finito hasta una salida exterior, independientemente de la posición inicial del usuario. Sin embargo, este algoritmo no funciona en sentido inverso, es decir, encontrar el camino desde una entrada exterior del laberinto hasta un destino final dentro del mismo.

El algoritmo de Trémaux, inventado por Charles Pierre Trémaux , ^{[ 6 ]} es un método eficiente para encontrar la salida de un laberinto que requiere dibujar líneas en el suelo para marcar un camino, y está garantizado que funciona para todos los laberintos que tienen pasajes bien definidos, ^{[ 7 ]} pero no está garantizado que encuentre la ruta más corta.

La entrada a un pasaje puede estar sin visitar, marcada una vez o marcada dos veces. Marcar una entrada no es lo mismo que marcar una bifurcación o un pasaje, ya que una bifurcación puede tener varias entradas, mientras que un pasaje tiene una entrada en ambos extremos. Los callejones sin salida pueden considerarse como bifurcaciones con una sola entrada.

El algoritmo funciona según las siguientes reglas:

• Al pasar por una entrada, ya sea para entrar o salir de un cruce, la entrada está señalizada.
• Al llegar a una intersección, la primera regla aplicable determinará la entrada por la que se debe salir:
  1. Si solo está señalizada la entrada por la que se acaba de pasar, se elige al azar una entrada sin señalizar, si la hay. Esta regla también se aplica si no hay entradas señalizadas.
  2. Se selecciona la entrada por la que se acaba de pasar si hay otras entradas marcadas, a menos que esté marcada dos veces.
  3. Se elige la entrada con la menor cantidad de puntos (cero si es posible, de lo contrario uno).

La regla de "dar la vuelta y regresar" transforma cualquier laberinto con bucles en uno simplemente conectado; cuando se encuentra un camino que cierra un bucle, se considera un callejón sin salida y se regresa. Sin esta regla, es posible bloquear el acceso a partes aún inexploradas del laberinto si, en lugar de regresar, se elige otra entrada al azar.

Al llegar a la salida, las entradas marcadas una sola vez indicarán el camino de regreso al punto de partida. Si no hay salida, este método llevará de vuelta al punto de partida, donde todas las entradas están marcadas dos veces. En este caso, cada pasaje se recorre dos veces, una en cada dirección. El recorrido resultante se denomina doble trazado bidireccional. ^{[ 8 ]}

Esencialmente, este algoritmo, que fue descubierto en el siglo XIX, se ha utilizado aproximadamente cien años después como búsqueda en profundidad . ^{[ 9 ] [ 10 ]}

El algoritmo de Tarry, publicado por Gaston Tarry en 1895 en Le problème des labyrinthes , es un método para recorrer un laberinto o un grafo no dirigido conexo sin conocimiento previo de su diseño. Es similar al algoritmo de Trémaux en que utiliza el marcado del laberinto para registrar el progreso de la exploración. El algoritmo garantiza el recorrido completo y la terminación; cada arista se recorre como máximo dos veces, una en cada dirección. Se puede expresar como una sola regla, descrita por MacTutor como «particularmente adecuada para la implementación informática»: No salga de una intersección por donde entró hasta que se hayan explorado todas las demás salidas. Actualmente se considera un procedimiento temprano similar a la búsqueda en profundidad . ^{[ 11 ] [ 9 ] [ 12 ]}

El método de relleno de callejones muertos es un algoritmo para resolver laberintos que rellena todos los callejones muertos, dejando sin rellenar solo los caminos correctos. Se puede utilizar para resolver laberintos en papel o con un programa informático, pero no es útil para una persona dentro de un laberinto desconocido, ya que este método examina todo el laberinto a la vez. El método consiste en:

1. encuentra todos los callejones sin salida en el laberinto y luego
2. "Rellena" el camino desde cada callejón sin salida hasta llegar al primer cruce.

Tenga en cuenta que algunos pasajes no se convertirán en pasajes sin salida hasta que se eliminen otros pasajes sin salida. A la derecha puede ver un vídeo que muestra cómo se rellenan los pasajes sin salida.

El relleno de callejones sin salida no puede cortar accidentalmente el inicio del final, ya que cada paso del proceso preserva la topología del laberinto. Además, el proceso no se detendrá demasiado pronto, puesto que el resultado no puede contener callejones sin salida. Por lo tanto, si el relleno de callejones sin salida se realiza en un laberinto perfecto (sin bucles), solo quedará la solución. Si se realiza en un laberinto parcialmente trenzado (con algunos bucles), quedarán todas las soluciones posibles, pero nada más.

Si se dispone de una visión omnisciente del laberinto, un algoritmo recursivo sencillo puede indicar cómo llegar al final. Al algoritmo se le proporcionarán los valores iniciales de X e Y. Si estos valores no coinciden con una pared, el método se llamará a sí mismo con todos los valores adyacentes, asegurándose de no haberlos utilizado previamente. Si los valores coinciden con los de la ubicación final, guardará todas las instancias anteriores del método como la ruta correcta.

En efecto, se trata de una búsqueda en profundidad expresada en términos de puntos de la cuadrícula. La vista omnisciente evita entrar en bucles por memorización. Aquí hay un ejemplo de código en Java :

boolean [][] laberinto = nuevo boolean [ ancho ][ alto ] ; // El laberinto boolean [][] estuvoAquí = nuevo boolean [ ancho ][ alto ] ; boolean [][] caminoCorrecto = nuevo boolean [ ancho ][ alto ] ; // La solución del laberinto int inicioX , inicioY ; // Valores iniciales de X e Y del laberinto int finX , finY ; // Valores finales de X e Y del laberintopublic void solveMaze () { laberinto = generarLaberinto (); // Crear laberinto (false = camino, true = pared)// La asignación a false a continuación es redundante ya que Java asigna los elementos de la matriz a false por defecto, pero se incluye porque otros lenguajes pueden no comportarse de la misma manera. for ( int row = 0 ; row < maze . length ; row ++ ) // Establece las matrices booleanas a valores predeterminados for ( int col = 0 ; col < maze [ row ] . length ; col ++ ){ wasHere [ row ][ col ] = false ; correctPath [ row ][ col ] = false ; } boolean b = recursiveSolve ( startX , startY ); // Te dejará con una matriz booleana (correctPath) // con la ruta indicada por valores true. // Si b es false, no hay solución para el laberinto } public boolean recursiveSolve ( int x , int y ) { if ( x == endX && y == endY ) return true ; // Si llegaste al final if ( maze [ x ][ y ] || wasHere [ x ][ y ] ) return false ; // Si estás en una pared o ya estabas aquí wasHere [ x ][ y ] = true ; if ( x != 0 ) // Comprueba si no estás en el borde izquierdo if ( recursiveSolve ( x - 1 , y )) { // Llama al método uno a la izquierda correctPath [ x ][ y ] = true ; // Establece ese valor de ruta en verdadero; return true ; } if ( x != width -1 ) // Comprueba si no está en el borde derecho if ( recursiveSolve ( x + 1 , y )) { // Llama al método uno a la derecha correctPath [ x ][ y ] = true ; return true ; } if ( y != 0 ) // Comprueba si no está en el borde superior if ( recursiveSolve ( x , y - 1 )) { // Llama al método uno hacia arriba correctPath [ x ][ y ] = true ; return true ; } if ( y != height - 1 ) // Comprueba si no está en el borde inferior if ( recursiveSolve ( x , y + 1 )) { // Llama al método uno hacia abajo correctPath [ x ][ y ] = true ; return true ; } return false ; }

El algoritmo de enrutamiento de laberintos ^{[ 13 ]} es un método de bajo consumo de recursos para encontrar la ruta entre dos ubicaciones cualesquiera del laberinto. El algoritmo se propuso inicialmente para el dominio de los multiprocesadores en chip (CMP) y garantiza su funcionamiento en cualquier laberinto basado en cuadrícula. Además de encontrar rutas entre dos ubicaciones de la cuadrícula (laberinto), el algoritmo puede detectar cuando no existe una ruta entre el origen y el destino. Asimismo, el algoritmo está diseñado para ser utilizado por un usuario interno sin conocimiento previo del laberinto, con una complejidad de memoria fija independientemente del tamaño del laberinto; requiere un total de 4 variables para encontrar la ruta y detectar las ubicaciones inaccesibles. Sin embargo, el algoritmo no encuentra la ruta más corta.

El algoritmo de enrutamiento en laberintos utiliza el concepto de distancia de Manhattan (DM) y se basa en la propiedad de las cuadrículas de que la DM aumenta o disminuye exactamente en 1 al moverse de una ubicación a cualquier conjunto de 4 ubicaciones vecinas. A continuación se muestra el pseudocódigo sin la capacidad de detectar ubicaciones inaccesibles.

Punto src , dst ; // Coordenadas de origen y destino // cur también indica las coordenadas de la ubicación actual int MD_best = MD ( src , dst ); // Almacena la MD más cercana que hemos tenido a dst // Una ruta productiva es la que hace que nuestra MD a dst sea menor while (cur != dst) { if (existe una ruta productiva ) { Tomar la ruta productiva ; } else { MD_best = MD ( cur , dst ) ; Imaginar una línea entre cur y dst ; Tomar la primera ruta a la izquierda / derecha de la línea ; // La selección izquierda / derecha afecta la siguiente regla de la mano while ( MD ( cur , dst ) ! = MD_best || no existe una ruta productiva ) { Seguir la regla de la mano derecha / izquierda ; // Lo opuesto al lado seleccionado de la línea } }

Cuando un laberinto tiene múltiples soluciones, quien lo resuelve puede querer encontrar el camino más corto desde el inicio hasta el final. Existen varios algoritmos para encontrar caminos más cortos, la mayoría provenientes de la teoría de grafos . Uno de estos algoritmos encuentra el camino más corto mediante una búsqueda en anchura , mientras que otro, el algoritmo A* , utiliza una técnica heurística . El algoritmo de búsqueda en anchura utiliza una cola para visitar celdas en orden creciente de distancia desde el inicio hasta llegar al final. Cada celda visitada debe mantener un registro de su distancia desde el inicio o qué celda adyacente más cercana al inicio provocó que se agregara a la cola. Cuando se encuentra la ubicación final, se sigue el camino de celdas hacia atrás hasta el inicio, que es el camino más corto. La búsqueda en anchura en su forma más simple tiene sus limitaciones, como encontrar el camino más corto en grafos ponderados.

La exploración colectiva se refiere a la exploración de un entorno desconocido por múltiples agentes móviles que se mueven a la misma velocidad. Este modelo se introdujo para estudiar la paralelización de la resolución de laberintos, ^{[ 14 ]} especialmente en el caso de árboles . El estudio depende del modelo de comunicación entre los agentes. En el modelo de comunicación centralizado, los agentes pueden comunicarse entre sí en todo momento. En el modelo de comunicación distribuido , los agentes solo pueden comunicarse leyendo y escribiendo en las paredes del laberinto. Para árboles con${\displaystyle n}$nodos y profundidad${\displaystyle D}$, con${\displaystyle k}$robots, el mejor algoritmo actual está en${\displaystyle O\left({\frac {n}{k}}+kD\right)}$en el modelo de comunicación centralizado y en${\displaystyle O\left({\frac {n}{\log k}}+D\right)}$en el modelo de comunicación distribuida. ^{[ 14 ]}

• Laberinto
• Algoritmo de generación de laberintos

• Piensa en el laberinto: algoritmos para resolver laberintos (detalles sobre estos y otros algoritmos para resolver laberintos)
• MazeBlog: Resolviendo laberintos mediante análisis de imágenes. Archivado el 20 de septiembre de 2015 en Wayback Machine.
• Vídeo: Simulación de resolución de laberintos
• Simon Ayrinhac, La corriente eléctrica resuelve laberintos , © 2014 IOP Publishing Ltd.