Comparación de Estrategias de Búsqueda Admisibles y

ε-Admisibles para el problema del 8-puzzle

Miguel Álvarez Álvarez

Inteligencia Artificial. 4º de Ingeniería Informática.

EPSIG. Universidad de Oviedo. Campus de Viesques. E-33271 Gijón.

Resumen. El objetivo de este documento consiste en realizar un estudio

comparativo de diversas estrategias de búsqueda heurística aplicadas sobre el
problema del 8-puzzle. En concreto, se considerará el algoritmo A* y se
analizará su comportamiento para los heurísticos más habituales.
Posteriormente se incluirán las estrategias ε-admisibles de ponderación estática,
ponderación dinámica y Aε*. El estudio se centrará en comprobar el desempeño
de estos algoritmos comparándolos con el A* original en función de diversos
valores de ε. Para ello se tomará como referencia un banco determinado de
ejemplos y se empleará un mismo heurístico como estándar para las cuatro
estrategias.

Palabras Clave: 8-puzzle, Algoritmo A*, búsqueda heurística, ε–admisible.

1 Introducción

Para llevar a cabo el estudio se recurre al conocido problema del 8-puzzle puesto que
constituye uno de los ejemplos típicos de uso en la Inteligencia Artificial, entre otras
razones porque partiendo de un estado inicial lo que se pretende es llegar siempre a un
mismo y único estado final.

El 8-puzzle es un tablero de 3x3 que está constituido por ocho fichas numeradas (del
1 al 8) y un hueco vacío que permite llevar a cabo los movimientos de las fichas para
alcanzar el objetivo. Estos movimientos se encuentran sujetos a una serie de
restricciones que se detallarán en el capítulo siguiente.
 Figura 1. Estado final

2 Planteamiento del problema

Se pretende que partiendo de un estado inicial, es decir, una situación determinada del
tablero se llegue con un número de movimientos mínimo al estado final mostrado en
la figura anterior. En cada movimiento se permite desplazar una única ficha y sólo se
autorizan aquellos realizados entre casillas que cumplan las siguientes restricciones:

1. Las casillas deben ser adyacentes.

2. Las casillas deben estar en la misma fila o en la misma columna, es decir, ser
ortogonales.
3. La casilla destino debe estar vacía.

A través de un banco de ejemplos utilizado para el estudio y que se compone de

un total de 40 con diversos costes, entendiendo por coste el número de movimientos
mínimo necesarios para ir del estado inicial al final, se lleva a cabo tanto el análisis de
A* con los heurísticos h0, h1, h2 y h3, es decir, mismo algoritmo pero distintos
heurísticos; como la comparación entre éste y las estrategias ε-admisibles de
ponderación estática, ponderación dinámica y Aε*. En este otro caso los algoritmos
varían ligeramente respecto al A* original pero se emplea el mismo heurístico para
compararlos entre sí (h2).
3 Métodos de resolución

3.1 Algoritmo A*

El algoritmo A* se enmarca en el grupo de los algoritmos de búsqueda en grafos y

constituye una especialización del BF. Bajo determinadas condiciones encuentra el
camino de menor coste existente entre un estado inicial y uno objetivo.
La principal característica de este algoritmo y que lo diferencia de los algoritmos
voraces o del BF es el hecho de que éste explora estados teniendo en cuenta aquellos
que resultan más prometedores para alcanzar la solución final desde un estado
intermedio, combinado con el coste que ha supuesto llegar desde el estado inicial
hasta ese intermedio.
La función de evaluación es la siguiente:
f(n)=g(n)+h(n)
Donde g(n) es el coste del mejor camino desde el inicial hasta n y h(n) supone una
estimación positiva del coste del camino más corto desde n al objetivo.
El algoritmo A* empleado presenta la siguiente estructura:

ABIERTA = (inicial);
Mientras NoVacia(ABIERTA) hacer
N = ExtraePrimero(ABIERTA);
Si EsObjetivo(n) entonces
Devuelve Camino(inicial, n) y para;
Fin si
S=Sucesores(n);
Añade S a la entrada de n en la TABLA_A;
Para cada q de S hacer
Si (q Є TABLA_A) entonces
Rectificar(q, n, Coste(n,q));
Ordenar(ABIERTA); {si es necesario}
Si no
Pone q en la TABLA_A con
Anterior(q) = n;
G(p) = g(n) + Coste(n, q);
H(q) = Heuristico(q);
ABIERTA = Mezclar(q, ABIERTA);
Fin si
Fin para
Fin mientras
Devuelve “no solucion”;

Figura 2. Algoritmo A*
 La lista ABIERTA contiene los estados candidatos a ser expandidos y se encuentra
ordenada por menor valor de f, es decir, con los estados más prometedores al
principio.
Se complementa con TABLA_A que contiene para un determinado estado, su padre,
el valor de g(n) y h(n) y TABLA_G que almacena los sucesores de ese estado y sus
costes.

3.1.1 Función heurística

Una función heurística establece una medida de lo prometedor que puede ser un nodo
para ser expandido camino a la solución final. A lo largo del estudio se emplean
varios heurísticos obtenidos a través de diversos razonamientos y que por tanto
presentan comportamientos diferentes. El primero de ellos es el heurístico trivial h0
que siempre devuelve 0.
Posteriormente h1 y h2 se obtienen de manera sistemática prescindiendo de
restricciones asociadas al problema (en esta ocasión tres, presentadas en el capítulo
anterior). En el primer caso prescindiendo de todas ellas se obtiene h1 que mueve una
ficha directamente a su posición en el objetivo. Eliminando la última restricción, es
decir, que la casilla deba estar vacía se obtiene h2 llevando a la ficha al objetivo a
través de movimientos entre casillas adyacentes ortogonalmente, siempre buscando el
coste mínimo.
El heurístico h3 no proviene a priori de eliminar condiciones del problema y lo que
hace es multiplicar por dos al número de fichas que se encuentren a una distancia
ortogonal dos de su posición en el objetivo.
Tanto h1 como h2 son heurísticos son monótonos y por tanto admisibles, por ser
obtenidos a través de simplificaciones del problema (prescindiendo de condiciones).
Sin embargo h3 no es monótono pero si admisible.
Por último se considera otro heurístico en el estudio utilizado en el algoritmo Aε*
y etiquetado como h4, que devuelve el mínimo de las distancias pero penalizadas
ligeramente por si acaso se debe realizar algún movimiento adicional. Si una ficha
está a distancia 1 ó 2 devuelve ese mismo valor pero si se encuentra a distancia 3 ó 4
devuelve 4 y 6 respectivamente.

3.2 Estrategias ε-admisibles

Constituyen algoritmos que sacrifican el hecho de obtener una solución óptima para
lograr mejorar el rendimiento del proceso pero sin desviarse en exceso del óptimo.
Este hecho se controla a través de ε que mide la distancia máxima al coste óptimo.

3.2.1 Ponderación estática

Es una variación del algoritmo A* que concretamente modifica la función de

evaluación f:
f(n) = g(n) + (1 + ε)h(n), ε Є [0,1]
 Pretende acelerar la búsqueda de la solución tratando de evitar que se expandan
todos los nodos del espacio de búsqueda.

3.2.2 Ponderación dinámica

Este algoritmo también modifica la función f pero a diferencia de la estrategia anterior

la ponderación varía dinámicamente en función del estado del problema en el que nos
encontremos:
f(n) = g(n) + h(n) + ε (1 – d(n)/N)h(n)

Se añade d(n) como la profundidad del nodo n y N que es una cota superior de la
profundidad de la mejor solución.

3.2.3 Algoritmo Aε*

Este algoritmo a diferencia de los anteriores no modifica f sino que añade a ABIERTA
una sublista llamada FOCAL:
FOCAL = {n Є ABIERTA/ f(n) <= (1+ ε)min(f(n’), n’ Є ABIERTA)}

Esta sublista se ordena colocando los nodos más prometedores (menor valor) al
principio de acuerdo con el criterio otorgado por el heurístico h4 presentado con
anterioridad. Una vez escogido un n de FOCAL deberá de eliminarse también de la
lista ABIERTA.

