Inteligencia Artificial 1
Parte II
Cap 4
Búsqueda Heurística
Marvin Minsky (AI Magazine - 1991)
 En pequeños dominios, podemos intentar aplicar todos
nuestros métodos de mindless search...pero no es práctico
porque la búsqueda se vuelve enorme...(CAP 3)
 Para reducir la extensión de la búsqueda desinformada
debemos incorporarle tipos adicionales de conocimiento lo
que, bajo determinadas condiciones, facilita la tarea de
resolución de problemas (CAP 4)
2
Repaso
 Russell y Norvig han definido con elegancia un algoritmo general
para resolver problemas de búsqueda. Este algoritmo puede ser
usado para expresar diferentes estrategias específicas de
búsquedas.
 Un problema se representa como una estructura con componentes:
 ESTADO
 NODO PADRE
 OPERADOR
 PROFUNDIDAD
 COSTO DE RUTA.
3
Conceptos Generales
 Una estrategia se define como una forma de darle un orden de
prioridades a la expansión de nodos.
 Hacer uso de la información con respecto al espacio de estados
 una FUNCION DE EVALUACION que describa la deseabilidad de
expandir un nodo
 usar conocimiento específico del problema
 encontrar soluciones con mayor eficiencia
4
Temas importantes
 Búsqueda Primero el Mejor
 Búsqueda A* (A estrella)
 Heurística
 Escalada (Ascenso a la Cima)
 Forjado Simulado
5
4.1
4.1
Búsqueda
primero el mejor
6
Algoritmos de búsqueda informada
(Búsqueda inteligente)
Búsqueda Heurística
Estrategias de Búsqueda Avara
A*
7
Búsqueda Heurística
 Usar información “heuristica” para adivinar qué nodo
expandir
 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 puede considerar como la maximización o minimización de una
función, como es del todo general.
 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 un meta-nivel - problema abierto
 puede no encontrar la mejor respuesta - superado por algoritmo A*
8
4.1 Búsqueda Primero lo Mejor
La IDEA ===>
usar una función de evaluación para cada nodo
- estimar la deseabilidad
==> EXPANDIR EL NODO MÁS DESEABLE ENTRE LOS NO EXPANDIDOS
IMPLEMENTACION ===>
FUNCIÓN_EMBRETAR_COLA = QUEUINGFN = insertar sucesores en orden
decreciente de idoneidad, quedando en el tope el mejor
CASOS ESPECIALES
Búsqueda avara
A*
9
Búsqueda Primero lo Mejor
 Ordenar los nodos de tal forma que el nodo de mejor evaluación
sea el primero en ser expandido
 la función de evaluación no es omnisciente - provee una medida
estimada de la deseabilidad de usar cierta ruta hacia el estado
meta
 la medida debe incorporar cierto estimado de costo de la ruta
desde un estado hacia el estado meta más cercano a él.
10
BPM - Búsqueda primero lo mejor
 Idea básica  expandir el nodo que maximiza o minimiza la función
de evaluación f(n)
 Estrategia Avara: f(n) = h(n), donde h(n) estima el costo de llegar desde el
nodo n hacia la meta
 ¿Qué sucede si a cada paso tratamos de acercarnos al nodo meta?
En este caso el método seguirá la ruta más
larga, al empezar a moverse hacia delante
según la receta
Escalada tiene este
mismo defecto
11
BPM
 Objetivo de la familia de búsquedas llamada Búsqueda Primero lo
Mejor  encontrar velozmente la meta
 expandimos el nodo más cercano al nodo meta
 para merecer optimalidad, queremos encontrar rapidamente la meta más “chata”
(esto es, más cercana al origen)
 el objetivo es distinto al de la búsqueda de costo uniforme - vista previamente (la
única búsqueda ciega interesada en costos) - que no está dirigida a la meta sino hacia
emplear el costo de ruta, ya recorrida, g, para decidir qué nodo expandir  en costo
uniforme la lista se ordena para obtener la solución más barata en base a datos
experimentados.
12
Búsqueda Avara
 La función de evaluación muestra la siguiente heurística:
 h(n) = costo estimado entre n y la meta
 por ejemplo
 hDLR(n) = distancia en línea recta desde n hasta Bucarest
 La búsqueda avara expande el nodo que pareciera estar más
cerca de la meta.
13
Búsqueda Avara
 Una de las búsquedas Primero lo Mejor más sencillas - MIN costo
estimado para llegar a la meta (2º sumando de f = g + h  f =
h)
 ese costo se puede estimar pero no determinar con exactitud; la
buena heurística ayuda.
 la función heurística h es una función que calcula dichos estimados
de costo
 h(n) = costo estimado de la ruta más barata desde el estado en n
hasta el estado meta.
14
Búsqueda Avara
 El nodo con valor h mínimo es el que se va a expandir: cola con
privilegios
 h puede ser cualquier función, siempre que valga cero en la meta, pero
la calidad cambia mucho
 las funciones heurísticas son problema -intensivas (son problema específicas)
 en problemas de búsqueda de ruta una buena h es hDLR , donde DLR es
