BUSQUEDA PRIMERO EL MEJOR

Búsqueda Primero el Mejor
(Best – First)
• La búsqueda primero el mejor es un caso en el cual se selecciona
un nodo para la expansión basada en una función de
evaluación f(n).
• Esta funciónevaluación devuelve un número que sirve para
representar lo deseable o indeseable que seria la expansión de un
nodo. Se expande primero aquel nodo que tiene mejor evaluación.
Se escoge el que pareceser el mejor pero puede no serlo.
• Hay una familia entera de algoritmos de Búsqueda-PrimeroMejor con funciones de evaluación diferentes. Un componente clave
de estos algoritmos es una funciónheurística, denotada h(n):
• h(n) = coste estimado del camino más barato desde el nodo n a un
nodo objetivo.

•A diferencia de los algoritmos de
búsqueda no informada, este algoritmo
garantiza que suresultado sea el mas
óptimo.

Ejemplo
Un sistema puede encontrarse en un conjunto de estados {S0, …., S8}.
Su estado inicial es S0y los estados meta, S7y S8. Considérense los
siguientesoperadores y costes asociados a cada operador:
OP1: S3→S8(coste 5) OP2: S2→S3(coste 25) OP3: S5→S3(coste 20)
OP4: S1→S2(coste 100) OP5: S4→S2(coste 80) OP6: S6→S7(coste 100)
OP7: S0→S1(coste 10) OP8:S0→S4(coste 10) OP9: S0→S5(coste 20)
OP10: S0→S6(coste 20)

Considérense también los siguientes valores de la función heurística h,
que estima el menor coste desde cada nodo a un nodo meta:
h(S0) = 40h(S3) = 10 h(S6) = 110
h(S1) = 20 h(S4) = 40 h(S7) = 0
h(S2) = 20 h(S5) = 100 h(S8) = 0

En este caso la característica deseable para expandir los nodos se
basa en encontrar aquel que tenga elmenor valor para la función h(s).

• Se tiene como nodo inicial
S0 y se observa que los
nodos
que
están
directamente
conectados
con el son S1, S4, S5 y S6.

• Se expanden los nodosdirectamente
conectados
con S0 y se observan sus
valores para la función
heurística.
• El nodo con menor valor
para la función heurística es
S1.

• El recorrido continua por el
nodo S1 y se...