4 Diseño del estudio experimental

El estudio experimental se divide en dos partes, una primera parte que ejecuta el
algoritmo A* con los diversos heurísticos y una segunda parte en la que se trabajan
las estrategias ε-admisibles con h2 como ya se indicó anteriormente.

Para aplicar el algoritmo A* se ejecuta primeramente el fichero prueba.lsp que

carga los principales ficheros del problema:

(load "tabla-g.lsp")
(load "tabla-a.lsp")
(load "objetivo.lsp")
(load "fich-obj.lsp")
(load "inicial.lsp")
(load "fich-res.lsp")
(load "abierta.lsp")
(load "grafo.lsp")
(load "heuris-0.lsp")
 (load "aestrela.lsp"))

Figura 3. Fichero prueba.lsp para A* con h0

A continuación se ejecuta el fichero aestrela.lsp que lanza el algoritmo tras

indicarle un estado inicial y donde se quiere guardar la solución obtenida:

(a+)
fichero del estado inicial: estadoin.lsp
fichero de resultados: …

Figura 4. Lanzamiento del algoritmo A*

El estado inicial se corresponde con uno de los ejemplos de la batería de pruebas

que se encuentra agrupada en cuatro bloques de costes 5, 10, 15 y 20 con diez
ejemplos cada uno. El fichero de resultados almacena el número de nodos generados,
expandidos y el camino seguido desde el estado inicial hasta el final así como el coste
del problema (que puede no coincidir con el coste que señala la batería de pruebas si
el camino seguido hasta la solución no es óptimo).
Para cambiar el heurístico basta con cargar (mediante load) el fichero que contenga
el heurístico requerido o bien cambiarlo manualmente cuando se carga prueba.lsp.
Para los algoritmos de ponderación dinámica y estática se procede de manera
similar pero cargando el fichero que contiene la implementación de A* con los
cambios requeridos. En este caso el heurístico permanece constante y lo que se hace
es experimentar con diversos valores de ε, admitiendo una relativa distancia a la
solución óptima. En concreto se experimenta con 0.5, 1 y 2.
Por último en el caso de Aε* se modificará el fichero que contiene la
implementación de ABIERTA y además se añadirá a prueba.lsp la carga del fichero
que contiene el heurístico h4. Por lo demás la experimentación es similar a la de los
otros algoritmos ε-admisibles.
Los resultados arrojados por los ficheros de resultados de las distintas pruebas
constituyen la base para el estudio.

5 Análisis de resultados

En primer lugar en la comparación de heurísticos con el algoritmo A* se han obtenido

los siguientes resultados:
 h0 h1 h2 h3

NG NE NG NE NG NE NG NE

Coste 5 84,11 48,78 11,89 5,33 11,43 5,00 84,11 48,78

Coste 10 1056,60 658,90 49,80 26,80 21,63 10,75 1056,60 658,90
Coste 15 11067,00 7181,33 499,70 296,50 78,13 44,25 11067,00 7181,33
Coste 20 4519,80 2777,20 347,10 209,90

Figura 5. Tabla de nodos generados y expandidos por los diversos heurísticos

Figura 6. Gráficas de nodos generados y expandidos para los ejemplos de coste 10

Analizando los datos de la tabla y las gráficas se comprueba que el rendimiento

tanto del heurístico h0 como del h3 (se solapan en las gráficas) resulta bastante pobre,
puesto que la cantidad de nodos generados y expandidos resulta elevada para todos
los costes, de hecho los ejercicios de coste 20 no se reflejan por el elevado tiempo de
ejecución que requerían.
Por otro lado el comportamiento de h1 mejora sustancialmente a los anteriores pero
quien mejor resuelve el problema del 8-puzzle es h2 puesto que es el que mejor
estima el coste a la solución óptima.

En la segunda parte del estudio se muestran los resultados obtenidos con los
algoritmos ε-admisibles. Para ilustrar su comportamiento se ha recurrido
principalmente a los ejemplos de coste 20 ya que tras realizar las mediciones se han
erigido como los más representativos.
Las resultados obtenidos con el algoritmo de ponderación estática se resumen en
las siguientes gráficas:
Figura 7. Gráficas del algoritmo de ponderación estática para coste 20