distancia en línea recta
 una ruta de A a B suele ir en la dirección correcta
15
Búsqueda Avara
 Adoptar la primera selección con una visión inmediata, sin
preocuparse si ha de ser la mejor con una perspectiva a largas
vistas.
 La búsqueda halla soluciones en forma rápida, que no siempre son
las óptimas
 susceptible a falsas largadas o pasos en falso (Iasi  Fagaras) que
va hacia Neamt, ruta muerta sin salida
 hay que cuidarse de los estados repetidos
 oscilaciones entre Neamt y Iasi
16
Búsqueda Avara
 Parecida a BPP, prefiriendo seguir una ruta singular hacia la meta,
aunque recula (backtracking o reversiva) al chocar con una ruta muerta
 sufre del mismo defecto  ni es óptima, ni es completa (con una ruta
posiblemente infinita)
 su complejidad temporal en el peor de los casos es O(b^m), siendo m
la profundidad máxima del espacio de búsqueda
 complejidad espacial igual a la temporal (guarda todos los nodos en
memoria)
 una buena h reduce fuertemente la complejidad
17
AVARA- Minimizar el Costo Estimado
 Función de evaluación heurística:
 h(n) = costo estimado de la ruta entre el nodo n al nodo meta
 h(n) = 0, si n es el nodo meta
» tabla de distancias lineales a Bucarest =>
18
Ejemplo de Búsqueda Avara





En el mapa ya visto anotamos Arad==>Bucarest = 366 km
h(n) = distancia en línea recta
- Zerind 374
-Sibiu 253 <==
-Timisoara 329
19
Ejemplo de Búsqueda Avara


Arad Oradea -
 Fagaras

366
380
.. 178
Rimnicu Vicea - 193
20
Ejemplo de Búsqueda Avara


Sibiiu
Bucarest
253
0 <====
21
AVARA- Minimizar el Costo Estimado
Arad
h(n) = 253
Sibiu
178
366
Arad
253
Sibiu
h(n) = 329 Timisoara
h(n) = 374
Zerind
193
380
Fagaras
h(n) = 366
Oradea
Rimnicu
h(n) = 0
Bucharest
verdadera ruta óptima es: Arad
 Sibiu  Rimnicu  Pitesti  Bucharest
22
Propiedades de la búsqueda avara
 Completa?
 No - puede colgarse en algún bucle
 p.ej., Iasi  Neamt  Iasi  Neamt  …
 Pasa a ser completa en espacio finito si se sujeta a una verificación de estado repetido
 Complejidad Temporal:
 En el peor caso: O(bm)
 pero una buena heurística provoca mejoras dramáticas
 Complejidad Espacial:
 En el peor caso: O(bm)
 mantiene todos los nodos en memoria
 Optima?
 No
23
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)
24
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)
 Queda
MIN g(n) + h(n)
25
Búsqueda A*
 Idea no expandir trayectos que ya se sabe que son caros
 Función de evaluación






f(n) = g(n) + h(n)
g(n) = costo hasta llegar a n
h(n) = costo estimado hasta la meta desde n
f(n) = costo total de ruta pasando por n hasta la meta
A* usa una heurística admisible - no hay sobreestimación de distancia
Teorema - A* es óptimo
 Aproximación  léase h como “heurístico”, pues es funcíón fuerte de
la heurística elegida
26
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)
27
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, todos incluyendo el nodo de inicio y a medida que se
acercan a la meta, empiezan a incluir justo la meta y la superan. El
contorno “iso-f” llamado i tiene todos los nodos con f=fi.
28
A* - resumen gráfico
 Ver figuras con círculos concéntricos deformados, ya no con
CONTORNOS equirradiales


29
“Contornos” concéntricos
30
“Contornos” concéntricos
380
31
Prueba estandar de la optimalidad
de A*

*
 ----------------------- -----------------------
*n
 * G1
 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
*G2
32
Optimalidad de A*
Teorema: Sea h*(n) el costo real desde n hasta la meta. Si h(n) < h*(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).

