Búsqueda heurística
1
Búsqueda “mejor el
primero”


Las estrategias de búsqueda sin
información suelen ser muy
ineficientes.
Búsqueda “mejor el primero”
» Función de evaluación (eval-fn):
– Mide “lo deseable” de expandir un nodo
» Algoritmo:
function BEST-FIRST-SEARCH(problem, eval-fn)
returns a solution sequence
inputs: problem, a problem
eval-fn, an evaluation function
queueing-fn <-- a function that orders by
increasing eval-fn
return
GENERAL-SEARCH(problem, queueing-fn)
2
Búsqueda avara, I

Es una búsqueda “mejor el primero”
con eval-fn(nodo)=h(nodo).
» Función heurística (h)
– Origen: exclamación de Arquímedes, “heureka”,
tras el descubrimiento de su principio
» Algoritmo:
function GREEDY-SEARCH(problem)
returns a solution or failure
return BEST-FIRST-SEARCH(problem, h)

h(nodo)=coste estimado del camino
más corto desde un nodo hasta el
objetivo.
» Todas las funciones heurísticas deben
cumplir al menos:
– h(n)>=0, para todo nodo n
– h(n)=0, si “n” es un nodo objetivo
3
Búsqueda avara, II

Ejemplo: Mapa de carreteras
– Viajar desde Arad hasta Bucarest
– Solución obtenida por búsqueda avara:
 Nodos expandidos Encuentra el camino
» “Arad, Sibiu, Fagaras, Bucharest”,
 No es óptima: Es más corto
» “Arad, Sibiu, Rimnicu, Pitesti, Bucharest”

La búsqueda avara suele encontrar
soluciones rápidamente
» No suelen ser óptimas
» No siempre se encuentran (ciclos)
– Ej. de situación anómala: Ir de Iasi a Fagaras. Si
no eliminamos repeticiones se entra en un ciclo.
V
I
N
I
4
Búsqueda avara, IV

En resumen:
» No es óptimo ni completo.
» En el peor caso:
m
– Complejidad temporal: O ( b )
m
– Complejidad espacial:
 Se almacenan todos los nodos en memoria
 m=máxima profundidad del árbol de
búsqueda
O (b )
5
Algoritmo A*, I

Algoritmo A*, combinación de:
» Búsqueda avara:
– Reduce coste de búsqueda, pero no es óptima ni
completa.
» Búsqueda de coste uniforme:
– Es completa y óptima pero ineficiente.

Se define la función “f(n)”:
» f(n)=g(n)+h(n)
» f(n)=coste estimado de la solución de
menor coste que pasa por “n”

Algoritmo:
function A*-SEARCH (problem)
returns a solution or failure
return BEST-FIRST-SEARCH(problem, g+h)
6
Algoritmo A*, II

Heurística admisible:
» Una función heurística “h” es admisible si
h ( n )  h * ( n ),  n
en donde h*(n)=“mínima distancia desde n
hasta el objetivo”

Ejemplo:
» En el mapa de carreteras, h es admisible.
» Solución obtenida por A*:
–
–
–
–
Orden de expansión: “A, S, R, P, F, B”
Encuentra la solución: “A, S, R, P, B”
Aplicación algoritmo (ver siguiente página)
Es la mejor solución.
 Se va a tener el resultado:
» Si h es admisible, A* es completo y
óptimo.
7
Algoritmo A*, III
f=0+366=366
1
A
f=140+253=393
T
2 S
Z
f=118+329=447
f=291+380=671
5
A
f=75+374=449
F
O
f=220+193=413
R
3
f=239+178=417
S
f=300+253=553
S
f=591
B
f=450
C
f=366+160=526
6 B
f=418
C
f=615
4
P f=317+98=415
R
f=607
8
Algoritmo A*, IV

Una heurística es monótona cuando:
 nm , h ( n )  h ( m )  cos te ( nm )
nm
n

