INTELIGENCIA ARTIFICIAL
BUSQUEDAS
INFORMADAS
Sesión 4
Ing. Victor Jaime Polo Romero
1
Búsquedas Informadas
Heurísticamente
La heurística son aquellos
criterios, métodos o principios
para decidir cual de muchas
alternativas de acción puede
ser la más efectiva para
cumplir con un objetivo.
Ing. Victor Jaime Polo Romero
2
La eficiencia en la búsqueda
puede mejorar en gran medida
si existe una forma de ordenar
las selecciones de modo que las
más prometedoras se exploren
primero.
Ing. Victor Jaime Polo Romero
3
Suponga que se desea hallar una trayectoria
de una ciudad a otra mediante un mapa de
carreteras como en la figura. Su trayectoria
debe comenzar en la ciudad S y terminar en
la ciudad G, su meta.
4
4
A
C
B
3
5
5
S
G
4
3
2
D
4
E
Ing. Victor Jaime Polo Romero
F
4
Además, se tiene las distancias de los nodos a
la meta.
B
C
A
10.4
6.7
4.0
11.0
S
G
8.9
D
E
6.9
Ing. Victor Jaime Polo Romero
F
3.0
5
Método Ascenso de Colina
El ascenso de colina se procede
como en el caso de la búsqueda
en profundidad, excepto que se
ordenan las selecciones de
acuerdo con alguna medición
heurística de la distancia que
queda por recorrer a la meta.
Ing. Victor Jaime Polo Romero
6
Cuanto mejor sea la medición
heurística de la distancia que
queda por recorrer a la meta,
mejor será el ascenso en colina
con relación a la búsqueda en
profundidad normal.
Ing. Victor Jaime Polo Romero
7
S
10.4
8.9
D
A
6.9
10.4
E
A
3.0
6.7
B
F
G
Ing. Victor Jaime Polo Romero
8
Búsqueda en Haz
La búsqueda en haz es parecida a la
de amplitud en cuanto que avanza
nivel por nivel. Sin embargo, a
diferencia de esta, la búsqueda en
haz se mueve hacia abajo solo a
través de los mejores W nodos de
cada nivel y los otros nodos se
ignoran.
Ing. Victor Jaime Polo Romero
9
En consecuencia, el número de
nodos explorados se mantiene
manejable, aun cuando haya
gran
cantidad
de
ramificaciones y la búsqueda
sea profunda.
Ing. Victor Jaime Polo Romero
10
S
W=2
S
10.4
D
A
8.9
B
4.0
B
8.9
D
10.4
A
S
E
B
6.9
C
F
B
D
A
D
A
3.0
6.7
6.9
Callejón sin
salida
S
E
A
D
E
C
6.7
D
A
D
B
E
Callejón sin
salida
Ing. Victor Jaime Polo Romero
E
A
10.4
A
4.0
F
C
G
11
Búsquedas optimas
LA MEJOR TRAYECTORIA
Se atenderá a la longitud de la mejor trayectoria.
Ing. Victor Jaime Polo Romero
12
Búsqueda de ramificación y cota
Expande la trayectoria parcial de menor costo
El esquema de ramificación y cota
siempre se mantiene al tanto de
todas las trayectorias parciales que
compiten para su consideración
posterior. La más corta de ellas se
extiende un nivel, creándose tantas
trayectorias parciales nuevas como
ramas existan.
Ing. Victor Jaime Polo Romero
13
En seguida se consideran estas
nuevas trayectorias junto con las
anteriores restantes de nuevo se
extiende la mas corta.
Este proceso se repite hasta llegar
a la meta a través de una
trayectoria.
Ing. Victor Jaime Polo Romero
14
Dado que la trayectoria más corta es
la que siempre se escoge para su
extensión, la trayectoria que primero
encuentra la meta es probable que
sea la óptima.
Ing. Victor Jaime Polo Romero
15
Nota:
Para convertir lo probable en
cierto, hay que extender todas las
trayectorias parciales hasta que
tenga una longitud igual o mayor
que la trayectoria completa mas
corta.
Ing. Victor Jaime Polo Romero
16
La razón es que el ultimo paso
para alcanzar la meta puede
ser lo suficientemente largo
para hacer que la supuesta
solución resulte mas larga que
una o más trayectorias
parciales.
Ing. Victor Jaime Polo Romero
17
Puede ser que en un solo paso
pequeño extienda una de las
trayectorias parciales al punto
solución. Para asegurar de que esto
no suceda, en lugar de terminar al
encontrar una trayectoria, termine
cuando la trayectoria parcial mas
corta tenga una longitud mayor que la
trayectoria completa mas corta.
Ing. Victor Jaime Polo Romero
18
S
S
3
D
A
La más corta de
ellas se extiende un
nivel
4
7
S
D
A
B
8
E
A
D
9
10
11
D
A
7
B
D
4
Se consideran estas
nuevas trayectorias
junto con las anteriores
restantes de nuevo se
extiende la mas corta.
B
8
S
11
B
S
D
A
8
D
9
E
A
D
A
7
F
B
8
D
9
A
E
C
12
E
11
B
F
10
6
Ing. Victor Jaime Polo Romero
19
S
S
D
A
B
11
12
C
A
D
E
B
E
B
E
9
10
D
A
F
11
10
11
12
C
E
E
B
15
C
11
12
E
E
A
E
F
10
D
A
10
11
F
D
D
B
S
A
B
B
13
14
S
E
A
D
B
B
13
B
11
F
E
A
D
10
11
C
12
E
Ing. Victor Jaime Polo Romero
15
B
E
14
13
F
B
B
A
15
11
C
15
F
2013
G
Termine cuando la trayectoria parcial mas corta tenga una
longitud mayor que la trayectoria completa mas corta.
S
D
A
B
11
E
C
D
14
E
F
B
16
15
E
A
D
13
F
14
B
F
B
A
15
C
G
13
15
Ing. Victor Jaime Polo Romero
21
Agregar subestimaciones para
mejorar la eficiencia
En algunos casos se puede mejorar en
gran
medida
la
búsqueda
de
ramificación y cota mediante el uso de
conjeturas acerca de las distancias
distantes, así como de hechos sobre
las distancias ya obtenidos.
Ing. Victor Jaime Polo Romero
22
Ahora si encuentra una trayectoria total al
extender de manera repetida la trayectoria
con la distancia subestimada mas corta no
necesita seguir adelante una vez que
todos los cálculos de distancias parciales
sean mayores que la mejor distancia de
trayectoria completa encontrada hasta
ese punto.
Ing. Victor Jaime Polo Romero
23
Puede detenerse debido a que la distancia
real a lo largo de una trayectoria completa
puede ser menor que una subestimación
de tal distancia. Si se puede garantizar
que todas las estimaciones de la distancia
restante son subestimaciones, entonces
no puede haber lugar a errores.
Ing. Victor Jaime Polo Romero
24
S
S
D
13.4 A
D
A
19.4
12.9
13.4
E
A
17.7
13.4
D
A
D
A
19.4
19.4
13
S
S
13.4
F
B
A
E
E
A
12.9
17.7
Ing. Victor Jaime Polo Romero
B
F
G
13
25
Busqueda en Escalada
• La técnica de escalada es la evolución de
la técnica de profundidad en la que cada
nodo se dispone en una forma de evaluar
cómo está de cerca o de lejos la solución.
La forma más común de evaluar es la
función de evaluación.
Ing. Victor Jaime Polo Romero
26
Ing. Victor Jaime Polo Romero
27
• f(nodo)= # de casillas bien colocadas (maximizo)
• f’(nodo)= # de casillas mal colocadas (minimizo)
• Como ejemplo del juego 8-puzzle se puede definir una
función de evaluación que fuera igual:
• f(nodo)= # de casillas bien colocadas (máximo)
• Que devuelven un número que representa como está de
cerca un determinado estado de la solución, cuanto
mayor sea el número se estará cerca de la solución.
• Por tanto si se tiene que elegir entre varios estados se
debería escoger aquel, que tendría un valor mayor de
esta función, es decir es una función que se debe
maximizar.
Ing. Victor Jaime Polo Romero
28
Ing. Victor Jaime Polo Romero
29
• procedimiento escalada (estado inicial estado final)
• N = estado inicial; Exito = Falso.
• Hasta que éxito.
– Generar los sucesos de N
– Si algún sucesor es estado final entonces Exito = Verdadero.
• Si No
• - Evaluar cada nodo como la función de evaluación
• - N = mejor sucesor
– Si Exito
• entonces Solución = camino desde nodo del estado-inicial al nodo
N por los
• punteros.
• Si No
• Solución = Fracaso.
•
• La técnica de escalada exagera los problemas de la profundidad en
el sentido de que no asegura de que se alcance la solución óptima
relacionada con esto existen dos problemas que ocurren a menudo
cuando se utiliza escalada:
Ing. Victor Jaime Polo Romero
30
Otras Búsquedas
Ing. Victor Jaime Polo Romero
31
Se tiene el Siguiente cuadro de Rutas
2
I
5
A
B
4
Ruta
5
3
I-D-E-F-M=15
6
D
IM =11
C
2
E
4
3
M
F
AM =10.4 BM=6.7 CM=4.0
DM=8.0 EM=6.9
FM=3.0
Ing. Victor Jaime Polo Romero
32
Búsqueda Avara - Greedy
Es cuando se reduce al mínimo el costo
estimado para alcanzar la meta, h(n).
Esta Búsqueda expande el nodo que parece
estar mas cerca al objetivo.
Ing. Victor Jaime Polo Romero
33
I
I
D
A
8
10.4
D
A
E
3
I
A
D
F
M
E
6.9
Ing. Victor Jaime Polo Romero
34
Metodo del Algoritmo A*
Idea: Evitar expandir caminos que ya
acumulan un costo elevado
Tener en cuenta lo que ha costado llegar
al nodo actual.
Ing. Victor Jaime Polo Romero
35
Observaciones a la búsqueda A*
Permite reducir al mínimo el costo de
encontrar la meta h(n) (costo estimado de
la ruta más barata que va de n a la meta)
Nodo de
comienzo
n
g(n)
meta
h(n)
Búsqueda A* utiliza f(h)=g(n)+h(n)
Ing. Victor Jaime Polo Romero
36
Algoritmo A*
• Función de evaluación: f(n) = g(n) + h(n)
– g(n): costo para llegar al nodo n (lo recorrido).
– h(n): costo estimado para llegar a un nodo
solución
– desde el nodo n (estimado de lo que falta por
recorrer).
– f(n): costo total estimado del camino para
llegar al objetivo a través del nodo n.
Ing. Victor Jaime Polo Romero
37
I
I
D
A
6+8=14
2+10.4=12.4
I
D
A
B
5+6.7=11.7
A
D
B
D
E
I
2+6.9=8.9
D
A
D
3+8=11
D
B
E
5+6.7=11.7
Ing. Victor Jaime Polo Romero
B
F
4+3=7
38
I
D
A
D
B
E
B
F
M
Ing. Victor Jaime Polo Romero
39
Trabajo
Ing. Victor Jaime Polo Romero
40
Estado Inicial : Arad – Estado Meta : Bucharest
Ing. Victor Jaime Polo Romero
41
Ing. Victor Jaime Polo Romero
42
Descargar

Busqueda en Escalada