=>
.
33
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) + h*(n)  g(n) + h(n) = f(n), y entonces
g(n) + h*(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..
34
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
 completa y óptima
 hDLR es admisible
35
Conducta de la búsqueda A*
 A lo largo de cualquier ruta a partir del inicio, el costo de f nunca
decae - esto es casi la regla general de las heurísticas admisibles
 una heurística que cumple con esa regla se dice que exhibe
MONOTONICIDAD
 heurística no-monotónica, caso raro
 f(n) = g(n) + h(n) = 3+4 siendo n nodo padre
 f(n’)= g(n’)+h(n’) = 4+2 siendo n’ nodo hijo
 6 no tiene sentido ya que el costo de f(n’) debe ser por lo menos 7, ya que la
ruta por n’ ha pasado por n. Esta no-monotonicidad debe ser corregida por
inconsistente.
 Nota  sigue siendo una heurística admisible ya que no sobreestima el costo,
al contrario, lo infraestima más.
36
Conducta de la búsqueda A*
 Realizar entonces una corrección menor que restituya la monotonicidad
de una heurística no-monotónica
 el costo f nunca decrece durante cualquiera de las rutas partiendo del
inicio, suponiendo que h sea admisible
 diverge desde el nodo inicial, sumando nodos en zonas anulares
concéntricas de costos f, o sea los contornos de iso- f .
37
Conducta de la búsqueda A*
 Con una búsqueda de costo uniforme (esto es, A* usando h = 0), las
zonas cubiertas entre dos contornos son anillos circulares
alrededor del estado de inicio.
 Con más heurística (h>0) incorporada, las zonas anulares o
contornos se estirarán hacia el estado meta y poco a poco irán
delimitando más la ruta óptima, enmarcandola más
ajustadamente.
 Esto recuerda los cambios de nivel de la BPA
38
Completitud de A*
 A* expande nodos en el orden de un creciente f, con lo cual
eventualmente expandirá hasta llegar al estado meta
 salvo que haya una cantidad infinita de nodos con f(n)< f*
 un nodo con un factor de ramificación infinito
 una ruta con costo de ruta finito pero con un número infinito de nodos a lo largo de
ella
39
Complejidad de A*
 La búsqueda A* es OPTIMAMENTE EFICIENTE para cualquier
función heurística al contrastarse con otros algoritmos óptimos que
compiten con ella.
 No hay otro algoritmo que expanda menos nodos que A*
 Cualquier algoritmo, que no expanda todos los nodos en los contornos
existentes entre el contorno del inicio y el de la meta, corre el riesgo de no
encontrar la solución óptima
40
Complejidad de A*
 Complejidad temporal - O(b^d)
 Complejidad espacial - O(b^d)
 el espacio de búsqueda de A* crece exponencialmente a no ser que
sea
h(n)-h*(n) =< O(log h*(n))
 prácticamente, el error es a lo menos proporcional al costo de la
ruta
 el crecimiento exponencial satura a cualquier computadora
41
Complejidad de A*
el uso de una heurística buena provee ventajas
enormes
usualmente A* se queda sin espacio antes de
quedarse sin tiempo, puesto que mantiene a
todos los nodos en memoria
42
A*
f(n) = 366
Arad
140
h(n) = 253
f(n) = 393
140
h(n) = 329
f(n) = 447 Timisoara
Sibiu
99
75
118
151
Zerind
h(n) = 374
f(n) = 449
80
Arad
Fagaras
Oradea
f(n) = 646
f(n) = 417
f(n) = 661
146
Rimnicu
f(n) = 413
97
80
Craiova
Pitesti
f(n) = 526
f(n) = 415
Sibiu
f(n) = 553
43
Resumen de la búsqueda A*
 A* usa una heurística admisible.
 h(n)  h*(n), donde h*(n) es el costo verdadero desde n
 para rutas sobre terreno, la distancia en línea recta nunca
sobreestimará la distancia real de una de ellas.
 A* es óptima si h es admisible
44
Resumen de la búsqueda A*
 Idea  No expandir estados que ya se sabe que son caros
 Mejorar la búsqueda de costo uniforme y la búsqueda avara haciendo:
f(n) = g(n) + h(n)
 g(n) = costo de inicio a n
 h(n) = costo estimado desde n hasta meta
 f(n) = costo total estimado de la ruta desde inicio a meta pasando por n
45
A*
h(n) = 253
f(n) = 393
140
Arad
Sibiu
151
f(n) = 417
99
Fagaras
80
Oradea
Rimnicu
f(n) = 413
f(n) = 526
f(n) = 646
99
211
146
Sibiu
Bucharest
Craiova
f(n) = 591
f(n) = 450
f(n) = 526
97
f(n) = 415
80
Sibiu
Pitesti
f(n) = 553
97
138
101
Rimnicu
Craiova
Bucharest
f(n) = 607
f(n) = 615
f(n) = 418
46
A*
h(n) = 253
f(n) = 393
140
Sibiu
99
151
80
Arad
Fagaras
Oradea
f(n) = 646
f(n) = 417
f(n) = 661
Rimnicu
146
Craiova
f(n) = 413
97
f(n) = 415
80
Sibiu
Pitesti
f(n) = 553
f(n) = 526
97
138
101
Rimnicu
Craiova
Bucharest
f(n) = 607
f(n) = 615
f(n) = 418
47
Casos límites de A*
 Si h=0 y g=d  BPA
 Si h=1/d y g=0  BPP
 Si h=0 y g=0  Búsqueda aleatoria
 Si h=h y g=0  Búsqueda avara
 Si h=0 y g=g  Búsq. de costo uniforme
 Si h(n)>h*(n)  se habría perdido la ruta óptima
 Si h(n)<h*(n)  ruta bien ¿tramo redundante?
48
4.2
4.2
Funciones heurísticas
49
4.2 Funciones Heurísticas
1
5
4
6
1
8
8
7
3
2
7
estado inicial
2
3
4
6
5
Estado meta
 Problema de los 8 tejos-Restricciones: no avanzar dos o más pasos
por turno, no avanzar diagonalmente, no superponer un tejo a otro,
no destornillar la cajita…
 h1(n) =tejos fuera de orden---h2(n) = suma de distancias de Manhattan
50
Funciones heurísticas
Mi problema con el juego de los 8 tejos es encontrar una heurística para saber o adivinar
cuánto me falta por llegar a la meta.
 Cuento cuántos tejos están mal ubicados con respecto a la meta. Tengo h1=7.
 Parto de nuevo. Cuento para cada tejo las cuadras de Manhattan que deben recorrer
(usando rutas ortogonales y ya no diagonales). Tengo h2=18.
 Miro mi posición actual y cuento cuántos pasos debe dar cada tejo, usando diagonales si
es necesario, para llegar a su posición meta. Sumo. Tengo h3=14.
 Cuento cuál es la distancia en línea recta DLR de cada tejo con respecto a la posición
deseada en la meta. Sumo para los 8. Tengo h4=13 .
 Nótese que siempre he violado restricciones del caso real. Al hacerlo, he descubierto
otros nuevos juegos “relajados”.
 Serán mis estimaciones de la distancia real, en pasos, a recorrer.
 Mi heurística óptima es la máxima entre h1,...,h4, pues he sido optimista.
 Todas son estrategias admisibles  optimistas (calculo menos pasos)  nunca
sobreestiman la distancia (definen la “admisibilidad”)
51
Heurísticas Admisibles
Encontrar una buena heurística para un problema
 relajar las restricciones
 en general, el costo de una solución exacta obtenida al relajar un
problema sirve como una buena heurística para el problema original se menciona de nuevo la distancia de Manhattan como ejemplo
 usar información estadística obtenida durante entrenamiento con
ejemplos para la predicción de valores heurísticos para los nodos, con el
riesgo de generar funciones heurísticas inadmisibles.
 información estadística (h2 =14 se correlaciona con h = 18)
52
Funciones heurísticas
 Siempre será mejor usar una función heurística con números
mayores, por supuesto, sin pasarse a la sobreestimación.
 Hago una abstracción. He inventado heurísticas por relajamiento
de las restricciones del problema  he empleado la regla
max(h1,h2,...) para definir la heurística óptima.
 He encontrado soluciones reales de versiones más sencillas del
problema pero he preferido la menos sencilla (por ser el mejor –el
más útil- de los mundos)
 La evaluación heurística debiera ser eficiente.
53
Inventar funciones heurísticas
 Problema relajado - menos restricciones impuestas a los operadores.- El
costo de una solución exacta a un problema relajado es a menudo una
buena heurística para el problema original.
 Un tejo se puede mover del cuadrado A al B si A es adyacente a B y B está vacío.
 un tejo se puede mover desde el cuadrado A al B si A está adyacente a B
 un tejo se puede mover del cuadrado A al B si B está vacío
 un tejo se puede mover del cuadrado A al B.
54
Inventar funciones heurísticas
 Definición del problema - un lenguaje formal  relajación automática
(programa ABSOLVER que relaja)
 falla en fijar claramente la mejor heurística  heurística compuesta h(n) = max(h1(n), ..., hm(n)), usa la función que sea la más precisa en
cada nodo
 aprender cuál es mejor “rasgo” para cada estado con sus propias
características.
 Costo de búsqueda  hay que considerar tambien el costo de usar h en
un nodo
55
Calidad de la heurística
 Factor de ramificación efectivo b*
 N = 1+b*+(b*^n)^2+...+(b*)^d –
 forma de caracterizar la calidad de la heurística
 h2 está más informada que h1 si para cualquier nodo n,
h2(n)>=h1(n) y ambos son admisibles
 h2 domina a h1 - entonces A* al usar h2 va a expandir menos nodos
que usando h1
 COMPARACION-Ver figura 4.8, pag 110 - tabla de comparación
de tres métodos, dominante A*(h2), dominados h1 y búsqueda
iterativa en profundidad.
56
Qué hago con la función
heurística preferida
 La utilizo en el momento cuando tengo que decidir cuál nodo de la
frontera (esto es de la cola) debo privilegiar para avanzar un paso
en la búsqueda.
 El nodo más conveniente - calculado según la función heurística ocupará el tope de la cola.
 Esto se ve claramente en la serie de diapositivas 20 a 24 – algo más
adelante - donde el agente resolvedor de problemas puede calcular
la calidad de los diferentes nodos (ciudades en ese caso) y va
construyendo contornos con valores crecientes de iso-calidad (esto
es, “iso-f” en el caso de A*) hasta llegar a la meta.
57
Inventar funciones heurísticas caso restricto
 Sea el problema de colorear mapas (fig 4.9 con seis países) con mínimo
número de colores (probemos con tres).
Seleccionar una variable (un país, de A a F) para atribuirle un valor
(un color)  A=verde, B=rojo (inicio).
 Variable más restringida (con menos grados de libertad)
 verificación adelantada (forward checking) - qué valores aún no son tabú para cada
variable.
 Seleccionar aquella variable con menores posibles valores  el factor de ramificación
tiende a ser mínimo
 el tamaño factible del problema para las n-reinas aumenta desde 30 con revisación por
adelantado hasta cerca de 100 sin ella.
58
Inventar funciones heurísticas caso restricto
 Revisión por adelantado (la variable de menor gl)
 seleccionar cuál es la variable involucrada en el máximo de restricciones con
respecto a otra variable sin asignar. Es la que tiene menos valores posibles (C gl=2; D
gl=3; E gl=1; F gl=2). Elegir D y darle el valor=azul
 Logra una reducción del factor de ramificación en las elecciones futuras.
 Valor menos restringidor
colorear D de rojo les da posibilidades a E y F
 elegir un valor (rojo D) que descarta el menor número de valores (solo descarta el rojo
que ya antes se había descartado) en variables E y F) conectadas a la variable en estudio
(D) por restricciones
 Es el valor menos molesto para los vecinos
 Deja mayor grado de libertad para selecciones futuras.
