El problema del n-Puzzle
Algoritmos de búsqueda utilizados.
Caracterización del Algoritmo DFID.
El algoritmo de búsqueda DFID (Depth-First Iterative-Deepening)
fue introducido por primera vez en el año 1977 cuando Slate y Atkin
presentaron un programa de ajedrez. El algoritmo combina las ventajas de
la búsqueda en anchura y de la búsqueda en profundidad. De
la primera guarda el concepto de encontrar la solución siempre
a la menor profundidad, mientras que de la segunda conserva el estilo de
búsqueda con lo cual asegura que su necesidad de memoria será
lineal. Para asegurar la completud del algoritmo, el DFID introduce un
límite de profundidad en cada una de sus iteraciones. El desarrollo
del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda
limitada en profundidad. Si en dicha iteración no se alcanza la
solución óptima, entonces se incrementa dicho límite
en una unidad de profundidad y se vuelve a realizar la búsqueda.
Caracterización del Algoritmo A*.
Un algoritmo de búsqueda por el mejor nodo combina las características
de los métodos en anchura y en profundidad. Se caracteriza porque
para cada nodo se generan todos los posibles sucesores y de estos sólo
se expande aquel que sea más prometedor después de la aplicación
sobre ellos de una función heurística h(n) que estima
el coste del camino desde cada nodo al objetivo. El uso de este tipo de
algoritmo, al minimizar el coste estimado hasta el objetivo, disminuye
considerablemente el coste de la búsqueda. Desafortunadamente, no
es ni óptimo ni completo.
Por otra parte, la búsqueda de coste uniforme minimiza el coste
del camino hasta el nodo, g(n) , es decir, expande para cada conjunto
de sucesores aquel cuyo camino desde el nodo raíz tenga un menor
coste. Este es un algoritmo óptimo y completo, pero puede ser muy
ineficiente.
Sería bueno poder combinar estas dos estrategias para conseguir
las ventajas de ambos. Afortunadamente, podemos hacer eso exactamente,
combinando las dos funciones de evaluación simplemente sumándolas:
Ya que g(n) proporciona el coste del camino desde el nodo de
inicio hasta el nodo n, y h(n) es el coste estimado del camino de
menos coste desde n hasta el objetivo, f(n) es el coste estimado
de la solución de menor coste que atraviesa el nodo n.
Si se intenta encontrar la solución de menor coste, es razonable
intentar primero el nodo con el menor valor de f. Lo bueno de esta
estrategia, es que es más que razonable. Se puede comprobar que
es completa y óptima, dando una simple restricción de la
función h.
La restricción es escoger una función h que nunca
sobreestime el coste para alcanzar el objetivo. Una función h
de este tipo es una heurística admisible.
A este algoritmo se le conoce con el nombre de A*.
Caracterización del Algoritmo IDA*.
El IDA* (Iterative-Deepening A*) es al igual que el DFID un algoritmo basado
en la profundización iterativa. La única diferencia entre
ambos algoritmos estriba en que mientras el DFID se basa en la profundidad
para cada una de sus iteraciones, el IDA se basa en la información
heurística que posee para determinar el siguiente límite
de la iteración. El tratamiento de esa información se realiza
de igual forma que en el algoritmo del A*, o sea mediante la función
de evaluación f introducida anteriormente. El funcionamiento
del algoritmo es el siguiente:
En cada iteración el algoritmo realiza una búsqueda
en profundidad hasta donde se lo permita su límite de coste. Cada
vez que se visita todo el grafo de búsqueda contenido dentro de
ese límite sin hallar la solución entonces, el algoritmo
incrementa el límite de coste. Ese nuevo límite viene dado
por el menor de los límites de corte, o sea, por el menor valor
del coste de los nodos que tenían un valor superior en la anterior
iteración.
Como señalamos anteriormente, este algoritmo se considera limitado
en profundidad, aunque esta afirmación no sea estrictamente cierta.
La razón de ello viene dado por su eficacia en cuanto al uso de
memoria pero como se puede ver de su funcionamiento no realiza un control
estricto de la memoria.
Caracterización del Algoritmo SMA*.
El SMA* (Simplified Memory-bounded A*) aparece en cierta medida debido
a los problemas del IDA* en espacios reducidos de memoria. Al contrario
de éste, el SMA* realiza un control estricto de la memoria, delimitando
desde un principio el máximo de memoria de la que dispone. En cambio,
la implementación de éste resulta muy dificultosa.
La documentación continúa con la descripción de
las funciones heurísticas utilizadas.
Vuelta al índice de la documentación.