Upload
jair-saint
View
218
Download
0
Embed Size (px)
DESCRIPTION
Inteligencia Artificial
Citation preview
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 1/7
Búsqueda en amplitud
Expandir nodo no expandido menos profundo
Implementación:
fringe es una cola FIFO, es decir, los nuevos sucesores van al nal
Diagrama:
Propiedades de la búsqueda en amplitud
• Completar? Sí (si b es nito)• Tiempo? ! b ! b" ! b# ! $$$ ! bd ! b (bd%) & O (bd ! )• espacio? O (bd ! ) (cada nodo mantiene en la memoria)• óptima? Sí (si el costo & por paso)• El espacio es el problema m's grande (m's de tiempo)
Búsqueda Uniforme costo
• mpliar el menor costo de nodo no expandido
Implementación:
• franja & cola ordenada por coste de la ruta• Euivalente a la amplitud primer paso si cuesta todos iguales• Completar? Sí, si el costo paso * +• Tiempo? -e nodos con g . costo de la soluci/n /ptima, O
(bceiling (0 1 2 +)) donde 0 1 es el coste de la soluci/n /ptima• espacio? -e nodos con g . costo de la soluci/n /ptima, O
(bceiling (0 1 2 +))• óptima? ! " nodos expandidos con el n de aumentar g (n)
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 2/7
Búsqueda en profundidad
Expandir profundo nodo no expandido
Implementación:
Flecos (%fringe%) & cola 3IFO, es decir, poner sucesores al frente
Propiedades de la búsqueda en amplitud
• Completar? 4o5 falla en espacios innitos de profundidad, espacios conbucles
$ 6odicar para evitar estados repetidas a lo largo de camino"$ completar en espacios nitos
• Tiempo? O (bm)5 terrible si m es muc7o ma8or ue d$ pero si las soluciones son densos, puede ser muc7o m's r'pido ue la
amplitud%primera
• espacio? O (bm), es decir, el espacio lineal9• óptima? 4o
Búsqueda en profundidad limitada
# :;sueda en profundidad con la profundidad límite de l, es decir, los nodos aprofundidad l no tienen sucesores
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 3/7
Iterati$e deepening searc%
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 4/7
Propiedades de la búsqueda profundi&ación iterati$a
4;mero de nodos generados en una b;sueda en profundidad limitado aprofundidad d con ramicaci/n factor de b5
4-3S & b< ! b ! b" ! $$$ ! bd%" ! bd% ! bd
• 'úmero de nodos generados en una búsqueda de profundi&acióniterati$a a profundidad d con rami(cación factor de b:
4I-S & (d ! ) b< ! db = ! (d%) b = " ! $$$ ! #bd%" ! "bd% ! bd
"$ Para b # <, d & >,#$ 'D) # ! < ! << ! <<< ! <$<<< ! <<$<<< & $$ 'ID # @ ! >< ! << ! #<<< ! "<$<<< ! <<$<<< & "#$>@>$ *$er%ead # ("#>@ % ) 2 $ & A
Propiedades de la búsqueda profundi&ación iterati$e
• Completar? Sí • Tiempo? (d ! ) b< ! b ! d (d%) b" ! $$$ ! bd & O (bd)• espacio? O (bd)
*ptimal? Sí, si el costo paso &
Summary of algorithms
+, searc%
• Idea: evitar la ampliación de caminos que están caros
• Función de evaluación f (n) = g (n) h (n)
• g (n) = costo hasta ahora para llegar a n
• h (n) = costo estimado de na meta
• f (n) = calcula el coste total de camino a trav!s de n a la meta
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 5/7
+dmissible %euristics
B Cna 7eurística 7 (n) es admisible si para cada nodo n, 7(n) . 7 1 (n), donde 7 1 (n) es el verdadero costo paraalcanDar el estado nal del n$
B Cna 7eurística admisible nunca se sobreestima el costepara llegar a la meta, es decir, es optimista
B Eemplo5 7S3- (n) (nunca sobreestima la distancia real decarretera)
eorema5 Si 7 (n) es admisible, 1 utiliDando GEE%SEG0Hes /ptima
*ptimalit- of +, .proof/
Supongamos ue algunos " obetivo sub/ptima se 7agenerado 8 est' en la frana$ Sea n un nodo no expandidoen la frana tal ue n est' en el buen camino m's corto7acia una meta /ptima $
7/17/2019 Algoritmos de Búsqueda
http://slidepdf.com/reader/full/algoritmos-de-busqueda-568e40cf9293e 6/7
B f (") & g ("), 8a ue 7 (") & <
B g (")J g () desde " es sub/ptima
B f () & g () desde 7 () & <
B f (")J f () desde arribaB f (")J f () desde arriba
B 7 (n) . 7 = 1 (n) desde 7 es admisible
B g (n) ! 7 (n) . g (n) ! 7 1 (n)
B f (n) . f ()
Kor lo tanto f (")J f (n), 8 1 4unca seleccionar' " para la
expansi/nConsistent %euristics
B Cna 7eurística es consistente si para cada nodo n, cada sucesor n Lde ngenerada por cualuier acci/n a,
7 (n) . c (n, a, n L) ! 7 (nL)
B Si 7 es consistente, tenemos
f (n L) & g (n) ! 7 (nL)
& (n) ! c (n, a, n L) ! 7 (nL)
* g (n) ! 7 (n)
& F (n)
B es decir, f (n) es no decreciente a lo largo decualuier camino$
eorema5 Si 7 (n) es consistente, 1 usando GMFI0O%SEG0H es /ptima
*ptimalit- of +,
B 1 expande nodos con el n de incrementar el valor f
B Koco a poco aNade F%contornos de nodos
0ontorno i tiene todos los nodos con f & , donde P !