59
Buscando una solución subóptima
3 (1)
(2) 2
4
(3) 1
1
(4) 1
goal
(5) 1
(6) 1
(7)
 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
min distancia esperada del 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)
 Diagnóstico: no tratamos de encontrar un
nodo meta que esté a una profundidad
más chata.
goal
60
Buscar la Solución Optima
 Tratamiento para el diagnóstico previo:
 Las etiquetas de los nodos son aquí
1+4 (6)
“profundidad + valor heurístico”. Números
entre paréntesis son orden de expansión.
 Para A* no hay diferencia real entre (5) y (6)
0+3 (1)
(2) 1+2
(3) 2+1
2+1 (7)

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)
3+0 (8)
goal
 Es imperiosa una heurística optimista.
(4) 3+1
(5) 4+1
5+1
goal
61
Buscar la Solución Optima
 Admisibilidad
0+3 (1)
(2) 1+2
1+2 (6)
(3) 2+1
2+1 (7)
 h - la función heurística - es optimista si para
todo n,
 h(n) h* (costo actual de llegar al nodo
meta)
 con eso no se sobreestima al costo.
 Una heurística optimista se llama admisible
 Casos especiales
3+0 (8)
goal
(4) 3+1
 h(n) = h(n)* (la heurística perfecta)
 h(n) = 0 ?