El valor ε= 0 responde al funcionamiento del algoritmo A* puesto que no presenta

distancia alguna respecto de la solución óptima. De los datos obtenidos en la primera
gráfica se comprueba como el valor de ε que menos nodos genera y expande es 1
seguido de 0.5 y posteriormente 2 ; todos ellos mejorando a A* pero a costa de
aumentar el coste del problema como se desprende de la segunda gráfica.

Para el algoritmo de ponderación dinámica se han obtenido los siguientes

resultados:

Figura 8. Gráficas del algoritmo de ponderación dinámica para coste 20

De la información aparecida en las gráficas se observa como este algoritmo presenta

un comportamiento parecido en términos globales al de ponderación estática. La
diferencia radica en el hecho de que tanto ε: 0.5 y 1 obtienen resultados similares en
cuanto a nodos generados y expandidos, pero este detalle puede ser una coincidencia
de los ejemplos seleccionados para ilustrar la gráfica.

Por último se presentan los resultados conseguidos con el algoritmo Aε*:

Figura 9. Gráficas del algoritmo Aε* para coste 10

En este caso se muestran los valores obtenidos para los problemas de coste 10
donde el valor 2 para la ε consigue resultados similares a A*. Se han ilustrado los
ejemplos relativos al coste 10 puesto que los de coste 15 mostraban unos resultados
muy pobres para ε=1 y un tiempo de ejecución excesivo para ε=2. En cuanto a los
ejemplos de coste 20 apenas se ejecutan y con resultados muy discretos (nodos
generados=1347 y expandidos=821) para ε=0.5 no alcanzando tiempos de ejecución
verificables para el resto de valores de ε. Por ello este algoritmo no se puede comparar
en las mismas condiciones con el resto de algoritmos ε-admisibles ni con A* puesto
que no es capaz de resolver en tiempo prudencial ejercicios con ciertos niveles de
dificultad.

6 Conclusiones

Se ha analizado el algoritmo A* para diversos heurísticos tras lo cual se ha

comprobado que el heurístico h2 presenta los mejores resultados debido a que es el
que más informado se encuentra de todos ellos. Del resto de heurísticos h1 obtiene
resultados discretos pero al menos consigue resolver todos los problemas planteados
en la batería de pruebas, hecho no superado por los h0 y h3 que no han podido
resolver problemas de coste 20 en tiempo prudencial.
En la segunda parte del estudio las estrategias ε-admisibles analizadas bajo el
heurístico h2, debido como se acaba de comentar a erigirse como el mejor de los
heurísticos estudiados, han corroborado que son capaces de generar y expandir menos
nodos que A* a costa de sacrificar ligeramente precisión en la solución y en ocasiones
velocidad de ejecución.
En concreto los mejores resultados de estos algoritmos se sitúan alrededor de los
valores 0.5 y 1 para ε, tanto en ponderación dinámica como estática. En términos
generales la mejor medición obtenida se consigue con ponderación dinámica y ε=1.
En cuanto a Aε* no ha sido capaz de superar problemas de cierta entidad por lo que
no se considera un algoritmo adecuado para resolver este tipo de problemas.
En resumen, las estrategias ε-admisibles (a excepción de Aε*) se han revelado bajo
determinadas circunstancias como un instrumento de uso en Inteligencia Artificial
capaz de lograr soluciones correctas y con un buen nivel de efectividad para
problemas del tipo del 8-puzzle.
7 Bibliografía

1. Thayer, J. T. and Ruml, W Faster than Weighted A*: An Optimistic Approach to Bounded
Suboptimal Searvh. Proceedings of the ICAPS 2008, pp.355-362.
2. J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading,
MA: Addison-Wesley, 1984.
3. Apuntes Inteligencia Artificial 2008-09, Tema: “Introducción a los sistemas de búsqueda”.
4. Apuntes Inteligencia Artificial 2008-09, Tema: “Técnicas de Búsqueda heurística”.