Introducción

Se trata de analizar una solución al problema del 8-puzzle mediante técnicas de busqueda heurística que encontrareis en las páginas web de la asignatura y de implementar algunas variantes sencillas. El objeto del puzzle es mover las casillas sobre el espacio vacío (o casilla en blanco) partiendo de la configuración inicial hasta llegar a la configuración final.

Un algoritmo general de búsqueda puede ilustrarse a partir del seudocódigo siguiente [1]:

 B<>function BUSQUEDA-GENERAL (problema, FN-INS-COLA)

		 returns solucion o fallo

		 nodos      (CREA-COLA  (CREA-NODO(ESTADO-INICIAL  problema  ))

		 loop B<>if nodos vacio then return fallo

			 		 nodo      EXTRAE-FRENTE-COLA(nodos)

			 		 if FN-TEST-OBJETIVO(ESTADO(nodo))==exito

				 		 		 then return nodo o camino

 		 		 nodos      FN-INS-COLA(nodos,EXPANDIR(nodo,OPERADORES    problema   ))

		 end loop

La investigación en el campo de búsqueda en IA se ha centrado en buscar la estrategia correcta para un problema y en la evaluación de ésta en términos de completud, optimalidad, complejidad espacial y complejidad temporal.

Los métodos de búsqueda no informada o búsqueda ciega son aquellos en los que no hay información acerca del número de pasos o del coste del camino para ir del estado inicial al objetivo. Lo único que se conoce es la forma de distinguir un estado objetivo de uno que no lo es. Estas estrategias suelen distinguirse por el orden en el que se expanden los nodos y puede adaptarse el algoritmo general anterior por medio de la FN-INS-COLA adecuada. Así si la forma de insertar los elementos en la cola de nodos es por el final FN-INS-FINAL-COLA tendremos una búsqueda en anchura, si fuese por el principio FN-INS-PRINCIPIO-COLA tendríamos una búsqueda en profundidad.

Los métodos de búsqueda informada utilizan una función de evaluación que ordena los nodos de la cola. Si g(n) nos da el coste del camino del nodo inicial al nodo n y h(n) nos da una estimación del coste del mejor camino del nodo n al objetivo, f(n)=g(n)+h(n) nos da una estimación del coste del mejor camino a través de n. La búsqueda conocida como A* o diatáxica, objeto de esta práctica, utiliza f como función de evaluación:

 B<>function BUSQUEDA-A* (problema) returns solucion o fallo

FN-INS-COLA    una funcion que ordena los nodos por medio de f=g+h

B<>return BUSQUEDA-GENERAL(problema, FN-INS-COLA)