m
Si h es monótona 
h admisible.
» Dems:
» Sea n un nodo, y sea  un camino desde
n hasta el objetivo:
  n 0 n1 ... n k
donde
n0  n
y
nk
es un nodo objetivo.
h ( n )  h ( n 0 )  h ( n 0 )  h ( n1 )  h ( n1 )  ...  h ( n k )  h ( n k ) 
 cos te ( n 0 n1 )  ...  cos te ( n k 1 n k )  cos te (  )
Por tanto
h ( n )  cos te (  ),    h ( n )  h * ( n ),  n
9
Algoritmo A*, V

monótona A h=1
1
3
» Dems: Contraejemplo
h=1
B 1 C h=4
3

h admisible

Si h es una heurística
D h=0
h monótona  f creciente
» En el problema del mapa, h es monótona
(“d” es la distancia en línea recta; “C” es el
coste del arco)
h ( A)  h ( B )  d ( A, B )  C ( A, B )
» y f es creciente (ver gráfico del ejemplo)
n
h(n)
C(n,m)
m
h(m)
10
Propiedades de A*, I

A* es óptimo y completo si h es
admisible
» Grafos localmente finitos
– con factores de ramificación finitos
– donde para todo operador: C (  )    0 ,  
Demostración (intuitiva):
» Para el caso más sencillo de heurísticas
monótonas:
– En el ejemplo del mapa de carreteras se tienen
conjuntos de nivel:
– En la búsqueda uniforme se tienen bandas
circulares, mientras que si la heurística es más
exacta (h --> h*), las bandas se dirigen más
directamente al objetivo.
11
Propiedades de A*, II
» A* es óptimo
» Hipótesis
–
–
–
–
(1) h es admisible
(2) G es óptimo con coste de camino f*
*
(3) G’ es objetivo subóptimo g ( G ')  f
Dems:
Sea n un estado en el camino óptimo a G y
supongamos que el algoritmo selecciona
para expandir G’ en lugar de G, entonces
por (1) y (2)
f  f (n)
*
Y si se ha escogido G’ para expandir
f ( n )  f (G ' )
Por tanto
f *  f ( n )  f ( G ')  g ( G ')  h ( G ')  g ( G ')
Es decir
f *  g ( G ')
que es una contradicción con (3). cqd.
12
Propiedades de A*, III
» A* es completo
» Hipótesis:
–
–
–
–
(1) heurísticas monótonas,
(2) factor de ramificación b, b  
(3) coste de operadores, C (  )    0 ,  
Dems: En algún momento se llegará a que
f=“coste de algún estado objetivo”, salvo que
existan infinitos nodos con f(n)<f*, lo cual
sucedería si:
b  
 Un nodo tuviera
(¡!)
 Hubiera un camino de coste finito pero con
infinitos nodos. Esto significaría que, por (1)
y (3)
*
n / f (n)  f
Por tanto, el algoritmo debe acabar.Y si
acaba, es que encuentra una solución. cqd.
13
Propiedades de A*, IV
Si h es monótona, y A* ha expandido un
nodo n, entonces g(n)=g*(n)
» Es consecuencia directa de que:
– Un subgrafo de una heurística monótona da
lugar a una heurística monótona (que es, por
tanto, admisible), considerando la nueva
heurística h’=h-g(n)
– h admisible --> A* completo y óptimo
A* es óptimamente eficiente
» Ningún otro algoritmo óptimo expandirá
menos nodos que A*
» Si un algoritmo no expande todos los
nodos entre el origen y el contorno óptimo,
corre el riesgo de perder la solución
óptima.
– Dems: ver Dechter – Pearl (1985)
La búsqueda de coste uniforme es un
caso particular de A* (h=0)
14
Propiedades de A*, V
» Complejidad (espacial y temporal):
~
~
O ( b ), d 
f *
d
~
minimo  valor  cos tes
d  “profundidad”
de la mejor solución
Se puede demostrar que la complejidad del
algoritmo sigue siendo exponencial si no ocurre
que:
| h ( n )  h * ( n ) | O (log h * ( n ) |,  n
En casi todas las heurísticas, el error es al
menos proporcional a h* y, por tanto,
normalmente se tiene complejidad exponencial.
De todos modos, el uso de heurísticas produce
enormes mejoras con respecto a la búsqueda no
informada.
La complejidad espacial suele ser un mayor
problema que la temporal.
15
Un ejemplo de A*, I
A h=6
1
2
h=5
B
5
4
D h=2
h=5 C
4
F h=5
1
E
4
h=4
1
h=2
I
3
1
2
2
h=1
G h=4
H
3
J
h=1
5
6
6
K
L h=0
h=0
16
Un ejemplo de A*, II
f=6
A
1
f=6
D
f=6
B
3
f=7 C
2
6 f=6 H
f=9
F
E
f=11 9
E
4
f=7
H
f=9
10
G f=9
8
K
L
f=13
f=11
L
f=10
11
H
f=10
K
f=14
J
5
f=7
f=10
7
K
f=11
G
I
f=11
17
Un ejemplo de A*, III

Si hubiéramos considerado eliminación
de estados repetidos, entonces:
» Habríamos eliminado (B-->E), (E-->H) y
(G->K)

Al ser h monótona:
– A* obtiene la mejor solución
– Al eliminar estados repetidos, ya que:
» Si h es monótona, entonces si un nodo
ha sido expandido --> g(n)=g*(n)
entonces, bastaría con:
1) Si está repetido en los nodos ya
expandidos, eliminar directamente el “nodo
nuevo”
2) Si está repetido en las hojas, quedarse
con el mejor entre el nodo “viejo” y el
“nuevo”
18
Un ejemplo de A*, IV
» Si eliminamos estados repetidos, en el
caso de una h admisible pero no
monótona, podemos eliminar un nodo peor
ya expandido:
h=1
A
1
3
h=1
B
C h=4
1
3
D
Se eliminaría
f=1 1
A
h=0
f=4 B
f=5 3
C
2
4
B f=3
D
f=6
f=5
5
D
19
Problema del 8-puzle

En el problema del 8-puzle:
» Una solución típica tiene unos 20 pasos
» Factor de ramificación (b): b  3
» Por tanto: 3 20  3 . 5 * 10 9 estados
– Si se lleva la cuenta de estados repetidos, el
número de estados es 9!=362.880
» Funciones heurísticas:
– h1=número de fichas mal colocadas
– h2=suma de distancias de Manhattan de las
fichas a sus posiciones objetivo
– Son heurísticas monótonas
20
Exactitud de heurísticas, I

Factor efectivo de ramificación (b*):
» N=número de nodos expandidos por A*
(incluido el nodo de la mejor solución)
» d=profundidad de la solución obtenida por
A*
» b*=factor de ramificación de un árbol de
profundidad d y N nodos.
N  1  b *  ( b *)  ...  ( b *)
2
d

( b *)
d 1
1
b * 1
» Resolución no algebraica, sino con
métodos de cálculo numérico.
» Ejemplo: d=5, N=52 ---> b*=1.91
» Normalmente, para una heurística h,
b*=constante en varias instancias del
problema.
21
Exactitud de heurísticas, II
» Si h-->h*, entonces b*-->1.
– Si h-->0 (búsqueda de coste uniforme), entonces
b*--> b (b = cantidad operadores)
» Ejemplo (heurísticas h1 y h2 en el
problema del 8-puzle):

Si una heurística h2 domina a otra h1
(h2>=h1; suponemos h1 y h2
monótonas), entonces h1 expande al
menos los mismos nodos que h2.
» Idea intuitiva:
– Si f(n)<f*, entonces n se expande. Pero esto es
equivalente a h(n)<f*-g(n). Por tanto, si ese nodo
es expandido por h2, también lo es por h1
22
Creación de funciones
heurísticas

Método de relajación:
» Problema inicial:
– Si A es adyacente a B y B es blanco, entonces
mueve ficha desde A hasta B
» Relajando las condiciones, se obtienen
nuevos problemas:
– 1) Si A es adyacente a B, entonces mueve ficha
desde A hasta B
– 2) Si B es blanco, entonces mueve ficha desde A
hasta B
– 3) mueve ficha desde A hasta B
» Entonces:
– “h* para el problema 2)” = heurística h1
– “h* para el problema 1)” = heurística h2

