Razonando como un niño

Acababa de llegar a la oficina, y ahí estaba el señor Lego sentado en la mesa de al lado. A pesar de ser mi compañero de trabajo (es programador como yo) nos hablamos de usted y yo siempre lo llamo señor Lego (su nombre real es Pascal Lego). Estaba ensimismado tratando de resolver un rompecabezas para niños pequeños. Un rompecabezas lineal de unas cuatro piezas grandes.

¿Difícil señor Lego? - Dije irónicamente.
Mucho, me respondió. Anoche estaba enseñando a mi hijo como resolver operaciones matemáticas con el ordenador, y de pronto me espetó - "Este ordenador es tonto, ni siquiera es capaz de resolver mi rompecabezas" - Y aquí ando, viendo como podría hacer un programa para demostrar a mi hijo que el ordenador si puede resolverlo. Quizás tu puedas echarme una mano.
La verdad es que tenía bastante trabajo acumulado, pero uno no es de piedra y siempre está dispuesto a enfrentarse a nuevos desafíos.



Esta bien, señor Lego. Primero hay que buscar una forma de representar el rompecabezas en el ordenador. Le propongo la siguiente representación:
A cada pieza le asignaremos un número, y la representaremos en una lista o array de enteros. Consideraremos que dos piezas encajan si con consecutivas y están ordenadas de menor a mayor. Por ejemplo [1234] representaría el rompecabezas bien ordenado y en el que encajan todas las piezas. Si estuvieran así [2134] significaría que las dos primeras piezas no encajan (están bailadas) pero las dos últimas si encajan.

Sí, me parece bien -dijo el señor Lego con poca convicción.

Ahora tenemos que definir qué acciones vamos a poder realizar sobre sobre las piezas. Si le parece, podemos definir estas:

D - Intercambiar las dos piezas de la derecha.
C - Intercambiar las dos piezas centrales.
I - Intercambiar las dos piezas de la izquierda.

De forma que si aplicamos la operación D a [2134] obtendríamos [1234].

Ya veo -dijo el señor Lego - entonces se trata de ir intercambiando piezas contiguas hasta conseguir que el rompecabezas esté ordenado.

Eso es -respondí. Ahora nos falta decidir qué estrategia seguimos para ir intercambiando las piezas. Si usted o yo quisiéramos ordenar las piezas seguiríamos una serie de procesos mentales bastante complejos, pero el ordenador, afortunadamente, no es tan inteligente como nosotros. Si fueras tan tonto como un ordenador, ¿qué estrategia seguirías?

El señor Lego se quedó mirándome sin saber si yo esperaba realmente una respuesta o era una pregunta retórica que estaba a punto de contestar yo mismo.

Pues probaría cambios a ciegas hasta que finalmente obtuviera el rompecabezas ordenado.

Muy bien, señor Lego. Me parece una buena estrategia -contesté como si fuera un locutor de radio que acaba de dar un premio a un oyente.
Para entendernos, en lo sucesivo, llamaremos estado a como queda el rompecabezas tras cada intercambio. Por lo tanto, partiremos de un estado inicial, que es como se encuentra el rompecabezas antes de empezar. Además iremos haciendo los cambios de forma sistemática para no dejarnos ninguno atrás. Lo mejor es verlo como un árbol donde se despliegan todas las posibilidades (estados). Cogí un bolígrafo e hice el siguiente esquema.

Fíjese señor Lego, He puesto arriba el estado inicial, y para generar los siguientes estados aplico las tres operaciones que hemos definido antes (D, C e I). Indico las operaciones aplicadas en cada caso en las flechitas para que quede más claro. Esto es lo que llamaremos expandir un estado. Si comprobamos que no hemos obtenido una ordenación correcta (a la que llamaremos nodo solución) repetimos el procedimiento expandiendo cada uno de los tres nuevos nodos que se han generado (a los que llamaremos nodos hijos).
En rojo he marcado un posible camino que nos ofrece una solución.

