Búsqueda Informada
Heurísticas
Búsqueda informada: heurística
Ejemplo de heurística para el problema
del viajante de comercio
Clasificación de heurísticas
Ventajas de las heurísticas
Aplicando heurísticas
Algoritmo de búsqueda de Greedy
Búsqueda de Greedy: ejemplo
Grafo del ejemplo de la búsqueda de
Greedy
Evaluación de la búsqueda de Greedy
Minimizar el costo de ruta total
 La búsqueda avara minimiza el costo estimado hasta la meta h(n)
 poda fuertemente el costo de búsqueda
 ni óptima ni completa
 la búsqueda de costo uniforme minimiza el costo hasta ese
momento, g(n)
 óptima y completa
 podría ser muy ineficiente
 f(n) = g(n) + h(n) = costo estimado de la solución más barata
pasando por (n)
Minimizar el costo de ruta total
 Observaciones





Supongamos que tenemos un nodo n a una profundidad d en el
árbol de búsqueda y que adivinamos que ese nodo se halla a una
distancia h(n) de la meta más cercana a él.
La meta estaría entonces a la profundidad d + h(n) en el espacio
de problema
En lugar de elegir para la expansión el nodo de mínimo h(n)
(distancia esperada hacia la meta), elegimos el nodo de

MIN { d + h(n) }
La profundidad se mide con la función de costo de la ruta g(n)
Quedando
MIN { g(n) + h(n) }
Algoritmo de búsqueda A*
Algoritmo de búsqueda A*
Optimalidad de A*
 Definir f* - el costo de la solución óptima para la ruta
 A* expande todos los nodos con f(n) < f*
 A* podría expandir algunos de los nodos a la derecha del
“contorno de la meta”, para los cuales f(n) = f*, antes de
seleccionar el estado meta.
 La primera solución encontrada debe ser la óptima, dado que los
nodos de todos los contornos subsiguientes tendrán un costo f más alto
y con ello un costo g más alto (todos los estados meta tienen h(n) = 0)
Buscando una solución subóptima

Las etiquetas de los nodos son su valor
heurístico h = k y los números entre
paréntesis son el orden de prioridad para
expandir.

El valor k de un nodo significa que
esperamos que esté a k pasos de la meta.

El método siempre expande nodos con una
mínima distancia esperada al nodo meta,
así que el subárbol de la derecha nunca
tiene turno para expandir. (Es una cola que
privilegia a la ruta izquierda, primero en
profundidad)

Conclusión: no tratamos de encontrar un
nodo meta que esté a una menor
profundidad.
3 (1)
(2) 2
4
(3) 1
1
(4) 1
goal
(5) 1
(6) 1
(7)
goal
Buscar la Solución Optima

Tratamiento para el diagnóstico previo:

Las etiquetas de los nodos son aquí
“profundidad + valor heurístico”. Números
entre paréntesis son orden de expansión.
0+3 (1)
(2) 1+2
1+4 (6)
(3) 2+1
2+1 (7)

Para A* no hay diferencia real entre (5) y
(6)
(4) 3+1
3+0 (8)
goal

No se puede garantir que se pueda
encontrar la solución óptima .

Por ejemplo, qué pasa si (5) fuese el
nodo meta?

Problema: con pesimismo se ha
etiquetado al primer nodo de la rama
derecha como 4 (hemos
sobreestimado su distancia a la meta)

Es imperiosa una heurística optimista.
(5) 4+1
5+1
goal
Buscar la Solución Optima
0+3 (1)
(2) 1+2
1+2 (4)
(3) 2+1
2+1 (5)
3+0 (6)
goal
3+1
4+1
5+1
goal
 Admisibilidad

h - la función heurística - es
optimista si para todo n,

h(n) < hp (coste real de
llegar al nodo meta)

con eso no se sobreestima al
costo.

Una heurística optimista
(que infravalora el coste) se
llama admisible
 Casos especiales

h(n) = hp(n) (la heurística
perfecta)

h(n) = 0 ?...(búsqueda ciega)
Forma útil de ver la optimalidad de A*
 Lema  A* expande nodos en el orden de valores
crecientes de f
 Esto implica decir que así como Primero en Amplitud va
agregando niveles o capas, A* va agregando contornos
“iso-f” siempre crecientes (un contorno “fi” tiene todos los
nodos con f = fi), incluyendo al nodo de inicio en
dirección al nodo meta.
“Contornos” concéntricos “iso-f”
380
A* aplicado a la búsqueda en
Rumania
Optimalidad de A*: demostración

*
 ----------------------- -----------------------
*n
 * G1
*G2
 Sea una meta subóptima
G2 que está en la cola de
espera
 Sea n un nodo sin
expandir en el camino más
corto hacia una meta
óptima G1
 A* nunca va a elegir G2
para su expansión
Optimalidad de A*
Teorema: Sea hp(n) el costo real desde n hasta la meta. Si h(n)
< hp(n) para todo nodo n, entonces A* siempre va a encontrar un
nodo meta óptimo.
Prueba: Sea s el nodo meta de mínimo costo. Sea
(tentativamente) que A* seleccione un nodo meta subóptimo s’,
donde g(s) < g(s’)…ec.a
Sea n un nodo sin expandir en la ruta desde el nodo inicio y el
nodo meta óptimo s. Notar que ese nodo sin expandir
necesariamente existe, de acuerdo con la suposición previa (en el
otro caso, s ya habría sido elegido como el nodo meta).
Optimalidad de A*
Puesto que n no ha sido elegido para su expansión en su ruta
hacia s’, se sigue que:
f(n) = g(n) + h(n) > f(s') = g(s') + h(s')
= g(s')
Dado que h es admisible, g(n) + hp(n) > g(n) + h(n) = f(n), y
entonces
g(n) + hp(n) > f(s') = g(s')
lo cual implica que
g(s) > g(s')
 Esto contradice la suposición previa (ec. a), la que indica
que s’ es una meta subóptima..
Resumen del algoritmo A*
 Una heurística admisible nunca sobreestima el costo
de llegar a la meta
 un estimado de costo optimista en la solución de un
problema es menor -más barato- que el real.
 Si h es admisible, f(n) nunca sobreestima el costo real
de la mejor solución pasando por n
 La búsqueda A* - con f(n) y con h admisible es:
 completa y óptima
 ejemplo: hDLR es admisible
Búsqueda A*: ejemplo
Evaluación de la búsqueda A*
Heurísticos admisibles: ejemplos
Heurísticos dominantes
Descargar

Búsqueda Informada