Solución previa

En primer lugar debe estudiarse la solución previa que podréis encontrar en las páginas web de la asignatura. En el problema resuelto una casilla puede moverse de un cuadro A a un cuadro B si A y B son adyacentes y B es la casilla en blanco.

La implementación de la búsqueda A* se ha hecho sobre un grafo de búsqueda. En estas implementaciones normalmente se usan dos listas de nodos:

• ABIERTA. Una lista con los nodos que se han generado y a los que se les ha aplicado la función de evaluación pero todavía no se han expandido.
• CERRADOS. Una lista con los nodos que se ya se han examinado.

Además de la documentación de la solución, el seudocódigo de esta implementación del algoritmo A* puede encontrase en [2] o [3].

En la solución propuesta se han aplicado las siguientes heurísticas:

• h1 = el número de casillas que están en una posición incorrecta.
• h2= la suma de las distancias de las casillas a sus posiciones en las posiciones del estado objetivo. Ya que las casillas no pueden desplazarse en diagonal, la distancia será la suma de distancias horizontal y vertical (suele llamarse a esto distancia Manhattan).