Pero, puede haber varios caminos que lleven a la solución del rompecabezas ¿no? -dijo el señor Lego.
Efectivamente, pero por ahora, nos bastará con cualquiera de las soluciones.

El Sr. Lego me miró desafiante y dijo: ¡Voy a probar a implemetarlo! Mientras salía corriendo a sentarse en su ordenador.

Pasó un buen rato, y cuando suponía que ya lo había dejado por imposible y que se estaría dedicando a mirar páginas en Internet, se levantó con unos listados en Python y me los soltó encima del teclado.

Reproduzco aquí ambos listados.

arbol.py

1. class Hoja:
2.     def __init__(self, datos, hijos=None):
3.         self.datos = datos
4.         self.hijos = None
5.         self.padre = None
6.         self.set_hijos(hijos)
7.        
8.     def __str__(self):
9.         return str(self.datos)
11.     def set_hijos(self, hijos):
12.         self.hijos=hijos
13.         if self.hijos != None:
14.             for h in self.hijos:
15.                 h.padre = self
17.     def get_hijos(self):
18.         return self.hijos
20.     def set_datos(self, datos):
21.         self.datos = datos
22.            
23.     def get_datos(self):
24.         return self.datos

backtracking_i.py

1. from arbol import Hoja
3. def buscar_solucion():
5.     global solucionado
6.     global estado_inicial
7.     global solucion
8.     global hojas_expandidas
9.     global hojas_no_expandidas
10.     global nodo_solucion
12.     while (not solucionado) and len(hojas_no_expandidas)!=0:
13.         nodo=hojas_no_expandidas[0]
14.         hojas_expandidas.append(hojas_no_expandidas.pop(0))
15.         if nodo.get_datos() == solucion:
16.             solucionado=True
17.             nodo_solucion = nodo
18.         else:
19.             # expandir nodos sucesores
20.             dato_nodo = nodo.get_datos()
21.            
22.             # movimiento izquierdo
23.             hijo_izquierdo = Hoja([dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]])
24.             hojas_no_expandidas.append(hijo_izquierdo)
26.             # movimiento central
27.             hijo_central = Hoja([dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]])
28.             hojas_no_expandidas.append(hijo_central)
30.             # movimiento derecho
31.             hijo_derecho = Hoja([dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]])
32.             hojas_no_expandidas.append(hijo_derecho)
34.             nodo.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho])
38. if __name__ == "__main__":
39.     print "iterativa"
40.     estado_inicial=[4,2,3,1]
41.     solucion=[1,2,3,4]
42.     hojas_expandidas=[]
43.     hojas_no_expandidas=[]
44.     solucionado=False
45.     nodo_solucion = None
47.     nodoInicial = Hoja(estado_inicial)
48.     hojas_no_expandidas.append(nodoInicial)
50.     buscar_solucion()
52.     # mostrar resultado (al reves)
53.     nodo=nodo_solucion
54.     while nodo.padre != None:
55.         print nodo
56.         nodo = nodo.padre
58.     print nodo

Tras ejecutarlos, obtuvimos el siguiente resultado:

[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]

Mira como lo he resuelto -dijo el señor Lego con un entusiasmo al que no nos tenía acostumbrado. Es el resultado de la búsqueda por el árbol, pero al revés. Muestro así el resultado porque empiezo mostrando el nodo solución y recorro hacia atrás el árbol hasta el nodo raíz. Lo he dejado así para no complicar mucho el programa y que sea más fácil de seguir.

Increíble señor Lego, su programa funciona correctamente. Pero explíqueme como lo ha planteado -le dije mostrando interés.

Bien, lo que he hecho es crear una clase muy sencilla para el manejo de árboles y que luego utilizo en el programa principal.
Tenemos una lista llamada hojas_no_expandidas donde inicialmente almacenamos el estado inicial.
En su bucle principal, el programa realiza las siguientes acciones:
A cada iteración del bucle while obtengo el primer nodo de hojas_no_expandidas y compruebo si ese nodo es un nodo solución. añadimos ese nodo a otra estructura (una lista) llamada hojas_expandidas, y evidentemente la retiro de hojas_no_expandidas.
Si el nodo es una solución, terminamos; si no, expandimos el nodo aplicando las tres operaciones (D, C, I) y añadimos los tres nodos nuevos a hojas_no_expandidas.

