Algoritmo de resolución de laberintos

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 pared, de Pledge y de 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 del camino más corto están diseñados para ser utilizados por una persona o un programa informático que pueda ver todo el laberinto a la vez.Los laberintos sin bucles se conocen como laberintos "simplemente conexos" o "perfectos", y son equivalentes 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 se estiraran los caminos del laberinto correctamente, el resultado podría asemejarse a un árbol.Este sencillo método puede ser implementado por un robot poco inteligente o quizás un ratón, ya que no requiere memoria. El robot continúa siguiendo el recorrido actual hasta llegar a un cruce y luego toma una decisión aleatoria sobre la siguiente dirección. Aunque este método siempre encontraría la solución correcta, el algoritmo puede ser muy lento.

Una regla eficaz para recorrer 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, al mantener una mano en contacto con una pared, el solucionador tiene la garantía de no perderse y alcanzar una salida diferente, si la hay. De lo contrario, el algoritmo regresará a la entrada tras haber recorrido al menos una vez todos los pasillos junto a esa sección de paredes conectada. El algoritmo es un recorrido de árbol ordenado en 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. En ese caso, el seguimiento de paredes se reduce a caminar en 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 estos son precisamente las soluciones, incluso si hay más de una.

Si el laberinto no está simplemente conectado (es decir, si los puntos de inicio y fin están en el centro de la estructura rodeados de bucles de paso, o si los caminos se cruzan y se encuentran por debajo, 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 tener cuidado al comenzar a seguir la pared en la entrada del laberinto. Si el laberinto no es simplemente conexo y se comienza a seguir la pared en un punto arbitrario dentro del laberinto, se podría quedar atrapado en una pared separada que gira sobre sí misma y no tiene entradas ni salidas. Si el seguimiento de la pared comienza tarde, se debe intentar marcar el punto donde comenzó. Dado que seguir la pared siempre llevará de vuelta al punto de partida, si se vuelve a encontrar el punto de partida, se puede concluir que el laberinto no es simplemente conexo y se debe cambiar a una pared alternativa que aún no se haya seguido. Consulta el Algoritmo de Compromiso, a continuación, para una metodología alternativa.El seguimiento de paredes puede realizarse en laberintos 3D o de dimensiones superiores si sus pasajes de dimensiones superiores pueden proyectarse en el plano 2D de forma determinista. Por ejemplo, si en un laberinto 3D se asume que los pasajes ascendentes conducen al noroeste y los descendentes al sureste, se aplican las reglas estándar de seguimiento de paredes. Sin embargo, a diferencia del laberinto 2D, esto requiere conocer la orientación actual para determinar qué dirección es la primera a la izquierda o a la derecha.Puede encontrar una simulación del funcionamiento de este algoritmo aquí.

Los laberintos disjuntos (donde las paredes no están conectadas al límite exterior/el límite no es cerrado) pueden resolverse con el método de seguimiento de pared, siempre que la entrada y la salida del laberinto se encuentren en las paredes exteriores. 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 Jon Pledge de Exeter) puede resolver este problema.El algoritmo Pledge, diseñado para sortear obstáculos, requiere una dirección elegida arbitrariamente, la cual será preferencial. Al encontrarse con un obstáculo, se mantiene una mano (por ejemplo, la derecha) a lo largo del obstáculo mientras se cuentan los ángulos de giro (el giro en sentido horario es positivo, el giro en sentido antihorario es negativo). Cuando el solucionador vuelve a estar orientado hacia la dirección preferencial original y la suma angular de los giros es 0, abandona el obstáculo y continúa moviéndose en su dirección original.La mano se retira de la pared solo cuando la suma de giros y el rumbo actual son cero. Esto permite al algoritmo evitar trampas con forma de letra G mayúscula. Suponiendo que el algoritmo gira a la izquierda en la primera pared, las paredes dan un giro de 360 grados. Un algoritmo que solo registra el rumbo actual entra en un bucle infinito al abandonar la pared inferior derecha en dirección izquierda y volver a la sección curva del lado izquierdo. El algoritmo Pledge no abandona la pared derecha debido a que la suma de giros no es cero en ese punto (nota: 360 grados no es igual a 0 grados). Sigue la pared en toda su extensión, dejándola finalmente en dirección izquierda, justo por debajo de la letra.Este algoritmo permite a una persona con una brújula orientarse desde cualquier punto dentro de un laberinto bidimensional finito hasta una salida exterior, independientemente de la posición inicial del solucionador. Sin embargo, este algoritmo no funciona a la inversa, es decir, no permite orientarse desde una entrada exterior del laberinto hasta un objetivo final dentro del mismo.

El algoritmo de Trémaux, inventado por Charles Pierre Trémaux, es un método eficiente para encontrar la salida de un laberinto que requiere dibujar líneas en el suelo para marcar un camino. Se garantiza que funciona en todos los laberintos con pasajes bien definidos, pero no garantiza que encuentre la ruta más corta.La entrada de un pasaje puede estar sin visitar, marcada una vez o dos veces. Cabe destacar que marcar una entrada no es lo mismo que marcar un cruce o un pasaje, ya que un cruce puede tener múltiples entradas, y un pasaje tiene una entrada en ambos extremos. Los callejones sin salida pueden considerarse cruces con una sola entrada (imaginemos que hay una habitación en cada callejón sin salida).El algoritmo funciona según las siguientes reglas:

• Cada vez que pasas por una entrada de un pasaje, ya sea para entrar o salir de un cruce, deja una marca en la entrada mientras pasas.
• Cuando se encuentra en un cruce, utilice la primera regla aplicable a continuación para elegir una entrada a la salida a través de:
  1. Si sólo la entrada de la que acabas de llegar está marcada, elige una entrada arbitraria sin marcar, si la hay. Esta regla también se aplica si usted está empezando en el medio del laberinto y no hay entradas marcadas en absoluto.
  2. Si todas las entradas están marcadas, vuelva por la entrada de la que acabas de llegar, a menos que esté marcada dos veces. Esta regla se aplicará cuando llegue a un callejón sin salida.
  3. Elija cualquier entrada con las marcas más pequeñas (cero si es posible, otra).

La regla de "dar la vuelta y regresar" transforma cualquier laberinto con bucles en uno simplemente conectado; siempre que encontramos un camino que cierre un bucle, lo consideramos un callejón sin salida y regresamos. Sin esta regla, es posible bloquear el acceso a partes aún inexploradas de un laberinto si, en lugar de regresar, elegimos arbitrariamente otra entrada.Al llegar a la solución, las entradas marcadas una sola vez te indicarán el camino de regreso al inicio. Si no hay salida, este método te llevará de vuelta al inicio, donde todas las entradas están marcadas dos veces. En este caso, cada pasaje se recorre exactamente dos veces, una en cada dirección. El recorrido resultante se denomina doble trazado bidireccional.

En esencia, este algoritmo, descubierto en el siglo XIX, se utilizó unos cien años después como búsqueda en profundidad.El método de relleno 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 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. encontrar todos los callejones en el laberinto, y luego
2. "llena" el camino de cada extremo muerto hasta que se encuentre la primera unión.

Tenga en cuenta que algunos pasajes no se convertirán en parte de los pasajes sin salida hasta que se eliminen otros primero. A la derecha se puede ver un video del relleno de los pasajes sin salida.El relleno de callejones sin salida no puede separar accidentalmente el inicio del fin, ya que cada paso del proceso preserva la topología del laberinto. Además, el proceso no se detendrá prematuramente, ya 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), se conservarán todas las posibles soluciones, pero nada más. [1]Si se proporciona una vista omnisciente del laberinto, un algoritmo recursivo simple puede indicar cómo llegar al final. El algoritmo recibirá un valor inicial de X e Y. Si estos valores no están en una pared, el método se llamará a sí mismo con todos los valores adyacentes, asegurándose de no haberlos usado previamente. Si los valores de 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 la cuadrícula. La vista omnisciente evita la introducción de bucles por memorización. Aquí hay un ejemplo de código en Java:El algoritmo de enrutamiento de laberintos es un método de bajo consumo para encontrar el camino entre dos puntos cualesquiera del laberinto. Inicialmente, se propuso para el dominio de los multiprocesadores de chip (CMP) y garantiza su funcionamiento en cualquier laberinto basado en cuadrícula. Además de encontrar rutas entre dos puntos de la cuadrícula (laberinto), el algoritmo puede detectar cuándo no hay ruta entre el origen y el destino. Además, el algoritmo está diseñado para ser utilizado por un viajero interno sin conocimiento previo del laberinto, con una complejidad de memoria fija, independientemente del tamaño del laberinto; requiere un total de cuatro variables para encontrar la ruta y detectar los puntos inalcanzables. Sin embargo, el algoritmo no busca la ruta más corta.El algoritmo de enrutamiento de laberinto utiliza el concepto 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 al moverse de una ubicación a cuatro ubicaciones vecinas. Aquí está el pseudocódigo sin la capacidad de detectar ubicaciones inalcanzables.

Cuando un laberinto tiene múltiples soluciones, quien lo resuelve puede querer encontrar el camino más corto de principio a fin. Existen varios algoritmos para encontrar los caminos más cortos, la mayoría basados en la teoría de grafos. Uno de estos algoritmos encuentra el camino más corto mediante 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 creciente de distancia desde el inicio hasta el final. Cada celda visitada debe registrar su distancia desde el inicio o qué celda adyacente más cercana al inicio provocó su adición a la cola. Una vez encontrada la ubicación final, se sigue la ruta 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 múltiples agentes móviles que se mueven a la misma velocidad. Este modelo fue introducido estudiar la paralelización del laberinto, especialmente en el caso de los árboles. El estudio depende del modelo de comunicación entre los agentes. En el modelo centralizado de comunicación, se permite a los agentes comunicarse en todo momento entre sí. En el modelo de comunicación distribuido, los agentes sólo 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 algoritmo más actual está en ${\displaystyle O\left({\frac {n}}+kD\right)}$ en el modelo centralizado de comunicación y en ${\displaystyle O\left({\frac {\log k}+D\right)}$ en el modelo de comunicación distribuido.

• Maze
• algoritmo de generación de laberinto

• Piensa en Laberinto: algoritmos de laberinto (detalles de estos y otros algoritmos de resolución de laberinto)
• MazeBlog: Resolver laberintos utilizando el análisis de imagen
• Video: simulación de solución de laberinto
• Simon Ayrinhac, corriente eléctrica resuelve laberintos, © 2014 IOP Publishing Ltd.