Otro método:
» h1, h2, ...hn admisibles --> max{h1, h2,
...hn} también es admisible
23
Algoritmo IDA*, I


Iterative-Deepening A*-search (h
monótona).
Algoritmo:
» s=nodo inicial
» Se definen:
C0  f (s)
y para k>=1:
C k  min { f ( n ) / f ( n )  C k 1 }
n
» El algoritmo realiza búsqueda en
profundidad para los valores L=0,1,2,... en
los conjuntos:
K L  {n / f ( n )  C L }
24
Algoritmo IDA*, II

Un ejemplo sencillo (h=0):
A
1
1
B
3
F
3
C
4
G
3
H
3
D
4
I
1
J
E
2 2
K
L
2
M
Se producen 4 iteraciones: f<=0, f<=1, f<=3, f<=4
25
Algoritmo IDA*, III, a
f=6 A
1
2
B f=6
3
f=7
C
f=6
4
F
f=11
E
f=9
D
f=6
H
K
f=11
I
f=10
J
f=7
L
f=10
Ejemplo de aplicación de IDA*, iteración f<=6
26
Algoritmo IDA*, III, b
f=6 A
1
2
F
f=11
B f=6
E
f=9
G
f=9
C f=7
3
D
f=6
6
f=7
E
4
H
f=10
5
H
f=6
K
f=11
I
J
f=10 f=7
L
f=10
Ejemplo de aplicación de A*, iteración f<=7
Faltarían otras dos iteraciones: f<=9, f<=10
27
Algoritmo IDA*, IV

