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:

f(n) = g(n) + h(n).

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