Un algoritmo de resolución de laberintos es un método automatizado para resolver un laberinto . Los algoritmos del ratón aleatorio, del seguidor de la pared, de Pledge y de Trémaux están diseñados para que los utilice dentro del laberinto un viajero sin conocimiento previo del laberinto, mientras que los algoritmos de relleno de callejones sin salida y del camino más corto están diseñados para que los utilice una persona o un programa informático que pueda ver todo el laberinto a la vez.
Los laberintos que no contienen bucles se conocen como laberintos "simplemente conectados" o "perfectos" y son equivalentes a un árbol en la 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 alargara los caminos en el laberinto de la manera adecuada, el resultado podría asemejarse a un árbol. [1]
Este método simple puede ser implementado por un robot muy poco inteligente o quizás por un ratón, ya que no requiere memoria. El robot continúa siguiendo el recorrido actual hasta llegar a una intersección y luego toma una decisión aleatoria sobre la siguiente dirección a seguir. Aunque un método de este tipo siempre encontraría eventualmente la solución correcta , el algoritmo puede ser muy lento. [2]
Una regla eficaz para atravesar laberintos es la regla de la mano sobre 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 con el 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 hay una; de lo contrario, el algoritmo regresará a la entrada después de haber atravesado todos los corredores junto a esa sección conectada de paredes al menos una vez. El algoritmo es un recorrido de árbol en orden de profundidad .
Otra perspectiva de por qué funciona el seguimiento de paredes es topológica. Si las paredes están conectadas, pueden deformarse formando un bucle o un círculo. [3] En ese caso, el seguimiento de paredes se reduce a caminar alrededor de un círculo de principio a fin. Para profundizar en esta idea, observe que al agrupar los 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 de inicio o final están en el centro de la estructura rodeados de bucles de paso, o los caminos se cruzan uno sobre el otro 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 de comenzar a seguir la pared en la entrada del laberinto. Si el laberinto no está conectado de manera simple 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. Si se da el caso de que el seguimiento de la pared comienza tarde, intente marcar la posición en la que comenzó. Debido a que seguir la pared siempre lo llevará de regreso al punto de partida, si se encuentra con su punto de partida una segunda vez, puede concluir que el laberinto no está conectado de manera simple y debe cambiar a una pared alternativa que aún no haya seguido. Vea el Algoritmo de compromiso , a continuación, para una metodología alternativa.
El seguimiento de paredes se puede realizar en laberintos tridimensionales o de dimensiones superiores si sus pasajes de dimensiones superiores se pueden proyectar en el plano bidimensional de manera determinista. Por ejemplo, si en un laberinto tridimensional se puede suponer que los pasajes "ascendentes" conducen al noroeste y los pasajes "descendentes" 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 que se conozca la orientación actual para determinar qué dirección es la primera a la izquierda o a la derecha.
Puedes encontrar una simulación del funcionamiento de este algoritmo aquí.
Los laberintos disjuntos (en los que las paredes no están conectadas al límite exterior o el límite no está cerrado) se pueden resolver con el método de los seguidores de pared, siempre que la entrada y la salida del laberinto se encuentren en las paredes exteriores del laberinto. Sin embargo, si el solucionador comienza dentro del laberinto, podría estar en una sección disjunta con respecto a la salida, y los seguidores de pared girarán continuamente alrededor de su anillo. El algoritmo Pledge (llamado así por 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 que dirigirse, que será la preferencial. Cuando se encuentra un obstáculo, una mano (por ejemplo, la derecha) se mantiene 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 se encuentra de nuevo de cara a 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 solo 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, uno gira 360 grados completos por las paredes. Un algoritmo que solo lleva un registro del "rumbo actual" conduce a un bucle infinito, ya que deja la pared inferior derecha en dirección a la izquierda y se dirige nuevamente hacia la sección curva del lado izquierdo. El algoritmo Pledge no abandona la pared más a la derecha debido a que la "suma de vueltas realizadas" no es cero en ese punto (tenga en cuenta que 360 grados no es igual a 0 grados ). Sigue la pared por completo, y finalmente la deja en dirección a 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 dentro de un laberinto finito bidimensional hasta una salida exterior, independientemente de la posición inicial del solucionador. Sin embargo, este algoritmo no funcionará al revés, es decir, no funcionará al encontrar el camino desde una entrada en el exterior de un laberinto hasta un 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 está garantizado que encuentre la ruta más corta.
La entrada de un pasaje no está visitada, está marcada una vez o está marcada dos veces. Tenga en cuenta que marcar una entrada no es lo mismo que marcar una intersección o un pasaje, porque una intersección puede tener múltiples entradas y un pasaje tiene una entrada en ambos extremos. Los callejones sin salida se pueden considerar como intersecciones con una entrada (imagine que hay una habitación en cada callejón sin salida).
El algoritmo funciona según las siguientes reglas:
La regla de "dar la vuelta y regresar" transforma de manera efectiva cualquier laberinto con bucles en uno simplemente conectado: siempre que encontramos un camino que cierra 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 dar la vuelta, elegimos arbitrariamente otra entrada.
Cuando finalmente se llega a la solución, las entradas marcadas exactamente una vez indicarán un camino de regreso al inicio. Si no hay salida, este método lo llevará de regreso al inicio, donde todas las entradas están marcadas dos veces. En este caso, se camina por cada pasaje exactamente dos veces, una en cada dirección. El camino resultante se llama doble trazado bidireccional. [8]
En esencia, este algoritmo, que fue descubierto en el siglo XIX, se utilizó unos cien años después como búsqueda en profundidad . [9] [10]
El método de relleno de callejones sin salida es un algoritmo para resolver laberintos que rellena todos los callejones sin salida, dejando solo los caminos correctos sin rellenar. Se puede utilizar para resolver laberintos en papel o con un programa informático, pero no es útil para una persona que se encuentra dentro de un laberinto desconocido, ya que este método analiza todo el laberinto a la vez. El método consiste en
Tenga en cuenta que algunos pasajes no pasarán a formar parte de los pasajes sin salida hasta que se eliminen otros primero. A la derecha se puede ver un video del proceso de rellenado de los pasajes sin salida.
El relleno de callejones sin salida no puede "cortar" accidentalmente el inicio del fin, 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 ningún callejón sin salida. Por lo tanto, si el relleno de callejones sin salida se realiza en un laberinto perfecto (un laberinto sin bucles), entonces solo quedará la solución. Si se realiza en un laberinto parcialmente trenzado (un laberinto con algunos bucles), entonces quedarán todas las soluciones posibles, pero nada más. [1]
Si se ofrece una visión omnisciente del laberinto, un algoritmo recursivo simple puede indicar cómo llegar al final. Se le proporcionará al algoritmo un valor X e Y inicial. 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 utilizado 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.
En efecto, se trata de una búsqueda en profundidad expresada en términos de puntos de cuadrícula. La vista omnisciente evita la introducción de bucles mediante la memorización. A continuación, se incluye un código de ejemplo en Java :
boolean [][] maze = new boolean [ width ][ height ] ; // El laberinto boolean [][] wasHere = new boolean [ width ][ height ] ; boolean [][] correctPath = new boolean [ width ][ height ] ; // La solución del laberinto int startX , startY ; // Valores iniciales X e Y del laberinto int endX , endY ; // Valores finales X e Y del laberinto public void solveMaze () { laberinto = generateMaze (); // Crear laberinto (falso = camino, verdadero = pared) // La siguiente asignación a falso es redundante ya que Java asigna elementos de matriz a falso de manera predeterminada for ( int row = 0 ; row < maze . length ; row ++ ) // Establece 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 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 )) { // Recuerda el 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 )) { // Recuerda el 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 )) { // Recuerda el 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 )) { // Recuerda el método uno hacia abajo correctPath [ x ][ y ] = true ; return true ; } return false ; } El algoritmo de enrutamiento de laberintos [11] es un método de bajo consumo de recursos para encontrar el camino entre dos ubicaciones cualesquiera del laberinto. El algoritmo se propuso inicialmente para el dominio de los multiprocesadores de chip (CMP) y garantiza que funciona para cualquier laberinto basado en cuadrículas. Además de encontrar caminos entre dos ubicaciones de la cuadrícula (laberinto), el algoritmo puede detectar cuándo 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 debe encontrar el camino más corto.
El algoritmo de enrutamiento de laberintos utiliza la noción de distancia de Manhattan (MD) y se basa en la propiedad de las cuadrículas de que la MD aumenta o disminuye exactamente en 1 cuando se pasa de una ubicación a cuatro ubicaciones vecinas. Aquí se muestra el pseudocódigo sin la capacidad de detectar ubicaciones inalcanzables.
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 el MD más cercano que hemos tenido a dst // Una ruta productiva es la que hace que nuestra MD a dst sea más pequeña while ( cur ! = dst ) { if ( existe una ruta productiva ) { Tome la ruta productiva ; } else { MD_best = MD ( cur , dst ); Imagine una línea entre cur y dst ; Tome 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 ) { Siga la regla de la mano derecha / mano izquierda ; // El opuesto del lado seleccionado de la línea } } 
Cuando un laberinto tiene múltiples soluciones, el solucionador puede querer encontrar el camino más corto desde el principio hasta el final. Hay varios algoritmos para encontrar los 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 celdas en orden de distancia creciente desde el inicio hasta que se llega al final. Cada celda visitada necesita realizar un seguimiento de su distancia desde el inicio o qué celda adyacente más cercana al inicio hizo que se agregara a la cola. Cuando se encuentra la ubicación de finalización, sigue 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 grafos 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 los árboles . El estudio depende del modelo de comunicación entre los agentes. En el modelo de comunicación centralizada, los agentes pueden comunicarse en todo momento entre sí. En el modelo de comunicación distribuida , los agentes pueden comunicarse solo leyendo y escribiendo en las paredes del laberinto. Para árboles con nodos y profundidad , con robots, el mejor algoritmo actual está en en el modelo de comunicación centralizada y en en el modelo de comunicación distribuida. [12]
