Introducción 1

Def: Una función heurística h es optimista o admisible si h(n) h*(n) para todo nodo n, donde h*(n) es el verdadero costo del nodo n al nodo meta mas cercano.

Def: Se dice que una heurística h es consistente si para todo nodo ni y todo sucesor nk de ni se cumple que

h(ni) – h(nk) c(ni, nk)

ni

nk

C(ni, nk)

nmeta

h(nk)

h(ni) – h(nk)

h(ni)

Introducción 2

Observaciones

1.- h* : N R mide el costo real desde el nodo n al nodo meta más cercano

2.- h : N R es una función heurística que estima el valor de h*

3.- h estima también implícitamente el costo de cada operador

4.- h es consistente si subestima el costo de todos los operadores

5.- Si h es consistente, entonces también es optimista o admisible

6.- Existen funciones h optimistas que no son consistentes.

Introducción 3

C

A

D

FE

4

7

3

4

3

B

Ejemplo de heurística no admisible

El grafo que se muestra en la figura describe un problema de búsqueda. Suponga que A es el estado inicial y que F y E son estados meta. Los arcos están etiquetados con el costo real de los operadores

La función heurística h, está dada por

Nodo A B C D E F

h 8 6 6 5 0 0

Introducción 4

Se pide:

a) Desarrollar el árbol de búsqueda que genera el algoritmo A*. Indique el orden en que se expanden los nodos. ¿Cuál de los nodos meta se encuentra primero?

b) ¿La función heurística es consistente y/u optimista? Argumente su respuesta.

c) Asigne los valores del costo real de los operadores y de la función heurística h, de modo que ésta resulte ser optimista (admisible) y no consistente.

d) Desarrolle el árbol de búsqueda que genera el algoritmo A*. ¿Es el algoritmo A* óptimo en este caso?

Solución

En el primer paso, se expande el estado A a los estados B y C

A

B

f= 0 + 8=8

4 3

f= 4 + 6=10C

f= 3 + 6 = 9

Introducción 5

A

B C

f= 0 + 8=8

4 3

f= 4 + 6=10f= 3 + 6 = 9

En segundo paso, se expande el estado C, que tiene un menor valor de la función de evaluación f, que el valor del nodo B

4

Df= 7 + 5=12

En el tercer paso , se expande el estado B, que tiene el menor valor de la función de evaluación f que el valor del estado D, y se llega al estado meta F

Introducción 6

A

B C

f= 0 + 8=8

4 3

f= 4 + 6=10f= 3 + 6 = 9

4

Df= 7 + 5=12

F

7

f= 11 + 0=11

El estado meta que se encuentra primero es el estado F, cuyo costo es 11. El costo del estado meta E es de 10, y por lo tanto en este caso A* no es óptimo

Introducción 7

b) ¿La función heurística h es consistente y/o optimista (admisible)?. Argumente su respuesta

La función heurística h no es consistente, porque no subestima el costo real del operador que lleva del estado D al estado E:

h(D) – h(E) = 5 – 0 = 5 > c(D,E) = 3

Además no es optimista (o admisible) porque no subestima el costo real para llegar desde el estado D al estado meta E:

h(D) = 5 > h*(D) = 3

Introducción 8

c) Asigne los valores del costo real de los operadores y de la función heurística h, de modo que ésta resulte ser optimista (admisible) y no consistente.

Una posible solución sería asignar como costos reales los mismos costos que en la red dada

C

A

D

FE

4

7

3

4

3

B

y como función heurística h , la siguiente

A B C D E F

h 8 6 6 1 0 0

Introducción 9

Con estos valores se cumple que la función heurística h es optimista (admisible), ya que

h(n) h*(n) n

Pero no es consistente, ya que según la definición debería cumplir que

h(ni) - h(nj) c(ni , nj)

Y en este ejemplo, para los nodos C y D no se cumple

h(C) - h(D) =6 – 1=5 / c(C, D) = 4

c) Desarrolle el árbol de búsqueda que genera el algoritmo A*. ¿Es el algoritmo A* óptimo en este caso?

Introducción 10

En el primer paso , se expande el estado A a B y C

34

A

BC

f= 0 + 8=8

f= 4 + 6 = 10f= 3 + 7 = 10

En el segundo paso se expande el estado B que tiene un valor de la función de evaluación f igual que el valor de f en estado C, pero B tiene un menor valor de la función heurística.

34

B C

f= 0 + 8=8

f= 4 + 6 = 10f= 3 + 7 = 10

A

F f=11 + 0 = 11

Introducción 11

34

B C

f= 0 + 8=8

f= 4 + 6 = 10f= 3 + 7 = 10

A

Ff=11 + 0 = 11

34

BC

f= 0 + 8=8

f= 4 + 6 = 10f= 3 + 7 = 10

A

Ff=11 + 0 = 11

En el tercer paso, se expande el estado C, que tiene un valor de la función de evaluación f menor que el valor de f en el nodo F, por lo tanto el estado meta F no se comprueba todavía

Df= 7 + 2 = 9

7

74

Introducción 12

34

B C

f= 0 + 8=8

f= 4 + 6 = 10f= 3 + 7 = 10

A

Ff=11 + 0 = 11

Df= 7 + 2 = 9

74

En el cuarto paso, se expande el estado D, que tiene un valor de la función de evaluación menor que el del estado F

3

E f = 10 + 0

En este último paso, el estado D se expande al estado E ya que tiene un valor menor que F y se comprueba que es un estado meta. Por lo que el primer estado meta encontrado es el estado E, cuyo costo es de 10.

Por lo tanto se comprueba en este caso que A* sí es óptimo, cumpliéndose que si h es admisible entonces A* es óptimo