(5) 4+1
5+1
goal
62
4.3
4.3
Búsqueda restricta por la
capacidad de memoria
63
Desarrollo de una búsqueda A* modif.
64
4.3 Búsqueda Restricta por la
Memoria
-
A* con Profundización Iterativa (IDA*) [Fig4.10]
- BPP por todos los nodos cuyos f sean menores o iguales al f límite
 el nuevo f límite siempre será el menor f de los nodos expandidos más
allá del f límite
 el número de las iteraciones de este método es proporcional al número
de los diferentes valores de f
 podría usarse un incremento e fijo para f límite
 pero no sería ADMISIBLE (e-admisible) que
 e  |opt – soln|
65
4.3 Búsqueda restringida por
Memoria - IDA*
 ¿Gran problema de A*?  mucho requisito de memoria.
 ¿Cuál es lo mejor para economía de memoria? BPP (DFS)
 ¿De qué forma se mejoraban los defectos de BPP sin empeorar más que un
poco sus requisitos de memoria?  PI
 De allí: iterative deepening A* search (IDA* o A*PI)
 cada iteración es una búsqueda en profundidad, ahorrativa, usando un límite
basado en el costo f y no en l (límite de profundidad)
 Estudiemos cinco iteraciones típicas donde f va creciendo. La última fila es la
conclusión de la iteración terminada.
 “Ciudades” meta D,F,I,J (la de costos menores de ruta)- Origen: A –Otras
que no son meta: B,C,E,G,H,K – Fig 4.11
66
Ejemplo de IDA* o A*PI
 DFS-contour = contorno BPP
 iteración 1
 DFS-CONTOUR(A, 12)
DFS-CONTOUR(B, 12)
f-cost(B) = 15 > 12
new-f = 15
next-f = 15
f-cost(G) = 13 > 12
new-f = 13
next-f = 13
f-limit = 13
---------------
 En el interior de la “iso-f = 12”: A (este iso-f se denomina contorno
inicio)
 Próxima a analizar “iso-f= 13”.
Ver Fig 4.11 –1,2,3
67
Ejemplo de IDA* o A*PI
iteración 2
 DFS-CONTOUR(A, 13)
DFS-CONTOUR(B, 13)
f-cost(B) = 15 > 13
next-f = 15
DFS-CONTOUR(G, 13)
DFS-CONTOUR(H, 13)
f-cost(H) = 18 > 13
DFS-CONTOUR(I, 13)
f-cost(I) = 24 > 13




f-limit = 15
---------------En el interior de la “iso-f = 13”: A y G (no son metas)
Próxima a analizar: “iso-f = 15”
 Ver Fig 4.11 –4,5,6
