4.11. Exploración de un laberinto¶
En esta sección examinaremos un problema que tiene relevancia para el mundo en expansión de la robótica: ¿Cómo encontrar la salida de un laberinto? Si usted tiene una aspiradora Roomba para limpiar su habitación (¿no todos los estudiantes universitarios?), deseará que pudiera reprogramarla utilizando lo que ha aprendido en esta sección. El problema que queremos resolver es ayudar a nuestra tortuga a encontrar su salida de un laberinto virtual. El problema del laberinto tiene raíces tan profundas como el mito griego sobre Teseo que fue enviado a un laberinto para matar al minotauro. Teseo usó una madeja de hilo para ayudarse a encontrar su camino de regreso una vez que hubiera eliminado a la bestia. En nuestro problema asumiremos que nuestra tortuga se deja caer en alguna parte en medio del laberinto y debe encontrar su salida. Mire la Figura 2 para tener una idea de hacia dónde vamos en esta sección.
Figura 2: El programa de búsqueda en un laberinto terminado¶
Figura 2: El programa de búsqueda en un laberinto terminado
Para que sea más fácil para nosotros, asumiremos que nuestro laberinto está dividido en “cuadrados”. Cada cuadrado del laberinto está abierto u ocupado por una sección de pared. La tortuga sólo puede pasar a través de los cuadrados abiertos del laberinto. Si la tortuga se topa con una pared, debe intentar continuar en una dirección diferente. La tortuga requerirá un procedimiento sistemático para encontrar su salida del laberinto. Aquí está el procedimiento:
Desde nuestra posición de partida, primero intentaremos avanzar un cuadrado hacia el Norte y luego recursivamente probaremos nuestro procedimiento desde allí.
Si no tenemos éxito al intentar un camino hacia el Norte como primer paso, daremos un paso hacia el Sur y repetiremos recursivamente nuestro procedimiento.
Si ir hacia el Sur no funciona, entonces intentaremos dar un paso hacia el Oeste como nuestro primer paso y aplicaremos nuestro procedimiento recursivamente.
Si el Norte, el Sur y el Oeste no han tenido éxito, aplicaremos el procedimiento recursivamente desde una posición un paso hacia nuestro Este.
Si ninguna de estas direcciones funciona entonces no hay manera de salir del laberinto y hemos fracasado.
Eso suena bastante fácil, sin embargo hay un par de detalles que discutir primero. Supongamos que tomamos nuestro primer paso recursivo al ir hacia el Norte. Siguiendo nuestro procedimiento, nuestro próximo paso sería también hacia el Norte. Pero si el Norte está bloqueado por una pared debemos mirar el siguiente paso del procedimiento e intentar ir hacia el Sur. Desafortunadamente ese paso hacia el Sur nos lleva de regreso a nuestro lugar de partida original. Si aplicamos el procedimiento recursivo desde allí, simplemente regresaremos un paso hacia el Norte y estaremos en un ciclo infinito. Por lo tanto, debemos contar con una estrategia para recordar dónde hemos estado. En este caso vamos a suponer que tenemos una bolsa de migas de pan que podemos dejar caer a lo largo de nuestro camino. Si damos un paso en una dirección determinada y encontramos que ya hay una miga de pan en ese cuadrado, sabemos que debemos retroceder inmediatamente y probar la siguiente dirección en nuestro procedimiento. Como veremos cuando observemos el código de este algoritmo, retroceder es tan simple como regresar desde una llamada recursiva de una función.
Como hacemos con todos los algoritmos recursivos, revisemos los casos base. Puede que usted ya haya adivinado algunos de ellos con base en la descripción del párrafo anterior. En este algoritmo hay cuatro casos base a considerar:
La tortuga se ha topado con una pared. Dado que el cuadrado está ocupado por una pared, no se puede realizar más exploración.
La tortuga ha encontrado un cuadrado que ya ha sido explorado. No queremos seguir explorando desde esta posición pues entraríamos en un ciclo.
Hemos encontrado un borde exterior que no está ocupado por una pared. En otras palabras, hemos encontrado una salida del laberinto.
Hemos explorado un cuadrado sin éxito en las cuatro direcciones.
Para que nuestro programa funcione, necesitaremos contar con una manera de representar el laberinto. Para hacer esto aún más interesante vamos a utilizar el módulo turtle para dibujar y explorar nuestro laberinto de modo que podamos ver este algoritmo en acción. El objeto Laberinto proporcionará los siguientes métodos para que los usemos al escribir nuestro algoritmo de búsqueda:
__init__lee en un archivo de datos que representa un laberinto, inicializa la representación interna del laberinto y encuentra la posición inicial para la tortuga.dibujarLaberintodibuja el laberinto en una ventana en la pantalla.actualizarPosicionactualiza la representación interna del laberinto y cambia la posición de la tortuga en la ventana.esSalidacomprueba si la posición actual es una salida del laberinto.
La clase Laberinto también sobrecarga el operador índice [] para que nuestro algoritmo pueda acceder fácilmente al estado de cualquier cuadrado particular.
Examinemos el código de la función de búsqueda que denominamos buscarDesde. El código se muestra en el Programa 3. Observe que esta función toma tres parámetros: un objeto laberinto, la fila de inicio y la columna de inicio. Esto es importante porque, como función recursiva, la búsqueda comienza lógicamente otra vez con cada llamada recursiva.
Programa 3
1def buscarDesde(laberinto, filaInicio, columnaInicio):
2 laberinto.actualizarPosicion(filaInicio, columnaInicio)
3 # Verificar casos base:
4 # 1. Hemos tropezado con un obstáculo, devolver False
5 if laberinto[filaInicio][columnaInicio] == OBSTACULO :
6 return False
7 # 2. Hemos encontrado un cuadrado que ya ha sido explorado
8 if laberinto[filaInicio][columnaInicio] == INTENTADO:
9 return False
10 # 3. Éxito, un borde exterior no ocupado por un obstáculo
11 if laberinto.esSalida(filaInicio,columnaInicio):
12 laberinto.actualizarPosicion(filaInicio, columnaInicio, \
13 PARTE_DEL_CAMINO)
14 return True
15 laberinto.actualizarPosicion(filaInicio, columnaInicio, INTENTADO)
16
17 # De lo contrario, use cortocircuitos lógicos para probar cada
18 # dirección a su vez (si fuera necesario)
19 encontrado = buscarDesde(laberinto, filaInicio-1, columnaInicio) or \
20 buscarDesde(laberinto, filaInicio+1, columnaInicio) or \
21 buscarDesde(laberinto, filaInicio, columnaInicio-1) or \
22 buscarDesde(laberinto, filaInicio, columnaInicio+1)
23 if encontrado:
24 laberinto.actualizarPosicion(filaInicio, columnaInicio, \
25 PARTE_DEL_CAMINO)
26 else:
27 laberinto.actualizarPosicion(filaInicio, columnaInicio, \
28 CAJELLON_SIN_SALIDA)
29 return encontrado
Al examinar el algoritmo usted verá que lo primero que hace el código (línea 2) es llamar a actualizarPosicion. Ésto se hace simplemente para ayudarle a usted a visualizar el algoritmo de modo que pueda ver exactamente cómo explora la tortuga su camino a través del laberinto. A continuación, el algoritmo comprueba los tres primeros de los cuatro casos base: ¿La tortuga ha chocado contra una pared (línea 5)? ¿La tortuga ha regresado a un cuadrado ya explorado (línea 8)? ¿La tortuga ha encontrado una salida (línea 11)? Si ninguna de estas condiciones es verdadera entonces continuamos la búsqueda recursivamente.
Usted notará que en el paso recursivo hay cuatro llamadas recursivas a buscarDesde. Es difícil predecir cuántas de estas llamadas recursivas se utilizarán, ya que todas ellas están conectadas por instrucciones or. Si la primera llamada a buscarDesde devuelve True, entonces ninguna de las tres últimas llamadas sería necesaria. Esto puede interpretarse como queriendo decir que un paso a (fila-1, columna) (o Norte si se quiere pensar geográficamente) está en el camino hacia la salida del laberinto. Si no hay un buen camino hacia el Norte para salir del laberinto, entonces se intenta la siguiente llamada recursiva, ésta al Sur. Si el Sur falla, se intenta entonces hacia el Oeste y finalmente hacia el Este. Si las cuatro llamadas recursivas devuelven False, entonces hemos encontrado un callejón sin salida. Usted debe descargar o transcribir todo el programa y experimentar con él cambiando el orden de estas llamadas.
El código de la clase Laberinto se muestra en el Programa 4, en el Programa 5 y en el Programa 6. El método __init__ toma el nombre de un archivo como su único parámetro. Este archivo es un archivo de texto que representa un laberinto usando caracteres “+” para las paredes, espacios en blanco para los cuadrados abiertos y la letra “S” para indicar la posición de inicio. La Figura 3 es un ejemplo de un archivo de datos del laberinto. La representación interna del laberinto es una lista de listas. Cada fila de la variable listalaberinto también es una lista. Esta lista secundaria contiene un carácter por cada cuadrado utilizando los caracteres descritos anteriormente. Para el archivo de datos en la Figura 3 la representación interna se parece a la siguiente:
[ ['+','+','+','+',...,'+','+','+','+','+','+','+'],
['+',' ',' ',' ',...,' ',' ',' ','+',' ',' ',' '],
['+',' ','+',' ',...,'+','+',' ','+',' ','+','+'],
['+',' ','+',' ',...,' ',' ',' ','+',' ','+','+'],
['+','+','+',' ',...,'+','+',' ','+',' ',' ','+'],
['+',' ',' ',' ',...,'+','+',' ',' ',' ',' ','+'],
['+','+','+','+',...,'+','+','+','+','+',' ','+'],
['+',' ',' ',' ',...,'+','+',' ',' ','+',' ','+'],
['+',' ','+','+',...,' ',' ','+',' ',' ',' ','+'],
['+',' ',' ',' ',...,' ',' ','+',' ','+','+','+'],
['+','+','+','+',...,'+','+','+',' ','+','+','+']]
El método dibujarLaberinto utiliza esta representación interna para dibujar en la pantalla la vista inicial del laberinto.
Figura 3: Un ejemplo del archivo de datos del laberinto
++++++++++++++++++++++
+ + ++ ++ +
+ + + +++ + ++
+ + + ++ ++++ + ++
+++ ++++++ +++ + +
+ ++ ++ +
+++++ ++++++ +++++ +
+ + +++++++ + +
+ +++++++ S + +
+ + +++
++++++++++++++++++ +++
El método actualizarPosicion, como se muestra en el Programa 5, utiliza la misma representación interna para ver si la tortuga se ha encontrado con una pared. También actualiza la representación interna con un “.” o un “-” para indicar que la tortuga ha visitado un cuadrado particular o si el cuadrado es parte de un callejón sin salida. Además, el método actualizarPosicion utiliza dos métodos auxiliares, moverTortuga y tirarMigaDePan, para actualizar la vista en la pantalla.
Finalmente, el método esSalida utiliza la posición actual de la tortuga para probar una condición de salida. Una condición de salida se da cuando la tortuga ha navegado hasta el borde del laberinto, ya sea la fila cero o la columna cero, o la columna de la derecha o la fila inferior.
Programa 4
class Laberinto:
def __init__(self,nombreArchivoLaberinto):
filasEnLaberinto = 0
columnasEnLaberinto = 0
self.listaLaberinto = []
archivoLaberinto = open(nombreArchivoLaberinto,'r')
filasEnLaberinto = 0
for linea in archivoLaberinto:
listaFila = []
columna = 0
for caracter in linea[:-1]:
listaFila.append(caracter)
if caracter == 'S':
self.filaInicio = filasEnLaberinto
self.columnaInicio = columna
columna = columna + 1
filasEnLaberinto = filasEnLaberinto + 1
self.listaLaberinto.append(listaFila)
columnasEnLaberinto = len(listaFila)
self.filasEnLaberinto = filasEnLaberinto
self.columnasEnLaberinto = columnasEnLaberinto
self.xTranslate = -columnasEnLaberinto/2
self.yTranslate = filasEnLaberinto/2
self.t = Turtle(shape='turtle')
setup(width=600,height=600)
setworldcoordinates(-(columnasEnLaberinto-1)/2-.5,
-(filasEnLaberinto-1)/2-.5,
(columnasEnLaberinto-1)/2+.5,
(filasEnLaberinto-1)/2+.5)
Programa 5
def dibujarLaberinto(self):
for y in range(self.filasEnLaberinto):
for x in range(self.columnasEnLaberinto):
if self.listaLaberinto[y][x] == OBSTACULO:
self.dibujarCajaCentrada(x+self.xTranslate,
-y+self.yTranslate,
'tan')
self.t.color('black','blue')
def dibujarCajaCentrada(self,x,y,color):
tracer(0)
self.t.up()
self.t.goto(x-.5,y-.5)
self.t.color('black',color)
self.t.setheading(90)
self.t.down()
self.t.begin_fill()
for i in range(4):
self.t.forward(1)
self.t.right(90)
self.t.end_fill()
update()
tracer(1)
def moverTortuga(self,x,y):
self.t.up()
self.t.setheading(self.t.towards(x+self.xTranslate,
-y+self.yTranslate))
self.t.goto(x+self.xTranslate,-y+self.yTranslate)
def tirarMigaDePan(self,color):
self.t.dot(color)
def actualizarPosicion(self,fila,columna,val=None):
if val:
self.listaLaberinto[fila][columna] = val
self.moverTortuga(columna,fila)
if val == PARTE_DEL_CAMINO:
color = 'green'
elif val == OBSTACULO:
color = 'red'
elif val == INTENTADO:
color = 'black'
elif val == CAJELLON_SIN_SALIDA:
color = 'red'
else:
color = None
if color:
self.tirarMigaDePan(color)
Programa 6
def esSalida(self,fila,columna):
return (fila == 0 or
fila == self.filasEnLaberinto-1 or
columna == 0 or
columna == self.columnasEnLaberinto-1 )
def __getitem__(self,indice):
return self.listaLaberinto[indice]
El programa completo se muestra en el ActiveCode 1. Este programa utiliza el archivo de datos laberinto2.txt que se muestra a continuación. Tenga en cuenta que es un archivo de ejemplo mucho más simple en que la salida está muy cerca de la posición inicial de la tortuga.
++++++++++++++++++++++
+ + ++ ++ +
+ ++++++++++
+ + ++ ++++ +++ ++
+ + + + ++ +++ +
+ ++ ++ + +
+++++ + + ++ + +
+++++ +++ + + ++ +
+ + + S+ + +
+++++ + + + + + +
++++++++++++++++++++++
Autoevaluación
Modifique el programa de búsqueda en un laberinto para que las llamadas a buscarDesde se encuentren en un orden diferente. Vea la ejecución del programa. ¿Puede usted explicar por qué el comportamiento es diferente? ¿Puede usted predecir qué camino seguirá la tortuga para un cambio dado del orden?