Un algoritmo de resolución de laberintos es un método automatizado para resolver un laberinto . Los algoritmos de ratón aleatorio, seguidor de pared, Pledge 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 llenado de callejones sin salida y de camino más corto están diseñados para ser utilizados por una persona o programa informático que puede ver todo el laberinto a la vez.
Los laberintos que no contienen bucles se conocen como laberintos "simplemente conectados" o "perfectos" y equivalen a un árbol en teoría de grafos. Los algoritmos de resolución de laberintos están estrechamente relacionados con la teoría de grafos . Intuitivamente, si uno estirara y estirara los caminos en el laberinto de la manera adecuada, el resultado podría parecerse a un árbol. [1]
Este método simple puede ser implementado por un robot muy poco inteligente o quizás por un mouse, porque no requiere memoria. El robot continúa siguiendo el pasaje actual hasta llegar a un cruce y luego toma una decisión aleatoria sobre la siguiente dirección a seguir. Aunque un método de este tipo siempre encontraría la solución correcta , el algoritmo puede ser muy lento. [2]
Una regla eficaz para atravesar 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 está simplemente conectado , 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, se garantiza que el solucionador no se perderá y llegará a una salida diferente. si hay uno; de lo contrario, el algoritmo regresará a la entrada después de haber atravesado cada corredor al lado de esa sección de paredes conectada al menos una vez. El algoritmo es un recorrido de árbol en orden en profundidad .
Otra perspectiva de por qué funciona el seguimiento de muros es topológica. Si las paredes están conectadas, es posible que se deformen formando un bucle o un círculo. [3] Luego, seguir la pared se reduce a caminar alrededor de un círculo de principio a fin. Para promover esta idea, observe que al agrupar componentes conectados de las paredes del laberinto, los límites entre ellos son precisamente las soluciones, incluso si hay más de una solución.
Si el laberinto no está simplemente conectado (es decir, si los puntos inicial o final están en el centro de la estructura rodeados por bucles de paso, o los caminos se cruzan entre sí y dichas partes del camino de la solución están rodeadas por bucles de paso), este método no necesariamente alcanzará la meta.
Otra preocupación es que se debe tener cuidado al comenzar a seguir la pared en la entrada del laberinto. Si el laberinto no está simplemente conectado y uno comienza a seguir la pared en un punto arbitrario dentro del laberinto, uno podría encontrarse atrapado a lo largo de una pared separada que gira sobre sí misma y no contiene entradas ni salidas. En caso de que el seguimiento de la pared comience tarde, intente marcar la posición en la que comenzó el seguimiento de la pared. Debido a que seguir la pared siempre te llevará de regreso al punto de partida, si te encuentras con tu punto de partida por segunda vez, puedes concluir que el laberinto no está simplemente conectado y debes cambiar a una pared alternativa que aún no hayas seguido. Consulte el Algoritmo de compromiso , a continuación, para conocer 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 manera determinista. Por ejemplo, si en un laberinto 3D se puede suponer que los pasajes "arriba" conducen al noroeste y que los pasajes "abajo" conducen al sureste, entonces se pueden aplicar las reglas estándar de seguimiento de paredes. Sin embargo, a diferencia de 2D, esto requiere que se conozca la orientación actual para determinar qué dirección es la primera a la izquierda o a la derecha.
Los laberintos separados (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 del laberinto. Sin embargo, si el solucionador comienza dentro del laberinto, es posible que esté en una sección separada de la salida, y los seguidores de la pared seguirán continuamente su anillo. El algoritmo Pledge (que lleva el nombre de John Pledge de Exeter) puede resolver este problema. [4] [5]
El algoritmo Pledge, diseñado para sortear obstáculos, requiere una dirección elegida arbitrariamente hacia la cual ir, que será preferencial. Cuando se encuentra un obstáculo, se mantiene una mano (digamos la mano derecha) a lo largo del obstáculo mientras se cuentan los ángulos girados (el giro en el sentido de las agujas del reloj es positivo, el giro en el sentido contrario a las agujas del reloj es negativo). Cuando el solucionador vuelve a mirar en la dirección preferencial original y la suma angular de los giros realizados es 0, el solucionador abandona el obstáculo y continúa moviéndose en su dirección original.
La mano se retira de la pared sólo cuando tanto la "suma de vueltas realizadas" como el "rumbo actual" están en 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, las paredes giran 360 grados completos. Un algoritmo que solo realiza un seguimiento del "rumbo actual" conduce a un bucle infinito cuando sale de la pared inferior derecha en dirección a la izquierda y corre hacia la sección curva en el lado izquierdo nuevamente. El algoritmo Pledge no abandona la pared más a la derecha debido a que la "suma de giros realizados" no es cero en ese punto (tenga en cuenta que 360 grados no es igual a 0 grados ). Sigue la pared por todos lados, finalmente dejándola hacia la izquierda afuera 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 interior hasta una salida exterior de cualquier laberinto bidimensional finito, independientemente de la posición inicial del solucionador. Sin embargo, este algoritmo no funcionará al hacer lo contrario, es decir, encontrar el camino desde una entrada en el exterior de un laberinto hasta algún objetivo final dentro de él.
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 se garantiza encontrar la ruta más corta.
La entrada de un pasaje puede no ser visitada, estar marcada una vez o dos veces. Tenga en cuenta que marcar una entrada no es lo mismo que marcar un cruce o un pasaje, porque un cruce puede tener varias entradas y un pasaje tiene una entrada en ambos extremos. Los callejones sin salida se pueden considerar como cruces con una entrada (imagine que hay una habitación en cada callejón sin salida).
El algoritmo funciona de acuerdo con las siguientes reglas:
La regla de "dar la vuelta y regresar" transforma efectivamente cualquier laberinto con bucles en uno simplemente conectado; Siempre que encontramos un camino que cerraría un bucle, lo tratamos como un callejón sin salida y regresamos. Sin esta regla, es posible cortar el acceso a partes aún inexploradas de un laberinto si, en lugar de regresar, elegimos arbitrariamente otra entrada.
Cuando finalmente llegues a la solución, las entradas marcadas exactamente una vez te indicarán el camino de regreso al inicio. Si no hay salida, este método te llevará de regreso al inicio donde todas las entradas están marcadas dos veces. En este caso, se recorre cada pasaje exactamente dos veces, una en cada dirección. El recorrido resultante se denomina doble trazado bidireccional. [8]
Básicamente, este algoritmo, que fue descubierto en el siglo XIX, se ha utilizado unos cien años después como búsqueda en profundidad . [9] [10]
El llenado de callejones sin salida es un algoritmo para resolver laberintos que llena todos los callejones sin salida, dejando solo los caminos correctos sin completar. Puede usarse para resolver laberintos en papel o con un programa de computadora, pero no es útil para una persona dentro de un laberinto desconocido ya que este método analiza todo el laberinto a la vez. El método es
Tenga en cuenta que algunos pasajes no se convertirán en partes de pasajes sin salida hasta que se eliminen primero otros callejones sin salida. A la derecha se puede ver un vídeo de la acción de rellenar un callejón sin salida.
El llenado sin salida no puede "cortar" accidentalmente el principio del final, ya que cada paso del proceso preserva la topología del laberinto. Además, el proceso no se detendrá "demasiado pronto", ya que el resultado no puede contener callejones sin salida. Por lo tanto, si el llenado sin salida se realiza en un laberinto perfecto (laberinto sin bucles), entonces sólo quedará la solución. Si se hace en un laberinto parcialmente trenzado (laberinto con algunos bucles), entonces quedarán todas las soluciones posibles, pero nada más. [1]
Si se le da una visión omnisciente del laberinto, un algoritmo recursivo simple puede indicarle cómo llegar al final. Al algoritmo se le dará un valor inicial de X e Y. Si los valores X e Y no están en una pared, el método se llamará a sí mismo con todos los valores X e Y adyacentes, asegurándose de que no haya usado esos valores X e Y antes. Si los valores X e Y son los de la ubicación final, guardará todas las instancias anteriores del método como la ruta correcta.
De hecho, se trata de una búsqueda en profundidad expresada en términos de puntos de cuadrícula. La vista omnisciente impide entrar en bucles por memorización. Aquí hay un código de muestra en Java :
booleano [][] laberinto = nuevo booleano [ ancho ] [ alto ] ; // El laberinto booleano [][] wasHere = new boolean [ ancho ][ alto ] ; booleano [][] rutacorrecta = nuevo booleano [ ancho ][ alto ] ; // La solución al laberinto int startX , startY ; // Valores iniciales X e Y del laberinto int endX , endY ; // Finalizando los valores X e Y del laberinto public void solveMaze () { laberinto = generarMaze (); // Crear laberinto (falso = camino, verdadero = pared) // La siguiente asignación a false es redundante ya que Java asigna elementos de matriz a false de forma predeterminada para ( int fila = 0 ; fila < maze . length ; fila ++ ) // Establece matrices booleanas a valores predeterminados para ( int col = 0 ; col < laberinto [ fila ] longitud ; columna ++ ){ estaba aquí [ fila ] [ col ] = falso ; rutacorrecta [ fila ] [ columna ] = falso ; } booleano b = recursiveSolve ( inicioX , inicioY ); // Te dejará con una matriz booleana (correctPath) // con la ruta indicada por valores verdaderos. // Si b es falso, 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 estuviste aquí wasHere [ x ][ y ] = true ; if ( x != 0 ) // Comprueba si no está en el borde izquierdo if ( recursiveSolve ( x - 1 , y )) { // Recupera el método uno a la izquierda correctPath [ x ][ y ] = true ; // Establece el valor de esa ruta en verdadero; devolver verdadero ; } if ( x != ancho - 1 ) // Comprueba si no está en el borde derecho if ( recursiveSolve ( x + 1 , y )) { // Recupera el método uno a la derecha rutacorrecta [ x ][ y ] = true ; devolver verdadero ; } if ( y != 0 ) // Comprueba si no está en el borde superior if ( recursiveSolve ( x , y - 1 )) { // Recupera el método uno hasta correctPath [ x ][ y ] = true ; devolver verdadero ; } if ( y != height - 1 ) // Comprueba si no está en el borde inferior if ( recursiveSolve ( x , y + 1 )) { // Recupera el método uno hacia abajo correctPath [ x ][ y ] = true ; devolver verdadero ; } falso retorno ; } El algoritmo de ruta del laberinto [11] es un método de bajo costo para encontrar el camino entre dos ubicaciones cualesquiera del laberinto. El algoritmo se propuso inicialmente para el dominio de multiprocesadores de chips (CMP) y garantiza que funcionará en cualquier laberinto basado en cuadrícula. Además de encontrar caminos entre dos ubicaciones de la cuadrícula (laberinto), el algoritmo puede detectar cuando no hay un camino entre el origen y el destino. Además, el algoritmo debe ser utilizado por un viajero interno sin conocimiento previo del laberinto con una complejidad de memoria fija, independientemente del tamaño del laberinto; requiriendo 4 variables en total para encontrar el camino y detectar las ubicaciones inalcanzables. Sin embargo, el algoritmo no consiste en encontrar el camino más corto.
El algoritmo de enrutamiento de laberinto utiliza la noción de distancia de Manhattan (MD) y se basa en la propiedad de las cuadrículas de que la MD incrementa/disminuye exactamente en 1 cuando se mueve de una ubicación a 4 ubicaciones vecinas cualesquiera. Aquí está el pseudocódigo sin la capacidad de detectar ubicaciones inalcanzables.
Punto origen , horario de verano ; // Coordenadas de origen y destino // cur también indica las coordenadas de la ubicación actual int MD_best = MD ( src , dst ); // Almacena el MD más cercano que hemos tenido a dst // Una ruta productiva es la que hace que nuestro MD a dst sea más pequeño while ( cur != dst ) { if ( existe una ruta productiva ) { Tomar la ruta productiva ; } else { MD_best = MD ( cur , horario de verano ); Imagine una línea entre cur y dst ; Tome el primer camino 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 ) { Sigue la regla de la mano derecha / izquierda ; // El opuesto del lado seleccionado de la línea } } 
Cuando un laberinto tiene múltiples soluciones, es posible que el solucionador desee encontrar el camino más corto de principio a fin. Existen varios algoritmos para encontrar caminos más cortos, la mayoría de ellos provenientes de la teoría de grafos . Uno de estos algoritmos encuentra el camino más corto implementando una búsqueda en amplitud , mientras que otro, el algoritmo A* , utiliza una técnica heurística . El algoritmo de búsqueda en amplitud utiliza una cola para visitar las celdas en orden de distancia creciente desde el principio hasta llegar al final. Cada celda visitada debe realizar un seguimiento de su distancia desde el inicio o qué celda adyacente más cercana al inicio provocó que se agregara a la cola. Cuando encuentre la ubicación final, siga el camino de las celdas hacia atrás hasta el inicio, que es el camino más corto. La búsqueda en amplitud en su forma más simple tiene sus limitaciones, como encontrar el camino más corto en gráficos ponderados.
La exploración colectiva se refiere a la exploración de un entorno desconocido por parte de 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, [12] especialmente en el caso de árboles . El estudio depende del modelo de comunicación entre los agentes. En el modelo de comunicación centralizada, los agentes pueden comunicarse entre sí en todo momento. En el modelo de comunicación distribuida , los agentes sólo pueden comunicarse leyendo y escribiendo en las paredes del laberinto. Para árboles con nodos y profundidad , con robots, el mejor algoritmo actual está en el modelo de comunicación centralizada y en el modelo de comunicación distribuida. [12]