68
Ejemplo de IDA* o A*PI
iteración 3
DFS-CONTOUR(A, 15)
DFS-CONTOUR(B, 15)
DFS-CONTOUR(C, 15)
next-f = 25
DFS-CONTOUR(D, 15)
next-f = 20
DFS-CONTOUR(G, 15)
DFS-CONTOUR(H, 15)
next-f = 18
DFS-CONTOUR(I, 15)
f-limit = 18
-------------
 En el interior de la “iso-f = 15”: A,G,B (no son metas)
 Próxima a analizar: “iso-f = 18”
69
Ejemplo de IDA* o A*PI

iteración 4
 DFS-CONTOUR(A, 18)
DFS-CONTOUR(B, 18)
DFS-CONTOUR(C, 18)
DFS-CONTOUR(D, 18)
next-f = 20
DFS-CONTOUR(G, 18)
DFS-CONTOUR(H, 18)
DFS-CONTOUR(J, 18)
DFS-CONTOUR(K, 18)
DFS-CONTOUR(I, 18)
f-limit = 20
-------------------
 En el interior de la “iso-f = 18”: A,G,B,H (no son metas)
 Próxima a analizar: “iso-f = 20”
70
Ejemplo de IDA* o A*PI
 iteración 5
 DFS-CONTOUR(A, 20)
DFS-CONTOUR(B, 20)
DFS-CONTOUR(C, 20)
DFS-CONTOUR(D, 20)
solución = D
 ----------------------
 En el interior de la “iso-f = 20”: A,G,B,H,D (D=meta) –Este iso-f
se denomina contorno meta.
 FIN – Hipotéticamente la próxima a analizar: “iso-f = 25”
Ver Fig 4.11 –7,8
Nota- La Fig 4.11 desarrolla el caso A*SRM
71
Algoritmo IDA*
 Un problema inherente a A* es su malgasto de memoria
 cuando h = 0 se reduce a BPA con lo cual usa memoria exponencial con la profundidad en que se encuentra el
nodo meta óptimo
 la profundización iterativa puede ayudar - ahora podamos los nodos cuyo nodo meta más cercano se puede mostrar
que está por debajo de la profundidad de corte.
 Las s iteraciones individuales realizan una BPP. La función heurística tiene como misión podar nodos, sin llegar a
determinar el orden de la expansión.
Sketch of IDA* Algorithm:
1. Set c = 1; this is the current cutoff value.
2. Set L to be the list of initial nodes.
3. Let n be the first node on L. If L is empty, increment c and return to step 2.
4. If n is a goal node, stop and return the path from initial node to n.
5. Otherwise, remove n from L. Add to front of L every child node n’ of n
for which f(n’)  c. Return to step 3.
72
Algoritmo IDA*
0+2 (1,2,4,9)
(3,5,10) 1+1
1+2 (7,13)
(6,11) 2+1
2+1 (8,14)
(12) 3+1
4+1
3+1 (15)
4+0 (16)
goal
 Para c = 1, solo se examina el nodo
inicio
 para c = 2, examinar dos nodos, inicio
y su hijo izquierdo. Notar que el hijo
derecho es podado pues su valor de f
>c=2
 las iteraciones individuales se realizan
mediante BPP (el nodo 12 se expande
antes que el 14, pese a que el valor de f
es menor)
5+0
goal
73
Búsqueda Restricta por Memoria
 A* Simplificada y Limitada por Memoria (SMA*) [Fig 4.12]
- según exigencias de memoria, descarta nodos de ella que
tengan valores de f altos.
-los valores de f descartados quedan memorizados en ancestros
- mecanismo de regeneración de nodos descartados que regenera lo
faltante solo si todo el resto de rutas son peores.
- óptima y completa si la solución más “chata” cupo en la
memoria.
 En el otro caso, entrega la mejor solución alcanzable:
ejemplo [Fig4.11]
74
En qué consiste SMA* o A*SRM
 IDA* emplea demasiado poca memoria y no la llena, con lo cual se
malgasta esfuerzo
 SMA* usa en cambio toda la memoria M disponible para realizar
la búsqueda
 evita estados repetidos dentro de la dispònibilidad de M
 completa si M >= d, optima si M >= d*
 optima en eficiencia si M >= bm
 la limitación de la memoria hace que no se pueda rastrear cuál
será el tiempo de cómputo (pendula entre candidatos) 
optimalidad cae.
75
4.4
4.4
Algoritmos de mejora iterativa
76
Algoritmos de Mejora Iterativa
 La lista de los principales ejemplos es:
 1) Arrancar con la configuración completa e ir modificando
hasta llegar a una solución.
 Por ejemplo, las 8 reinas [Fig4.16]
 2) Ascenso a la Cima o Descenso por Gradientes [Fig4.14]
 3) Endurecimiento (FORJADO) Simulado [Fig4.15]
Se transige con el empeoramiento transitorio
77
Ascenso a la Cima (Hill-Climbing Search)
Sinónimo: Escalada
 Descenso por gradiente - continuamente se desplaza en la dirección de
