Busqueda Informada

Búsqueda Informada
Juan Carlos Ruiz González

Búsqueda Informada
La que utiliza el conocimiento específico del
problema más allá de la definición del
problema en sí mismo.

Búsqueda informada(heurística)
– La heurística aparece bajo la forma de una función de
evaluación basada en la información específica para el
dominio o contexto relacionada con el problema
– El problema de búsqueda se puedeconsiderar como la
maximización o minimización de una función, como es del
todo general

Búsqueda informada (heurística)
– La función de evaluación nos proporciona una manera de
evaluar un nodo“localmente” basado en una estimación del
costo de llegar desde el nodo al nodo meta.
Problemas con la Heurística
– La heurística suele ser poco certera - problema abierto
– Valor de la actividad a unmeta-nivel - problema abierto
– Puede no encontrar la mejor respuesta - superado por
algoritmo A*

Estrategias de búsqueda informada (heurística)
●
●
●
●

Primero el mejor.
Búsqueda A*.
Búsqueda heurísticacon memoria acotada.
Aprende a Buscar Mejor.

Búsqueda Voraz
La búsqueda voraz (primero el mejor) trata de
expandir el modo más cercano al objetivo
alegando que probablemente conduzca
rápidamente auna solución. Así, evalúa los
nodos utilizando solamente la función
heurística f(n)=h(n).

Algoritmo
El algoritmo requiere el uso de dos listas:
Abiertos: contiene aquellos nodos que ya han
sidoevaluados, pero cuyos descendientes aun
no han sido generados. Esta lista es una
lista con prioridad.

Algoritmo
Cerrados: contiene aquellos nodos que ya han
sido evaluados y sus descendientes hansido
generados.

Algoritmo
El algoritmo busca el mejor nodo en Abiertos y lo
expande generando a sus descendientes, los cuales a su
vez son evaluados e insertados en Abiertos. La lista
Cerrados permitellevar un control de los estados
repetidos y determinar la mejor ruta para llegar a ellos

Algoritmo
1.
2.

Comenzar con una lista ABIERTOS conteniendo sólo al estado inicial y otra
lista...