Introducción
• Búsqueda
ciega o no informada (anchura, profundidad): no cuenta con ningún conocimiento sobre
cómo llegar al objetivo.
• Búsqueda
informada: aplicar conocimiento al proceso de búsqueda para hacerlo más
eficiente.
• El
conocimiento vendrá dado por una función que estima la “bondad” de los
estados:
• Dar
preferencia a los estados mejores.
• Ordenando la
cola de ABIERTOS, comparando su bondad estimada.
• Objetivo:
reducir el árbol de búsqueda, ganando eficiencia en la práctica.
Heurística
• Del griego heuriskein,
descubrir: ¡Eureka!
• Según la RAE:
“técnica de la indagación y del descubrimiento”.
• Otro significado:
método para resolver problemas que no garantiza la solución, pero que en
general funciona bien.
• En nuestro
caso, una heurística será una función numérica sobre los estados.
Características:
- Esta función de evaluación se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones más prometedoras.
- No siempre se garantiza encontrar una solución (si existe).
- Esta función de evaluación se utiliza para guiar el proceso haciendo que en cada momento se seleccione el estado o las operaciones más prometedoras.
- No siempre se garantiza encontrar una solución (si existe).
-No siempre se garantiza
encontrar la solución más próxima (la que tenga el número menor de operaciones).
Como por ejemplo:
Búsqueda A*: minimizar el costo
estima total de la solución
La
forma más ampliamente conocida de la búsqueda
primero el mejor se le llama búsqueda A* conocida como “Búsqueda
A-estrella”; la cual evalúa los nodos combinando g(n) y h(n) de la siguiente
manera:
f(n)=g(n)+h(n)
g(n)
significa el coste para alcanzar el nodo; lo que quiere decir que nos da el
coste de camino desde el nodo inicial al nodo n y h(n)=significa el coste de ir
al nodo objetivo, es decir, el coste estimado del camino más barato desde n
hasta el objetivo.
f(n)=coste
más barato estimado de la solución a través de n.
De esta
manera se trata de encontrar la solución más barata y es razonble intentar
primero el nodo con el valor más bajo de g(n).
Cabe
mencionar que esta estrategia resulta ser más que razonable con tal que la
funcion heurística h(n) satisfaga cierta condiciones; la búsqueda A* compleja
como optima, la optimalidad de A* es sencilla de analizar si se usa con la
búsqueda de árboles.
A* es óptima si h(n) es una heurística admisible,
es decir, con tal de que la h(n) nunca sobrestime el coste de alcanzar el objetivo.
Como g(n) es el coste exacto para alcanzar n, tenemos como consecuencia
inmediata que la f(n) nunca sobrestime el coste verdadero de una solución a
través de n. 
En el ejemplo de
la figura, se ha superpuesto una rejilla para estimar distancias. Supóngase que
se quiere determinar el camino óptimo entre A y F. Inicialmente, se toma el
origen y se coloca en la lista Abierta.
El nodo A pasa a
lista cerrada y se pasan a la lista Abierta los conectados con el (B y C),
asignándoles valores R, E y punteros al antecesor (A).
Se selecciona el
de menor valor T de la lista Abierta (B) y se pasa a lista cerrada. Los
conectados con el (D y E) no se pasan a Abierta, pues el valor T es mayor que
los ya existentes.
Se selecciona el
de menor valor T de la lista Abierta (D) y se pasa a lista cerrada. Sólo se
pasa el nodo F a Abierta, pues B está ya en cerrada.
Búsqueda IDA*
Es de tipo de algoritmos de búsqueda
heurística con limitación de memoria. Los más utilizados son el IDA* (Iterative
Deepening A*), y SMA* (Simplified memory A*).
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.
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 en su
funcionamiento no realiza un control estricto de la memoria.
Características
de IDA*
IDA* es un método de búsqueda completo
y óptimo, lo que quiere decir que siempre encuentra una solución si es que ésta
existe y además garantiza encontrar la mejor solución de entre todas las
posibles.
Este método tiene las mismas ventajas y
desventajas que A*, excepto en lo referente al coste espacial. En este aspecto
IDA* presenta notables ventajas ya que únicamente necesita un espacio
proporcional a la longitud de la ruta más larga que se explore.
Esta limitación en el uso de la
memoria resulta beneficiosa pero también tiene sus desventajas, ya que al
convertir la búsqueda de la solución en un proceso iterativo expandiremos
varias veces los mismos nodos. Esto es algo muy a tener en cuenta, ya que
dependiendo de las características de los problemas a resolver obtendremos
mejores o peores prestaciones.
En el mejor caso el coste temporal de
IDA* puede ser muy similar al de A*, e incluso menor, ya que al ser un
algoritmo simple y no necesitar de inserciones, borrados y reordenamientos en
listas de prioridades tiene una menor sobrecarga por nodo. Este mejor caso
ocurrirá cuando tengamos un problema en el que las heurísticas adopten valores
aproximados al coste real desde el comienzo de la ejecución, ya que entonces se
realizarán pocas iteraciones, expandiendo además pocos nodos en las iteraciones
iniciales. Podemos asociar este caso con el problema del 8-puzzle cuando se usa
la heurística de distancias.
En el peor caso el coste temporal de
IDA* se acerca al de un algoritmo de profundización iterativa habitual como el
IDS (Iterative Deepening Search), es decir, en cada iteración se profundiza
únicamente un nivel más en el árbol. Esto ocurre en problemas en los que los
valores heurísticos son poco acertados, lo que provoca que en cada iteración
aumentemos el contorno en sólo uno o dos niveles.
Como por ejemplo:
Conclusión
Por lo visto en este
capítulo podemos concluir que la
utilización de métodos de búsqueda respaldados con información, presenta nuevos
problemas para la elección del método de búsqueda mas adecuado para un
problema, ya que, no solo debemos tener en cuenta el método de búsqueda sino que también se
debe confeccionar correctamente una heurística eficiente.
El valor devuelto debe
resultar útil y correcto ya que, aunque eligiéramos el mejor método si la
heurística falla podríamos no arribar a la solución.
También podemos concluir que en
algunos casos se pueden combinar métodos de búsqueda para así llegar a una
función óptima.
No hay comentarios:
Publicar un comentario