Búsqueda Primero el Mejor(Best – First)

Algoritmo:1. Sea L una Lista de nodos iniciales.

2. Sea N el nodo más cercano a la meta (el mejor). Si L está vacía, falla.

3. Si N es la meta. Regrese la trayectoria desde el nodo inicial al nodo N.

4. Si N no es una meta. Buscar los hijos de N, colocarlos en L, etiquetándolos con la trayectoria desde el nodo inicial. Retorne al paso 2.

Búsqueda Primero el Mejor(Best – First)

• La búsqueda primero el mejor es un caso en el cual se seleccionaun nodo para la expansión basada en una función deevaluación f(n).

• Esta función evaluación devuelve un número que sirve pararepresentar lo deseable o indeseable que seria la expansión de unnodo. Se expande primero aquel nodo que tiene mejor evaluación.Se escoge el que parece ser el mejor pero puede no serlo.

• Hay una familia entera de algoritmos de Búsqueda-Primero-Mejor con funciones de evaluación diferentes. Un componente clavede estos algoritmos es una función heurística, denotada h(n):

• h(n) = coste estimado del camino más barato desde el nodo n a unnodo objetivo.

Ejemplo

Un sistema puede encontrarse en un conjunto de estados {S0, …., S8}.Su estado inicial es S0y los estados meta, S7y S8. Considérense lossiguientes operadores 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) = 40 h(S3) = 10 h(S6) = 110h(S1) = 20 h(S4) = 40 h(S7) = 0h(S2) = 20 h(S5) = 100 h(S8) = 0

En este caso la característica deseable para expandir los nodos sebasa en encontrar aquel que tenga el menor 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 nodos

directamente 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 agregan los

nodos directamente unidos

a el. En este caso el único

nodo directamente

conectado es S2.

• Como caso hipotético: si

existiera un nodo S9 con un

valor igual a 40 para la

función heurística el

recorrido debería seguir por

el nodo S2 debido a que es

este el que cuenta con el

valor menor para la función

h(s), que es el criterio

elegido para seleccionar el

nodo por el cual se

continuara con el recorrido.

• Se agrega S3, que es el

único nodo directamente

conectado con S2.

• Nuevamente como caso

hipotético: Si hubiese un

nodo S10 conectado con S2

y el mismo tuviera un valor

igual a 5 para la función

h(s) el recorrido debería

seguir por S10. Como se

menciono anteriormente,

este es un caso hipotético.

• Se agregan los nodos

conectados directamente

con S3. En este caso solo

existe uno el cual es S8.

• Se puede observar que el

valor para la función

heurística h(s) para S8 es

0. Esto quiere decir que S8

es un estado meta.

• Se anota el camino solución

analizando el recorrido

hecho por el algoritmo.

• Al sumar los valores del

coste de los recorridos entre

los nodos se puede conocer

cual es la distancia que

existen entre los mismos.

En este caso la suma seria

10 + 100 + 25 + 5 = 140.

• Se puede observar en la tabla que el nodo S7 también tiene unvalor de 0 para la función h(s). Sin embargo el algoritmo debúsqueda primero el mejor tiene como objetivo encontrar la mejorruta o solución basado en el los valores dados por una funciónheurística que se aplica a cada nodo del recorrido y en este casoesa respuesta esta dada por el camino que lleva hacia el nodo S8.

• A diferencia de los algoritmos de búsqueda no informada, estealgoritmo garantiza que su resultado sea el mas óptimo.

• El valor de una función heurística y los criterios por los cuales seconsidera un valor mejor que otro dependen de cual sea elplanteamiento del problema dado y qué criterios se tengan encuenta para encontrar una meta.