valor que más crece - elegir el mejor siguiente estado inmediato)
 no mantiene un árbol de búsqueda
 descarta información de ruta
 rearranque de ascenso basado en azar
 tres motivos de falla reconocidos
 máximos locales - caminata al azar
 mesas - caminata al azar
 riscos - oscilaciones y poco progreso
 ascenso a la cima aleatorio con rearranque
 la estructura de la “superficie” del espacio de estados
78
Ascenso a la Cima
Idea general  si no podemos usar una descripción matemática para
derivar e igualar a cero y con ello encontrar la ruta inteligente
adecuada, recurrimos al ascenso a la cima.
Exploramos localmente cerca del punto en que estamos, palpando la
dirección del ascenso máximo o pendiente máxima.
Dejamos así de lado un árbol de búsqueda.
Avanzamos por la pendiente máxima con un paso arbitrario (no sabemos
cuál usar).
 Un paso corto lleva a vagabundeo sin ganancia de información.
 Si el paso es muy largo nos sobrepasamos y ya no estamos dentro del método
 Cuando decae la mejora, estamos en la cima o en una mesa.
 Retomamos la búsqueda al azar.
79
FORJADO o Endurecimiento
simulado
 En metalurgia y termodinámica se menciona el forjado o endurecimiento como
el proceso de inicio a alta temperatura y enfriamiento gradual para obtener
transiciones de fase más estables que las obtenidas por enfriamiento rápido.
 FORJADO o ENDURECIMIENTO SIMULADO  proceso de
búsqueda global u optimización global en sistemas de comportamiento
estocástico, con alguna probabilidad que es función de una
“temperatura” (un cierto parámetro que desciende por ejemplo hasta
cero) con lo cual la conducta es diferente de una completamente
determinística. La temperatura arranca siendo alta, el metal está
blando y se va endureciendo al descender la temperatura con un
programa preestablecido.

80
FORJADO o Endurecimiento
simulado
  problemas difíciles, por ejemplo multimodales, basados en la metáfora de imitar el
endurecimiento o forjado usado en metalurgia. Si el programa de enfriamiento es
demasiado rápido, las transiciones de fase ocurren desordenadamente, mientras que si
el programa de temperatura es suave, se logra mayor estabilidad, que aquí se interpreta
como encontrando la más alta cima en lugar de cimas subóptimas.
 Pertenece a la familia de los métodos de búsqueda heurísticos, esto es, admite que haya
pasos aparentemente en falso, que no mejoran la evaluación, pero esos pasos van
disminuyendo en su probabilidad a lo largo del tiempo, cuando no se han encontrado
otras cimas que la principal que se está ascendiendo.
 La tasa con que se admiten aparentes pasos en falso (decrecientes) está regulado por un
programa de enfriamiento (cooling schedule), con lo cual se mantiene la vigencia de la
metáfora.
 El método garante un óptimo global y no un subóptimo local si la temperatura baja con
suavidad.
81
FORJADO o Endurecimiento Simulado
 Elegir un movimiento al azar
 si es mejor, ejecutarlo
 si es peor, ejecutarlo con probabilidad que decrezca
exponencialmente con lo “malo” del movimiento y la
“temperatura”
 la temperatura cambia de acuerdo con un programa
 si el programa hace descender la T en forma lenta, el
algoritmo va a encontrar un óptimo global
82
Aplicaciones en Problemas con Satisfacción de
Restricciones (CSP)
 Resolver los CSP por mejoramiento iterativo
 solución inicial - uso de todas las variables
 operador de modificación - asignar un valor diferente a una
variable
 reparación heurística
 heurística de min-conflictos - seleccionar el valor que resulte
en un número mínimo de conflictos con otras variables
83
Satisfacción de Restricciones
- elegir un valor para cada variable
-luego usar reparación heurística (reparar las
inconsistencias)
  un método frecuentemente muy exitoso 
elegir los valores que entren en min-conflictos
con otras variables
84
4.5
4.5
Resumen y conclusiones
razonadas
85
Resumen
 Búsqueda Primero por lo Mejor - parte de Búsqueda General y
expande según COSTO MINIMO
 Avara  COSTO MINIMO se interpreta como h, el que falta
por satisfacer
 A*  combina costo uniforme (g) con avara (h) - inconveniente
- no ahorra espacio
86
Resumen (2)
 Una buena heurística, ahorra.
 A*PI = A* + PI (profundización iterativa). Al ser
profundización, ahorra.
 A*SRM - si la memoria está llena, borrar el nodo de f más
alto de la cola de espera (supresor)
 Mejoramiento iterativo:
 ascenso a la cima - evaluación por calidad
 gradiente mínimo - evaluación por costo
 forjado simulado - retroceder pasos
87
Resumen (3)
 PSR (constraint satisfaction) - se asignan valores a todas las
variables y luego se modifican para conducir el proceso
hacia buen éxito.
 Al reparar inconsistencias se llaman algoritmos PSR
 GSAT – algoritmo paradigmático en su uso en temas
