El problema del n-Puzzle


 

Caracterización de las búsquedas ciegas.

La búsqueda ciega o no informada sólo utiliza información acerca de si un estado es o no objetivo para guiar su procesu de búsqueda.

Los métodos de búsqueda ciega se pueden clasificar en dos grupos básicos:

Son procedimientos de búsqueda nivel a nivel. Para cada uno de los nodos de un nivel se aplican todos los posibles operadores y no se expande ningún nodo de un nivel antes de haber expandido todos los del nivel anterior. En estos procedimientos se realiza la búsqueda por una sola rama del árbol hasta encontrar una solución o hasta que se tome la decisión de terminar la búsqueda por esa dirección ( por no haber posibles operadores que aplicar sobre el nodo hoja o por haber alcanzado un nivel de profundidad muy grande ) . Si esto ocurre se produce una vuelta atrás ( backtracking ) y se sigue por otra rama hasta visitar todas las ramas del árbol si es necesario. A partir de los dos tipos de búsqueda anteriores surgió uno nuevo, llamado método de búsqueda por profundización iterativa. El algoritmo de búsqueda más representativo de esta nueva tendencia es el DFID acrónimo de su nombre en inglés (Depth-First Iterative-Deepening).
 

 

Caracterización de las búsquedas heurísticas.
 
Las técnicas de búsqueda heurística se apoyan al contrario de los métodos de búsqueda ciega se apoyan en información adicional para realizar su proceso de búsqueda. Para mejorar la eficiencia de la búsqueda, estos algoritmos hacen uso de una función que realiza una predicción del coste necesario para alcanzar la solución. La función que guía el proceso toma el nombre de función heurística.

De todos los algoritmos de búsqueda heurística, uno destaca en especial: el A*. Este algoritmo, a pesar de haber sido creado entorno a los años 60, sigue en la actualidad siendo uno de los mas utilizados. Desafortunadamente, es ineficiente en cuanto al uso de memoria durante el proceso de búsqueda. Por ello, en las décadas de los 80 y 90, aparecieron algoritmos basados en el propio A*, pero que limitaban el uso de memoria. Dos de los algoritmos más representativos de esta última tendencia son el IDA* (Iterative-Deepening A*) y el SMA* (Simplified Memory-bounded A*).

La documentación sigue con la descripción de los algoritmos de búsqueda utilizados.

Vuelta al índice de la documentación.