La verdad es que no esperaba que el señor Lego fuera capaz de resolver el problema, aunque la verdad es que no terminaban de convencerme todas aquellas variables globales, aunque supongo que lo dejó así por simplicidad y para que yo pudiera entender mejor su código.
No está nada mal, señor Lego. Acaba de implementar una búsqueda en un árbol, y usted ha hecho una implementación iterativa -le dije.

¿Iterativa? ¿es que se puede implementar de otra forma? -dijo simulando sorpresa.

De hecho, señor Lego, los algoritmos de busqueda suelen implementarse usando recursividad -dije.
El señor Lego sabía lo que era la recursividad de sus años de carrera, pero no tenía muy claro cómo podría usarla en este problema, así que me senté ante el ordenador y tecleé el código siguiente reutilizando su implementación de árbol.

backtracking_r.py

1. from arbol import Hoja
2.  
3. def buscar_solucion(nodo_inicial, solucion, visitados):
4.     visitados.append(nodo_inicial.get_datos())
5.     if nodo_inicial.get_datos() == solucion:
6.         return nodo_inicial
7.     else:
8.         # expandir nodos sucesores (hijos)
9.         dato_nodo = nodo_inicial.get_datos()
10.         hijo_izquierdo = Hoja([dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]])
11.         hijo_central = Hoja([dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]])
12.         hijo_derecho = Hoja([dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]])
13.         nodo_inicial.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho])
14.  
15.         for nodo_hijo in nodo_inicial.get_hijos():
16.             if not nodo_hijo.get_datos() in visitados:
17.                 sol = buscar_solucion(nodo_hijo, solucion, visitados)
18.                 if sol != None:
19.                     return sol
20.  
21.         return None
22.  
23.  
24. if __name__ == "__main__":
25.     print "recursiva"
26.     estado_inicial=[4,2,3,1]
27.     solucion=[1,2,3,4]
28.     nodo_solucion = None
29.     visitados=[]
30.  
31.     nodo_inicial = Hoja(estado_inicial)
32.  
33.     nodo = buscar_solucion(nodo_inicial, solucion, visitados)
34.  
35.     # mostrar resultado (al reves)
36.     while nodo.padre != None:
37.         print nodo
38.         nodo = nodo.padre
39.  
40.     print nodo
41.  
42.  

Ahora -comencé a explicarle- la función buscar_solucion recibe tres parámetros: El nodo inicial, la solución que estamos buscando y una lista llamada visitados que contendrá aquellos nodos que vayamos visitando durante el recorrido del árbol.
Ya dentro de la función, si comprobamos que hemos llegado a una solución, saldremos devolviendo dicho nodo como resultado; si no, expandimos el nodo y volvemos a llamar recursivamente a la función buscar_solucion con cada uno de los nodos hijos generados. Si el nodo que estamos evaluando no es solución devolvemos None (valor nulo).

Ejecuté el programa y éste fue el resultado:

[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 1, 4, 3]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
[1, 4, 3, 2]
[1, 3, 4, 2]
[3, 1, 4, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[4, 3, 2, 1]
[3, 4, 2, 1]
[3, 2, 4, 1]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]

La sonrisa del señor Lego se hizo enorme al ver que su solución había resuelto el rompecabezas en menos movimientos.
Su solución no parece muy buena -dijo el señor Lego con desdén.

Tiene usted toda la razón. El algoritmo realiza algunos movimientos bastante tontos, por decirlo de alguna manera. Cuando resuelve usted el rompecabezas, hay ciertos movimientos que nunca haría ¿no es cierto? -pregunté.

