PDF de programación - Búsqueda con información, informada o heurística

Búsqueda con información,

informada o heurística

1

1

Heurística

(cid:122) Del griego heuriskein (encontrar,

descubrir).
» Arquímedes (cid:198) ¡EUREKA!
» Uso en IA

– 1957, (G. Polya): Estudio de métodos para

descubrir formas de resolución de problemas

– 1963, (Newell): Proceso que puede resolver un

problema pero sin garantías de que lo haga

– El 1er. Laboratorio de Sistemas Expertos (en

Stanford) se denominó HPP: Heuristic
Programming Project

– Actualmente:

(cid:122) Cualquier técnica que mejore la ejecución en

el caso promedio durante las tareas de
resolución de problemas, pero que no
mejore necesariamente el peor caso.

2

2

Estrategias de búsqueda

informada

(cid:122) Estrategias que usan la información de

definición del problema y el coste del estado
actual al objetivo (información específica del
problema)

(cid:122) Estrategias:

» El primero mejor (Best first Search)
» Búsqueda Avara
» A*
» IDA*
» Mejora iterativa
– Hill climbing
– Simulated Annealing

3

3

Búsqueda el primero mejor, I

(cid:122) Búsqueda el primero mejor

» Se incorpora una función de evaluación

(eval-fn) que mide lo deseable de expandir
un nodo.
– Se expande el nodo con f(n) menor
– Best-first se pude implementar como una cola de

prioridad, estructura de datos que mantiene la
frontera en orden ascendente de los valores de f
– Existe una variedad importante de algoritmos el-

primero-mejor con diferentes funciones de
evaluación. Una componente esencial de los
mismos es la función heurística h(n).

(cid:122) h(n)= valor estimado del camino de coste
mínimo desde el nodo n al nodo objetivo
(cid:122) Todas las funciones heurísticas deben

cumplir:

» h(n) >= 0, para todo nodo n
» h(n) = 0, si n es un nodo objetivo

4

4

Búsqueda el primero mejor, II

A partir del algoritmo de búsqueda general, introducimos
conocimiento específico del problema al insertar los nodos
sucesores en la cola mediante una función de evaluación.

Función evaluación: medida de lo “deseable” de expandir un
nodo.

Se expande primero el nodo no expandido más “deseable”

5

5

Búsqueda avara, I

(cid:122) Búsqueda el primero mejor donde

» eval-fn(nodo) = h(nodo)

(cid:122) Suele encontrar soluciones rápido

» No suelen ser óptimas
» No siempre se encuentran (estados

repetidos (cid:198) ciclos)
– Ej. de situación anómala: Ir de Iasi a Fagaras. Si
no eliminamos repeticiones se entra en un ciclo.

I

V
N

I

» Ejemplo: Mapa de carreteras

– Objetivo: Viajar desde Arad hasta Bucarest.
– Heurística h: distancias medidas en línea recta

(sobre el mapa) entre Arad y Bucarest
– Solución obtenida por búsqueda avara:

(cid:122) Nodos expandidos Encuentra el camino

» “Arad, Sibiu, Fagaras, Bucharest”,

(cid:122) No es óptima: Es más corto

» “Arad, Sibiu, Rimnicu, Pitesti, Bucharest”
6

6

374

366

329

7

7

Búsqueda avara: ejemplo del

mapa de carreteras

2. Expandir: Sibiu (h menor, 253)

Inicio por ciudad de partida

1. Expandir: Arad

3. Expandir: Fagaras (h menor, 178)

4. Se llega a Bucharest, solución encontrada
8

8

Búsqueda avara, II

(cid:122) En resumen:

» No es óptimo ni completo.
» En el peor caso:

– Complejidad temporal:

– Complejidad espacial:

( mbO
( mbO

)
)

(cid:122) Se almacenan todos los nodos en memoria
(cid:122) m = máxima profundidad del árbol de

búsqueda

9

9

Algoritmo A*, I

(cid:122) 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.

