El problema imaginario de la rata en busca de comida dentro de un laberinto se ha utilizado frecuentemente para escenificar diferentes estrategias de «búsqueda», un área muy estudiada en la Inteligencia Artificial.
Imaginemos que se sueltan tres ratas en un laberinto en cuyo interior hay, en algún lugar, una apetitosa comida. Cada rata utiliza una técnica de búsqueda diferente:
– La primera rata emplean un sistema de búsqueda aleatorio («el recorrido del borracho»).
– La segunda rata ejecuta una búsqueda exhaustiva («enumeración sistemática»)
– Y la tercera rata realiza una búsqueda heurística («exploración guiada»).
¿Cuál de ellas sería la técnica más eficiente?
Pues, a todas luces parece que la tercera técnica es la más inteligente y la que requiere menos esfuerzo para llegar a la solución.
Hay que observar que todos los métodos heurísticos dependen de «alguna forma» de saber cuándo la búsqueda se está aproximando a su objetivo (en nuestro ejemplo sería el olfato de la rata). Sin este tipo de conocimiento, la búsqueda no tendría más remedio que ser sistemática para hallar un resultado de forma segura.
Para demostrar esto presentamos el clásico problema de la búsqueda en el laberinto escrito en SuperBASIC. Es muy frecuente ver este programa ejemplo en textos de Inteligencia Artificial, y en su momento se presentaron versiones para Spectrum, MSX, Commodore, … en revistas de la época (una de ellas es «Mi Computer» -de donde saqué esta idea-). Pues bien, ahora le toca el turno a nuestro querido QL y su SuperBASIC. La ventaja sobre otras plataformas de los 80 es que el Basic del QL es más «humano» a la hora de leer y comprender el código que cualquier otro Basic de los de «antes».
Nuestro pequeño programa es experimental, y sólo pretende ilustrar una técnica de búsqueda empleando alguna heurística. Sobra decir que el BASIC en general no es un buen lenguaje para tratar este tipo de problemas, tal como lo pueda ser por ejemplo el C, Pascal o Lisp, pero aquí sólo tratamos de divertirnos con nuestros viejos ordenadores y de paso repasar o aprender algo más de programación (:-).
Bueno, comencemos …
El problema consiste en lo siguiente:
1) Construir un laberinto aleatorio donde colocamos un símbolo que representa a la rata «R» y otro símbolo que representa a la comida «C».
Laberinto, posiciones iniciales: Rata y Comida
2) El segundo paso, y el más interesante, es diseñar una estrategia que permita a la rata ir «aproximándose» a la comida sin necesidad de hacer una exploración exhaustiva. En la imagen 2 vemos el resultado de dicha exploración y cómo la rata va «olfateando» las distintas casillas hasta llegar a su objetivo.
Laberinto, rutina de exploración
3) Y finalmente, pintamos el recorrido más óptimo que ha encontrado la rata (no necesariamente el mejor).
Laberinto, resultado final
He intentado que el código sea lo más autodescriptivo posible, por lo que sólo comentaré las partes más interesantes.
El laberinto está representado en una matriz de dos dimensiones, codificada así
210 DIM M(MaxAlto+1, MaxAncho+1)
El alto y ancho del laberinto lo podemos configurar mediante las variables MaxAlto y MaxAncho. En nuestro ejemplo le hemos dado valores para que ocupe prácticamente toda la pantalla en Modo 8 del QL.
Cada casilla de esa matriz contiene alguno de los valores para representar: nuestra «ratita», la comida, las secciones de muro, y las casillas blancas donde la rata puede transitar. En el vector C$ colocamos los caracteres que representa cada una de esas posibilidades.
La estructura de datos más importante del programa son los siguientes vectores donde se va almacenando del «árbol» de búsqueda que va realizando la rata:
350 DIM Camino(LimArbol)
360 DIM Pasos(LimArbol)
370 DIM Nodos(LimArbol)
380 DIM Heu(LimArbol)
(LimArbol es una constante predeterminada para almacenar el recorrido de la rata por los distintos nodos de exploración).
Las posiciones de cada casilla se van almacenando en el vector «Nodos», se representan las coordenadas X,Y de la matriz que representa el laberinto por medio de un valor entero. La fórmula es CoordenadaXY = (Fila * MaxAncho) + Columna.
El vector Camino, va almacenando el «Nodo-Padre» de la casilla representada en cada elemento del vector. En cualquier elemento podemos hacer un recorrido hasta el nodo raíz empleando los valores de este vector.
El vector Pasos, representan el nivel de profundidad en el árbol de búsqueda.
Y por último, el vector Heu almacena el coste calculado. En base a este valor se van decidiendo los mejores nodos a expandir a medida que se avanza en la búsqueda. La heurística depende de los valores de este vector.
La estrategia empleada para el cálculo de este valor heurístico se denomina algorítmo A* (A estrella), y consiste en combinar un cálculo ponderado entre el recorrido realizado y la distancia que falta para llegar al objetivo. Nuestra fórmula empleada es:
CosteEstimado (H) = Distancia que queda (Q) + Distancia cubierta (C)
Podemos darle pesos a los valores de Q y C, en nuestro ejemplo 1 y 2 respectivamente. El valor más bajo de (H) es la elección mejor.
Otro aspecto importante a tener en cuenta, es que a medida que avanzamos en la búsqueda tenemos que «descatalogar» aquellas posiciones por las cuales no podemos seguir avanzando. Esto lo hacemos colocando un valor negativo en el vector Heu.
No sé si estos breves comentarios ayudarán en la lectura é interpretación del código fuente. A continuación se muestra el programa completo.
Si lo ejecutamos varias veces podemos comprobar que, en la mayoría de los casos, el resultado es bastante bueno.
En definitiva, un problema divertido con un lenguaje divertido como es el SuperBASIC del QL. Que lo disfrutéis.
.
100 REMark =============================================================
110 REMark -- Laberinto (afx, julio 2009)
120 REMark =============================================================
130 :
140 :
150 REMark -------------------------------------------------------------
160 REMark -- Declaraci–n variables globales y constantes
170 REMark -------------------------------------------------------------
180 :
190 MaxAlto = 20: MaxAncho = 39 : REMark ancho y alto del laberinto
200 DIM M(MaxAlto+1, MaxAncho+1) : REMark matriz del laberinto
210 LimArbol = 512 : REMark l“mite del vectores para Œrbol
220 Peso1 = 1: Peso2 = 2 : REMark pesos para la heur“stica
230 Muro = 1: Rata = 2: : REMark constantes
240 Comida = 3: Dn = 4: : REMark "
250 Blanco = 5 : REMark "
260 Xx = 999999 : REMark "
270 XNodo = 0 : REMark Siguinte Nodo libre
280 DIM C$(5) : REMark Caracteres del laberinto
290 C$(Muro) = CHR$(255)
300 C$(Blanco) = " "
310 C$(Rata) = "R"
320 C$(Comida) = "C"
330 C$(Dn) = " "
340 DIM Camino(LimArbol) : REMark vectores para manejo Œrbol
350 DIM Pasos(LimArbol) : REMark "
360 DIM Nodos(LimArbol) : REMark "
370 DIM Heu(LimArbol) : REMark " (Heur“stica)
380 FilComida = 0 : REMark Posici–n de la comida
390 ColComida = 0
400 NodCon = 0 : REMark N™mero de nodos examinados
410 SFil = 0 : REMark Siguiente Fila
420 SCol = 0 : REMark Siguiente Columna
430 S = 0 : REMark Mejor nodo, “ndice vector Œrbol
440 a$ = "" : REMark Para captura teclas
450 :
460 REMark --------------------------------------------------------------
470 REMark -- Secuencia principal
480 REMark --------------------------------------------------------------
490 :
500 REMark --- Pasos previos
510 :
520 InicializaPantalla
530 MensajeInfo 1, "Generando laberinto ..."
540 FabricaLaberinto
550 DibujarLaberinto
560 :
570 NodCon = 0
580 InicializarArbol
590 :
600 Nodos(1) = 2 * MaxAncho + 2 : REMark primer nodo abierto en pos 2,2
610 Pasos(1) = 0 : REMark por ahora no hay pasos
620 Camino(1) = 0 : REMark no hay ning™n predecesor (camino)
630 Heu(1) = (FilComida-1) + (ColComida-1) : REMark coste para heur“stica
640 :
650 REMark --- Bucle principal
660 :
670 MensajeInfo 0,"Explorando camino ..."
680 :
690 REPeat BuclePrincipal
700 BuscarMejorNodo
710 NodCon = NodCon + 1
720 MonitorExploracion
730 GenerarSucesores
740 IF (SFil = FilComida AND SCol = ColComida) OR NodCon > LimArbol-2 THEN
750 EXIT BuclePrincipal
760 END IF
770 END REPeat BuclePrincipal
780 :
790 REMark --- Resultado final
800 :
810 IF SFil = FilComida AND SCol = ColComida THEN
820 MensajeInfo 0, "Fin exploraci–n."
830 MensajeInfo 1, "Pulsa una tecla para pintar camino..."
840 a$ = INKEY$(-1)
850 :
860 DibujarLaberinto
870 MostrarCamino
880 :
890 MensajeInfo 0, "Pulsa una tecla para salir."
900 MensajeInfo 1, ""
910 a$ = INKEY$(-1)
920 ELSE
930 MensajeInfo 0, "Resultado."
940 MensajeInfo 1, "No he encontrado camino –ptimo..."
950 a$ = INKEY$(-1)
960 END IF
970 :
980 STOP
990 :
1000 :
1010 REMark -------------------------------------------------------------
1020 REMark -- Procedimientos, Funciones, ...
1030 REMark -------------------------------------------------------------
1040 :
1050 :
1060 DEFine PROCedure FabricaLaberinto
1070 LOCal i, j, lim
1080 FOR i = 1 TO MaxAlto + 1
1090 FOR j = 1 TO MaxAncho + 1
1100 IF RND(100) < 55 THEN
1110 M(i,j) = Muro
1120 ELSE
1130 M(i,j) = Blanco
1140 END IF
1150 IF i = 3 OR j = 3 THEN M(i,j) = Blanco
1160 IF i = MaxAncho - 4 OR j = MaxAlto -4 THEN M(i,j) = Blanco
1170 IF i = 1 OR j = 1 THEN M(i,j) = Muro
1180 IF i > MaxAlto OR j > MaxAncho THEN M(i,j) = Muro
1190 END FOR j
1200 END FOR i
1210 lim = INT(MaxAlto/2)
1220 FilComida = lim + INT(RND(MaxAlto-1-lim))
1230 lim = INT(MaxAncho/2)
1240 ColComida = lim + INT(RND(MaxAncho-1-lim))
1250 M(FilComida,ColComida) = Comida
1260 M(2,2) = Rata
1270 PasaEscoba
1280 END DEFine
1290 :
1300 :
1310 DEFine PROCedure PasaEscoba
1320 LOCal tx,ty,ax,ay,sx,sy,sw
1330 tx=2: ty=2: ax=1: ay=1: sx=1: sy=1 :sw=1
1340 REPeat tunel
1350 sw=RND(1,2)
1360 SELect ON sw
1370 =1
1380 IF sx THEN
1390 IF tx=MaxAlto THEN ax=-1
1400 tx=tx+ax
1410 END IF
1420 IF tx=FilComida AND ax=-1 THEN
1430 sx=0: IF ty>ColComida THEN ay=-1
1440 END IF
1450 =2
1460 IF sy THEN
1470 IF ty=MaxAncho THEN ay=-1
1480 ty=ty+ay
1490 END IF
1500 IF ty=ColComida AND ay=-1 THEN
1510 sy=0: IF tx>FilComida THEN ax=-1
1520 END IF
1530 END SELect
1540 IF M(tx,ty) = Comida THEN EXIT tunel
1550 M(tx,ty) = Blanco
1560 END REPeat tunel
1570 END DEFine
1580 :
1590 :
1600 DEFine PROCedure DibujarLaberinto
1610 LOCal i,j
1620 CLS
1630 FOR i = 1 TO MaxAlto + 1
1640 FOR j = 1 TO MaxAncho + 1
1650 AT i,j: PRINT C$( M(i,j) )
1660 END FOR j
1670 END FOR i
1680 INK 1: AT 2,2: PRINT C$(M(2,2))
1690 INK 6: AT FilComida,ColComida
1700 PRINT C$(M(FilComida,ColComida))
1710 INK 7
1720 END DEFine
1730 :
1740 :
1750 DEFine PROCedure InicializarArbol
1760 LOCal i
1770 FOR i = 1 TO LimArbol
1780 Camino(i) = 0
1790 Pasos(i) = Xx
1800 Nodos(i) = 0
1810 Heu(i) = Xx
1820 END FOR i
1830 XNodo = 2
1840 END DEFine
1850 :
1860 :
1870 DEFine PROCedure BuscarMejorNodo
1880 LOCal i, BN
1890 MensajeInfo 1, "Buscando mejor nodo ..."
1900 BN = Xx
1910 S = 1
1920 FOR i = 1 TO LimArbol
1930 IF Heu(i) >= 0 AND Heu(i) < Xx THEN
1940 V = Pasos(i) * Peso1 + ABS(Heu(i)) * Peso2
1950 IF V < BN AND Heu(i) >= 0 THEN
1960 S = i: BN = V
1970 END IF
1980 END IF
1990 END FOR i
2000 REMark IF S = 1 THEN PRINT#0, "Explorando ..."
2010 SFil = INT(Nodos(S) / MaxAncho)
2020 SCol = Nodos(S) - (MaxAncho * SFil)
2030 END DEFine
2040 :
2050 :
2060 DEFine PROCedure GenerarSucesores
2070 LOCal f, c
2080 LOCal res%
2090 MensajeInfo 1, "Generando sucesores..."
2100 res% = 0
2110 IF Heu(S) = 0 THEN RETurn
2120 REMark -- norte
2130 f = SFil - 1 : c = SCol
2140 IF f > 1 THEN
2150 res% = AbrirNodo% (f, c)
2160 END IF
2170 REMark -- este
2180 f = SFil : c = SCol + 1
2190 IF c <= MaxAncho THEN
2200 res% = AbrirNodo% (f, c)
2210 END IF
2220 REMark -- sur
2230 f = SFil + 1: c = SCol
2240 IF f <= MaxAlto THEN
2250 res% = AbrirNodo% (f, c)
2260 END IF
2270 REMark -- oeste
2280 f = SFil : c = SCol - 1
2290 IF c > 1 THEN
2300 res% = AbrirNodo% (f, c)
2310 END IF
2320 REMark -- Cerrar nodo
2330 Heu(S) = -Heu(S)
2340 IF (SFil <> 2 AND SCol <> 2) AND (SFil>0 AND SCol>0) THEN
2350 AT SFil,SCol: PRINT ".";
2360 END IF
2370 M(SFil,SCol) = Dn
2380 END DEFine
2390 :
2400 :
2410 DEFine FuNction AbrirNodo% (pF, pC)
2420 LOCal nx, xy
2430 IF M(pF,pC) = Dn THEN RETurn 0
2440 IF M(pF,pC) = Muro THEN RETurn 0
2450 REMark hallar posici–n libre
2460 nx = 0
2470 REPeat HallarPosicion
2480 IF Pasos(XNodo) <> Xx THEN
2490 nx = nx + 1: XNodo = XNodo + 1
2500 END IF
2510 IF XNodo > LimArbol THEN XNodo = 1
2520 IF nx > LimArbol THEN
2530 PRINT "No hay hueco en el arbol para expandir mŒs nodos"
2540 STOP
2550 END IF
2560 IF Pasos(XNodo) = Xx THEN
2570 EXIT HallarPosicion
2580 END IF
2590 END REPeat HallarPosicion
2600 REMark abrir el nodo
2610 xy = (pF * MaxAncho) + pC
2620 Nodos(XNodo) = xy
2630 Camino(XNodo) = S
2640 Pasos(XNodo) = Pasos(S) + 1
2650 Heu(XNodo) = ABS(pF - FilComida) + ABS(pC -ColComida)
2660 IF pF > 0 AND pC > 0 THEN
2670 AT pF,pC:PRINT "+"
2680 END IF
2690 RETurn 1
2700 END DEFine
2710 :
2720 :
2730 DEFine PROCedure InicializaPantalla
2740 MODE 8
2750 WINDOW 512,232,0,0
2760 WINDOW#2, 512,232,0,0
2770 WINDOW#0, 512,24,0,232
2780 PAPER 0: INK 7:BORDER 1,2: BORDER#2,1,2
2790 CLS:CLS#0:CLS#2
2800 END DEFine
2810 :
2820 :
2830 DEFine PROCedure MostrarCamino
2840 LOCal nPasos, x, y
2850 nPasos = Pasos(S)
2860 AT 0,0:PRINT "Camino de: ";nPasos;" pasos."
2870 INK 2
2880 REPeat PintaCamino
2890 REMark activar nodo padre
2900 S = Camino(S)
2910 IF S = 0 THEN EXIT PintaCamino
2920 y = INT(Nodos(S)/MaxAncho)
2930 x = Nodos(S) - y * MaxAncho
2940 AT y,x:PRINT "*"
2950 END REPeat PintaCamino
2960 INK 1
2970 AT 2,2:PRINT C$(Rata)
2980 INK 7
2990 END DEFine
3000 :
3010 :
3020 DEFine PROCedure MonitorExploracion
3030 AT 0,0:PRINT FILL$(" ",40)
3040 AT 0,0:PRINT "Casilla F:";SFil;" C:";SCol;" Nodo Arbol:"; S
3050 END DEFine
3060 :
3070 :
3080 DEFine PROCedure MensajeInfo (linea%, mensaje$)
3090 AT#0,linea%,0:PRINT#0, FILL$(" ",40)
3100 AT#0,linea%,0:PRINT#0, mensaje$
3110 END DEFine
.
NOTA (post editado):
– He corregido un error en las llamadas a la función AbrirNodo%, las llamada tenía dos parámetros más de los necesarios. Curiosamente esto no provocaba ningún error ni fallo en el programa, (los últimos parámetros no se utilizaban). ¡Curiosidades del SuperBASIC!
– Segunda corrección, se ha incluido una rutina (PasaEscoba) aportada por Badaman que asegura al menos un camino entre la rata y la comida.
QBlog 