Efectivamente, yo nunca haría el cambio [1, 4, 3, 2] --I--> [4, 1, 3, 2]. No tiene sentido. Estamos empeorando la situación.
Es decir, señor Lego, que usted sabe, antes de hacer el cambio, que ese movimiento no le acerca más a la solución. Es un proceso que en Inteligencia Artificial se denomina Heurística y consiste precisamente en eso, en comprobar si el movimiento nos acerca más a la meta o no.
De hecho, cuando el algoritmo de búsqueda encuentra un nodo que sabe que no nos llevará a un buen resultado no sigue explorando por ahí (se da la vuelta). A esta técnica se le denomina Backtracking.
Me senté y modifiqué el programa de la siguiente manera.

backtraking_r_h.py

1. from arbol import Hoja
2.  
3. def buscar_solucion(nodo_inicial, solucion, visitados):
4.     visitados.append(nodo_inicial.get_datos())
5.     if nodo_inicial.get_datos() == solucion:
6.         return nodo_inicial
7.     else:
8.         # expandir nodos sucesores (hijos)
9.         dato_nodo = nodo_inicial.get_datos()
10.         hijo_izquierdo = Hoja([dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]])
11.         hijo_central = Hoja([dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]])
12.         hijo_derecho = Hoja([dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]])
13.         nodo_inicial.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho])
14.  
15.         for nodo_hijo in nodo_inicial.get_hijos():
16.             if (not nodo_hijo.get_datos() in visitados) and heuristica(nodo_inicial, nodo_hijo):
17.                 sol = buscar_solucion(nodo_hijo, solucion, visitados)
18.                 if sol != None:
19.                     return sol
20.  
21.         return None
22.  
23.  
24. def heuristica(nodo_padre, nodo_hijo):
25.     calidad_padre=0
26.     calidad_hijo=0
27.     dato_padre = nodo_padre.get_datos()
28.     dato_hijo = nodo_hijo.get_datos()
29.     for n in range(1,len(dato_padre)):
30.         if (dato_padre[n]>dato_padre[n-1]):
31.             calidad_padre = calidad_padre + 1;
32.         if (dato_hijo[n]>dato_hijo[n-1]):
33.             calidad_hijo = calidad_hijo + 1;
34.  
35.     if calidad_hijo>=calidad_padre:
36.         return True
37.     else:
38.         return False
39.    
40.  
41. if __name__ == "__main__":
42.     print "recursiva con heuristica"
43.     estado_inicial=[4,2,3,1]
44.     solucion=[1,2,3,4]
45.     nodo_solucion = None
46.     visitados=[]
47.  
48.     nodo_inicial = Hoja(estado_inicial)
49.  
50.     nodo = buscar_solucion(nodo_inicial, solucion, visitados)
51.  
52.     # mostrar resultado (al reves)
53.     while nodo.padre != None:
54.         print nodo
55.         nodo = nodo.padre
56.  
57.     print nodo
58.  

¿Ve usted? he añadido una función llamada heurística que comprueba si el nodo hijo nos aleja de la solución en vez de acercarnos a ella. Lo que hacemos es mirar cuántas piezas contiguas hay en el nodo padre y cuántas en el hijo. Si el hijo tiene menos piezas contiguas que el padre, podremos descastar este movimiento. Esta técnica tiene algunos inconvenientes no muy evidentes a simple vista, pero en general es una buena aproximación. Pero ya hablaremos de eso en otro momento.

Tras ejecutar el código obtuvimos el siguiente resultado:

[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]

Mucho mejor -dijo el señor Lego ya no tan sonriente. Pero si hay varias posibles soluciones, ¿cómo podemos saber que ésta es la mejor de todas?

Muy buena pregunta señor Lego. De hecho no podemos saberlo, a no ser que recorramos todo el árbol.

Me senté de nuevo y me puse a teclear los siguientes cambios.

backtracking_r_h_m.py