(cid:122) 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

(cid:122) Algoritmo:

function A*-SEARCH (problem)
returns a solution or failure

return BEST-FIRST-SEARCH(problem, g+h)

10

10

Algoritmo A*, II

(cid:122) Heurística admisible:

» DEF: Una función heurística h es admisible

si

nh
)(

≤

h

(*

n

),

n
∀

» en donde h*(n)=“mínima distancia desde n

hasta el objetivo”

» Las heurísticas admisibles son optimistas

en el sentido de que el coste de alcanzar el
objetivo h(n), es menor de lo que lo es
actualmente h*(n).

(cid:122) 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 (A* es óptimo)

11

11

Algoritmo A*, III

f=0+366=366
A

1

f=140+253=393

2

S

T

f=118+329=447

Z

f=75+374=449

5

A

f=291+380=671

O

F
f=239+178=417

f=220+193=413
R

3

S

f=300+253=553

S
f=591

B
f=450

C

f=366+160=526

4
f=317+98=415

P

B
6
f=418

C
f=615

R
f=607

12

12

Algoritmo A*, IV

(cid:122) Una heurística es monótona cuando:

Γ∀

nm

nh
)(,

−

n

mh
(
nmΓ

)

≤

cos

te

(

Γ
nm

)

m

(cid:122) Si h es monótona h admisible.

⇒

» Dems:
» Sea n un nodo, y sea un camino desde

Γ

n hasta el objetivo:
...10Γ=Γ
kn
nn
kn
n =0
n
donde y es un nodo objetivo.
h n
h n
h n
h n
(
(
( )
)
)
(
)
−
=
−
k
k
0
h n
h n
h n
)
(
)
)
(
(
...
−
=
+
− −
0
1
1
te
te
...
(
cos
)
(
cos
Γ
+ +
Γ
≤
Por tanto

h n
h n
(
(
)
≤
k
k
1
−
te
te
(
cos
)
=
Γ
h monótona

=
h n
(

)
k
1
−
)
=

+
cos

n
k

n
k
1
−

n n
k
0

n n
0 1

)

−

(

Γ

)

h n
) 0
0(
− =
h
h n
( )
⇒
≤

h n
cos
( )
≤
n
n
*( ),
∀

te

( ),
Γ ∀Γ ⇒

13

13

Algoritmo A*, V

» Teorema: h admisible monótona

– Dems: Contraejemplo
3

h=1

⇒
h=1
A
1

C

h=4

1

B
3
D

h=0

⇔
» Teorema: h heurística monótona f

creciente
– En el problema del mapa,

(cid:122) h es monótona (d: distancia en línea recta;

“C”: coste del arco)
BAd
(

BhAh
(

−

≤

)

)

(

,

)

≤

BAC

(

,

)

(cid:122) f es creciente (ver gráfico del ejemplo)

n

h(n)

C(n,m)

m

h(m)

14

14

Propiedades de A*, I

(cid:122) Teorema: A* es óptimo y completo si h es

admisible
» Válido en grafos localmente finitos

– con factores de ramificación finitos
C
– donde para todo operador:

,0

)(
Γ∀>≥Γ

δ

» Conjuntos de nivel (caso de heurísticas monótonas):

– Si búsqueda uniforme (h(n)=0): bandas circulares
– si la heurística es más exacta (h (cid:198) h*), los conjuntos

de nivel se dirigen directamente al objetivo.

15

15

Propiedades de A*, II

» Dems: A* es óptimo
» Hipótesis

– (1) h es admisible
– (2) G es óptimo con coste de camino f*
') >
– (3) G’ es objetivo subóptimo
– Dems:

g G
(

*

f

Como G’ es subóptimo
+

g G
(

f G
(

')

')

=

h G
(

')

=

g G
(

')

>

*

f

Supongamos que el nodo n está en el camino al

óptimo

f n
( )

=

g n
( )

+

h n
( )

≤

*

f

Por tanto
f n
( )
≤

f

*

<

f G
(

')

=

g G
(

')

+

h G
(

')

=

g G
(

')

que es una contradicción con (3). cqd.

16

16

Propiedades de A*, III

» Dems: A* es completo
» Hipótesis:

– (1) heurísticas monótonas,
– (2) factor de ramificación b,
C
– (3) coste de operadores,
– (4) f* es finito
– Dems: En algún momento se llegará a que

< ∞b
)(
Γ∀>≥Γ
δ

,0

f=“coste de algún estado objetivo”, salvo que
existan infinitos nodos con f(n)<f*, lo cual
sucedería si:

= ∞b

(cid:122) Un nodo tuviera (contradice (2))
(cid:122) Hubiera un camino de coste finito pero con

infinitos nodos. Esto significaría que, por (1),
(3) y (4)

n f n
/
( )
∃

>

*

f

Por tanto, el algoritmo debe acabar.Y si
acaba, es que encuentra una solución. cqd.

17

17

Propiedades de A*, IV
(cid:122) Proposición: 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 (cid:198) A* completo y óptimo

(cid:122) A* es óptimamente eficiente

» Ningún otro algoritmo óptimo expandirá

menos nodos que A* (salvo muerte súbita
entre nodos n con f(n)=f*)
– Si algún algoritmo expande menos nodos corre

el riesgo de perder la solución óptima

» 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)

18

18

Propiedades de A*, V
» Complejidad (temporal y espacial):

~

bO d

(

~
d

),

=

f
*
valor

−

cos

tes

minimo

−

– Se puede demostrar que la complejidad del

|

algoritmo sigue siendo exponencial salvo que el
error en la función heurística no crezca más
rápido que el logaritmo del coste del camino
óptimo, es decir:
n
h n
n
*( ) |
( )
≤
∀
Siendo h*(n) el coste óptimo de alcanzar el
objetivo desde n.

(log *( )),

O

n

−

h

h

– En casi todas las heurísticas, el error es al

menos proporcional al coste del camino y, por
tanto, 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, al requerir mantener
en memoria todos los nodos generados.

19

19

h=5
B

5

h=5

F

1

Un ejemplo de A*, I

h=6

A

2

h=5

C

1

h=4

E

3

1

4

2

4

h=2

D

1

2

4

I

h=2

h=4

G

6

h=1

3

H

5

J

h=1

6

K

h=0

h=0

L

20

20

Un ejemplo de A*, IIa

1

h=5, f=6=1+5
B

2

4

1

A h=6, f=6=0+6
2
h=5, f=7=2+5
C

6

5 4

1

1

f=6=5+1
H

4

3

D h=2, f=6=4+2

4

I

f=10=8+2
5

2

5

J
f=7=6+1

f=10=10+0
L
12

f=7=3+4

E

7

3

9

6

K

f=9=5+4
E
10

3

H

f=9=8+1
11

2

G

5

F
f=11=6+5
2

f=11=7+4
G

6

f=14=14+0
K

f=11=11+0
8

H

f=9=5+4
f=7=6+1
6
5
K f=11=11+0

K f=12=12+0

L

f=11=11+0

L
f=13=13+0

En caso de empate se toma
el nodo más profundo

21

21

Un ejemplo de A*, IIb

1

h=5, f=6=1+5
B

2

4

1

A h=6, f=6=0+6
2
h=5, f=7=2+5
C

5

5 4

1

1

f=6=5+1
H

4

3

D h=2, f=6=4+2

4

I

f=10=8+2
5

2

6

J
f=7=6+1

f=10=10+0
L
12

f=7=3+4

E

7

3

10

6

K

f=9=5+4
E

9

3

H

f=9=8+1
11

2

G

5

F
f=11=6+5
2

f=11=7+4
G

6

f=14=14+0
K

f=11=11+0
8

H

f=9=5+4
f=7=6+1
6
5
K f=11=11+0

K f=12=12+0

L

f=11=11+0