Tema 3: Búsqueda Heurística
(Tema 9 Nilsson)
En donde veremos cómo la información sobre el
espacio de estados puede impedir a los algoritmos
cometer un error en la oscuridad.
1
1. ¿Qué es la heurística?.
2. Búsqueda preferente por lo “mejor” y funciones de
evaluación.
a. Búsqueda Avara (Greedy).
b. Búsqueda A*.
3. Funciones heurísticas y eficiencia del proceso de
búsqueda.
4. Introducción a los algoritmos bioinpirados.
5. Bibliografía.
2
TSP (traveller salesman problem)
181.440 rutas distintas
30
4 x 1031 !!!
Problema NP-hard ó NP-completo resol. en t exponencial. 3
HEURÍSTICA RAE: En algunas ciencias, manera de
buscar la solución de un problema mediante
métodos no rigurosos, como por tanteo, reglas
empíricas, intuición.
4
5
6
7
3. Búsqueda primero el mejor, búsqueda
heurística ó informada y funciones de evaluación.
Esta sección muestra cómo una estrategia de búsqueda informada
(la que utiliza el conocimiento específico del problema más allá de la
definición del problema en sí mismo), puede encontrar sol. de una
manera más eficiente que una estrategia no informada.
Función de evaluación heurística f(n): “distancia heurística” al
siguiente nodo. Produce un valor que representa lo deseable (o
indeseable) que sería la expansión de un nodo n.
Búsqueda primero el mejor: Se expande primero el
nodo que proporciona un mejor valor (f<) para la función
de evaluación se expanden 1º los nodos más cercanos
al objetivo).
Mecanismos: Avara.
A*. 8
Búsqueda 1º el mejor
h(n) = función heurística.
Al llegar a n, se expande hacia el nodo de <
h(n).
f(n)=h(n)
h1 h2
Nodo meta (h2 <
h1)
9
Reducir al mínimo el coste estimado para alcanzar una meta.
Formalmente h puede ser cualquier función.
Requisito h(n) = 0 si y sólo si n es una meta.
Problema 1: puzzle de ocho piezas:
h(n) = número de fichas descolocadas.
Problema 2: encontrar el camino para ir desde Arad a
Bucarest.
h(n) = distancia en línea recta (dlr) entre n y la ubicación
de la meta. Expande el nodo que parece estar más cercano
al objetivo.
10
h
=
11
No se obtienen del enunciado del probl hdlr =
Dist real entre ciudades
12
Búsqueda avara
Expansión: Arad, Sibiu, Timisoara,
Zerind, Fagaras, Riminicu, Arad,
Oradea, Sibiu, Bucarest
13
14
ARAD SIBIU FAGARAS BUCAREST (450km) no es
una solución óptima. Solución óptima: ARAD SIBIU
RIMMICU PITESTI BUCAREST (418 km).
La búsqueda avara se parece y sufre los mismos defectos
que la BPP:
* No es óptima.
* Es incompleta (puede ir hacia abajo en un camino ∞ y nunca
volver).
* Complejidad temporal O(bm), m profundidad máxima del
espacio de búsqueda y b= factor de ramificación.
* Complejidad espacial O(bm). Guarda todos los nodos en
memoria.
* Una buena función heurística permite disminuir notablemente
la complejidad tanto espacial como temporal.
15
al objetivo pasando por n.
16
Shakey (It
[Link] shakes)
tecnologia/shakey-robot-
inteligencia_artificial-
coche_autonomo_0_632037257.html
Presentado por primera vez en
1968 por Peter E. Hart, Nils J.
Nilsson y Bertram Raphael.
1966-72. Shakey es un
robot movil, construido en el
Stanford Research Institute
(SRI), equipado con
sensores de tacto y
cámaras. Shakey habita en
una de varias habitaciones
interconectadas, en medio
de un montón de bloques de
madera.
Si a Shakey se le pide
mover un objeto, desde un
origen a un destino
determinado, éste, busca la
manera más óptima de
llevarlo a cabo utilizando los
Búsqueda A*
Presentado por primera vez en 1968 por Peter E.
Hart, Nils J. Nilsson y Bertram Raphael, (Robot
SHAKEY)
El algoritmo A* encuentra, siempre y cuando se
cumplan unas determinadas condiciones, el camino de
menor coste entre un nodo origen y uno objetivo
pasando por n.
g(n)
n f(n)= g(n) + h(n)
h(n)
18
A* es óptimo y completo si h(n) es una heurística admisible (p. ej. hdlr),
es decir, con tal de que h(n) nunca sobreestime el coste de alcanzar el
objetivo.
Ya que g(n) es el coste exacto para alcanzar n f(n) nunca sobreestima
el coste verdadero de una sol. a través de n.
El t computacional no es la principal desventaja de A* . Como mantiene
todos los nodos generados en memoria, A* se queda sin mucho espacio
antes de quedarse sin t. A* no es práctico para probs. grandes.
Modernos algoritmos solucionan este prob., [Link]. los algoritmos genéticos
19
20
19
2 8 2 8
1 6 3 1 6 3
7 5 4 7 5 4
9
2 8 3 2 8 3
1 6 18 1 5 6
7 5 4 2 8 3 7 4
1 6
7 5 4 2 3
4 1 8 6
7 5 4
2 8 3 17
1 6 4
2 8 3 2 8 3
BPA
7 5
1 4 5 1 6
8 7 6 7 5 4
2 8 3 2 8 3
1 4 16 1 4 5
7 6 5 2 8 7 6
1 4 3 1 2 3
7 6 5 2 8 7 8 4
1 4 3 6 5
7 6 5
15
2 3 2 3 4 27
1 8 4 1 8 1 2 3 G o al
1 3 7 7 6 5 7 6 5 8 4
Start 2 8 3 2 8 3 2 3 7 6 5 node
1 6 4 1 4 1 8 4
node 7 5 7 6 5 7 6 5 14 26 2 8 3
7 1 4
2 3 1 2 3 6 5
1 8 4 8 4
7 6 5 7 6 5 2 8 3
7 4
6 1 5
13 25 8 1 3
2 8 3 2 8 3 2 4
7 1 4 7 1 4 7 6 5
6 5 6 5
8 3
6 2 1 4
2 8 3 7 6 5
1 4
24
7 6 5 8 3 2 8 3
2 1 4 6 7 4
12 7 6 5 1 5
8 3
2 1 4 2 8 3
6 7 4
7 6 5 23 1 5
2 2 8 3
6 7 4 2 8 3
2 8 3 1 5 6 4 5
1 6 4 1 7
7 5
2 8
11 22 6 4 3
2 8 3 2 8 3 1 7 5
6 4 6 4
1 7 5 1 7 5 2 3
6 8 4
5 1 7 5
2 8 3
6 4 21 2 3
1 7 5 2 3 6 8 4
6 8 4 1 7 5
1 7 5
8 6 3
2 4
1 7 5
10 20
8 3 8 3 8 3
2 6 4
1 7 5
2 6 4
1 7 5
2 6 4
1 7 5 21
B. avara
22
A*
Volvemos atrás
cuando el valor
de f
supera al valor de
f de un nodo
anterior.
23
Heurística: No se obtienen del enunciado del probl hdlr =
Dist real entre ciudades
24
Búsqueda A*
g+h
25
B avara = 450
26
2018 WAYMO Google ; UBER
27
DARPA: Defense Advanced Research Projects
Agency
DARPA Desert Challenge 2005 Stanley:
[Link]
v=M2AcMnfzpNg
DARPA Urban Challenge 2007:
[Link]
WAYMO GOOGLE: [Link]
v=ObHoEuQ_rYU
ACCIDENTE UBER 2018:
[Link]
70_604181.html
[Link]
autonomo-de-uber-si-habria-detectado-al-peaton- 28
4. Funciones heurísticas y eficiencia del proceso de
búsqueda.
h1 Cantidad de números que están en lugar incorrecto. (h 1 = 8).
h2 Suma de las distancias Manhattan (verticales y horizontales) que
separa a los números de su posición meta. (h2 = 18).
h2 domina a h1 , por lo tanto h2 es mejor heurística que h1.
Se comprueba experimentalmente que es siempre mejor usar una h
con valores más altos, a condición de que no sobreestime y que el t
computacional de la h no sea demasiado grande. 29
Incluir aptdo. 9.3 Nilsson en 2020-2021
30
31
(para BP)
(No se cuentan las barreras.) (para Bavara y A*)
32
BP: Sol. correcta (s.e.u.o)
0 I
1 Q 4 W
2 P
5 K
3 G
6 C
7 A
8 B
9 D
10 M
11 F
33
Sol. Incorrecta
s.e.u.o.
34
35
36
Problemas Nilsson:
9.1 ; 9.2.
Probls. Billhardt et al.
1.3 1.10
37
NILSSON
38
39
9.1.2.
9.1.
h= 4-g
Hasta 16
posibilidades,
pero
sólo 3 si
aplicamos
simetrías.
41
NILSSON
42
9.2.
Sol: h1 = nº de discos no colocados en la varilla
final.
Otra mejor: h= h1 + 1 por cada disco encima de
otro cualquiera que haya que mover al disco meta.
43
Problemas Billhardt
44
45
46
Desde
cada nodo
5 hasta la
meta el
coste es 5
47
48
49
50
51
52
Mundo de
bloques.
Nisson. 7.2.
53
Ej. 1.6 BILLHARDT
54
55
56
57
58
59
Ej. 1.9
60
61
62
63
64
65
5. Bibliografía
Inteligencia Artificial, una nueva síntesis, Nils J.
Nilsson.
Inteligencia Artificial, un enfoque moderno,
Stuart Russell & Peter Norvig.
[Link]
(página del Russell).
[Link]
(transparencias IA).
[Link]
[Link] (transparecias IA).
[Link]
(revista de inteligencia artificial).
[Link] (portal de
Carlos H. Von der Becke).
66