posteriores
88
Conclusiones razonadas
 En nuestra conducta intelectual raramente resolvemos nuestros
problemas con un ascenso continuo hacia el buen éxito. Por eso
es difícil de interpretar que un agente resolvedor de problemas
vaya a servir en los casos particulares de búsqueda.
Probablemente necesitará un abanico de recursos de búsqueda.
Quizás haya que disponerlos en una estructura jerárquica rica
con estructuras complejas y recursivas.
89
Conclusiones razonadas
 Como contrapartida, es estupendo que una máquina se guíe por los gradientes de la
superficie de respuesta. Los métodos de búsqueda se dividen en dos grupos:
 los DESINFORMADOS ACERCA DE DERIVADAS, globalmente lentos e
ineficientes (en muchas casos) y
 los INFORMADOS y que usan inteligentemente esa información. El ascenso a la
cima es un bello ejemplo de algoritmo informado y al serlo es muy rápido y
eficiente.
 En el caso del humano, puede hacer recordar la teoría de la felicidad de Mihaly
Csikszentmihalyi, acerca del desafío y la habilidad. Una habilidad orientada por
derivadas, pendientes y tangentes parece la mejor manera de enfrentar desafíos
complejos.
90
Conclusiones razonadas
 Aun con el FENOMENO DE MESA (the Mesa Phenomenon) - donde el
espacio está compuesto primariamente por zonas sin pendientes y donde
pasa a explorar al azar - el método de ascenso a la cima parece un buen
ejemplo de las reflexiones estimuladas por el lema de la I.A., “los aviones
no aletean” ( no hay que imitar temas secundarios de la biología, sino los
principales – aquí trepar, errar y trepar es primario)
 Frente al efecto MESA  la búsqueda al azar es una de las más ingeniosas
para detectar nuevas pendientes – es así una heurística adecuada que
complementen a la búsqueda de ascenso a la cima.
91
Conclusiones razonadas
 Estas heurísticas conducen a pensar en otra categoría de métodos de búsqueda
mucho más afines a la mente humana. No han sido mencionados en este Capítulo 4.
Son los que incorporan aprendizaje a la búsqueda  tema por ver (cap. 17). En vez
de buscar al azar, buscar al azar en zonas no recién exploradas.
 La idea fundamental es aprendizaje por refuerzo (típico de los animales) , un
concepto tradicional de la psicología y de la IA.
 El clásico método de programación dinámica de Bellman es el único método
que computa la mejor estrategia de control a lo largo del tiempo de
búsqueda. Se ha podido hibridizar entonces entre aprendizaje por refuerzo y
programación dinámica clásica, generando ADP (programación dinámica
aproximada). Ese quizás sea el futuro.
92
Conclusiones razonadas
 Si no sabemos cómo obtener X, creemos un espacio de estados
donde sepamos que va a estar incorporado X y luego busquemos
a X dentro de ese espacio.
 Mérito de esta formulación  siempre es posible encontrar un
espacio donde esté contenida la respuesta o solución.
 Cuanto menos conocimiento tengamos, tanto más grande será el
espacio. La inteligencia lo achica.
93
Conclusiones razonadas
Dos grandes temas fundamentales en IA.
 La búsqueda es uno de ellos.
 Los procesos de reconocimiento de patrones 
APRENDIZAJE, son el otro, igualmente fundamental (aunque
reconocer es haber buscado). Permiten el contacto entre la
estructura de memoria almacenada y la estructura de la tarea a
enfrentar.
 La esencia de tener un problema es el de no saber qué hacer a
continuación.
 Esto genera búsqueda - una búsqueda combinatoria.
94
Conclusiones razonadas
 Hay por lo menos tres búsquedas en cada tarea intelectual.
 Búsqueda clásica dentro del espacio de problema tradicional, a través de los nodos de un árbol
o entre nodos, como el ascenso a la cima.
 Búsqueda de la receta intelectual para buscar (tarea por ahora del diseñador - ¿en el futuro?)
 Búsqueda de medir bien la aproximación a la meta (la heurística – el programa ABSOLVER)
 Alguna de esas búsquedas podría ser encarada como reconocimiento de
patrones o como búsqueda propiamente dicha.
 Sabemos que los árboles de búsqueda se pueden plantear como cláusulas de
Horn  buscar es también esgrimir lógica  con estructuras lógicas se puede
buscar.
 A esta altura lo que sabemos es buscar  esa es nuestra opción.
95
CONTINÚA
 http://www.angelfire.com/oh4/ohcop/ClaseCap5nu.ppt
 http://www.angelfire.com/oh4/ohcop/ClaseCap5nu.ppt
 http://www.angelfire.com/oh4/ohcop/ClaseCap5nu.ppt
 BIBLIOGRAFIA DEL TEMA:
 http://www.angelfire.com/oh4/ohcop/ayuda44.html
 http://www.angelfire.com/oh4/ohcop/ayuda44.html
 http://www.angelfire.com/oh4/ohcop/ayuda44.html
96
Descargar

Glosario de Carlos von der Becke - Cap 4