1. from arbol import Hoja
2.  
3. def buscar_solucion(nodo_inicial, solucion, visitados, nivel):
4.     global mejor_solucion
5.  
6.     visitados.append(nodo_inicial.get_datos())
7.     if nodo_inicial.get_datos() == solucion:
8.         if not mejor_solucion:
9.             mejor_solucion=[nivel,nodo_inicial]
10.         else:
11.             if mejor_solucion[0]>nivel:
12.                 mejor_solucion=[nivel,nodo_inicial]
13.     else:
14.         # expandir nodos sucesores (hijos)
15.         dato_nodo = nodo_inicial.get_datos()
16.         hijo_izquierdo = Hoja([dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]])
17.         hijo_central = Hoja([dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]])
18.         hijo_derecho = Hoja([dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]])
19.         nodo_inicial.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho])
20.  
21.         for nodo_hijo in nodo_inicial.get_hijos():
22.             if (not nodo_hijo.get_datos() in visitados) and heuristica(nodo_inicial, nodo_hijo):
23.                 buscar_solucion(nodo_hijo, solucion, visitados, nivel+1)
24.  
25.  
26.  
27. def heuristica(nodo_padre, nodo_hijo):
28.     calidad_padre=0
29.     calidad_hijo=0
30.     dato_padre = nodo_padre.get_datos()
31.     dato_hijo = nodo_hijo.get_datos()
32.     for n in range(1,len(dato_padre)):
33.         if (dato_padre[n]>dato_padre[n-1]):
34.             calidad_padre = calidad_padre + 1;
35.         if (dato_hijo[n]>dato_hijo[n-1]):
36.             calidad_hijo = calidad_hijo + 1;
37.  
38.     if calidad_hijo>=calidad_padre:
39.         return True
40.     else:
41.         return False
42.    
43.  
44. if __name__ == "__main__":
45.     print "recursiva con heuristica (mejor solucion)"
46.     estado_inicial=[4,2,3,1]
47.     solucion=[1,2,3,4]
48.     nodo_solucion = None
49.     visitados=[]
50.     mejor_solucion=[]
51.  
52.     nodo_inicial = Hoja(estado_inicial)
53.  
54.     buscar_solucion(nodo_inicial, solucion, visitados, 0)
55.  
56.     # mostrar resultado (al reves)
57.     nodo=mejor_solucion[1]
58.     while nodo.padre != None:
59.         print nodo
60.         nodo = nodo.padre
61.  
62.     print nodo
63.  

Fíjese en el cambio señor Lego, ahora, aunque encontremos una solución, no salimos de la función con return, sino que la almacenamos y seguimos buscando. La próxima vez que encuentre una solución, la comparará con la que tiene almacenada y si es mejor, la sustituirá. Así cuando termine el recorrido del árbol, tendremos almacenada la mejor solución de todas.

Pero, ¿cómo sabemos si una solución es mejor que otra? -preguntó el señor Lego.

Para nuestro caso hemos seguido un criterio sencillo. Fíjese que cada vez que llamamos recursivamente a la función buscar_solucion descendemos un nivel en el árbol, es decir, estamos a un salto más de distancia del nodo raíz. Para saber en qué nivel del árbol nos encontramos hemos añadido un nuevo parámetro a la función buscar_solucion llamado nivel. A cada llamada a la función le sumamos uno.
Por lo tanto, la mejor solución será aquella que esté más cerca del nodo raíz, porque es la que tiene menos movimientos. Es decir, la que tenga un nivel más bajo.

Ejecutamos el programa y obtuvimos:

[1, 2, 3, 4]
[2, 1, 3, 4]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]

Fíjese que, en este caso, no se ha mejorado con respecto al algoritmo anterior. Aunque en un árbol más grande seguramente sí que habría habido diferencias.

Entonces es mejor usar siempre esta última implementación ¿no? -Preguntó el señor Lego.

Para nada. Si el árbol fuera más grande el tiempo necesario para recorrerlo entero crece exponencialmente hasta valores de años, siglos o incluso milenios con los ordenadores actuales (y futuros). Es decir, son problemas computacionalmente intratables. Sólo puede usarse en árboles pequeños. Aunque si quiere, otro día hablaremos sobre estrategias para enfrentarse a ese tipo de problemas intratables. Por hoy ya está bien.