IDA* es completo y óptimo, pero al ser
iterativo en profundidad, necesita
menos memoria. Complejidad espacial:
~
~
O ( b * d ), d 
~
f *
minimo  valor  cos tes
d  “profundidad”

de la mejor solución
Complejidad temporal:
» En problemas como el mapa de carreteras,
cada iteración puede añadir sólo un nodo
nuevo. Por tanto, si A* expande N nodos,
IDA* necesitará N iteraciones y expandirá
1+2+...+N= O ( N 2 )
– Una solución a este problema podría ser
discretizar los posibles valores de C k (múltiplos
de  ). Se tendrían heurísticas  -admisibles.
En tal caso, el número de
f *
iteraciones sería:
28

Algoritmos de mejora
iterativa, I

Ejemplo de las N damas:
» Partiendo de N damas en el tablero,
moverlas hasta encontrar una solución.

Uso de funciones de evaluación (una
heurística h es un ejemplo).
» Búsqueda de máximos-mínimos.

Búsqueda con escalada:
» Si se puede elegir más de un sucesor que
mejore el inicial (con el mismo valor de la
función de evaluación), se elige al azar.
» Inconvenientes:
– Máximos locales
– Zonas llanas
– Crestas
29
Algoritmos de mejora
iterativa, II

Enfriamiento simulado:
» Simulated annealing
» Annealing: “Proceso de enfriar lentamente
un líquido hasta que se congela”.
– “Si la temperatura se reduce suficientemente
lentamente en un líquido, el material obtendrá su
estado de más baja energía (ordenación
perfecta)”.
» Algoritmo:

En problemas de satisfacción de
restricciones como el de las N-damas:
» Resolución de problema de 1.000.000 de
damas en menos de 50 pasos.
– Minimización de conflictos (en una columna al
azar mover una dama a la casilla que cree
menos conflictos)

Aplicados también a programación de
observaciones en el telescopio Hubble.
30
Descargar

Búsqueda heurística