Upload
juan-carlos-rodriguez
View
107
Download
0
Embed Size (px)
Citation preview
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 1/75
Ejercicio 2Búsqueda no informada
Trabajo realizado por:– David García Villaescusa
– Francisco Javier Gómez González
– Juan Carlos Rodríguez García– Álvaro Solana Sánchez
13 de Octubre de 2011
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 2/75
Búsqueda no informada 2
Contenido
● Introducción.● Búsquedas en anchura.● Búsquedas en profundidad.● Búsquedas de coste uniforme.● Resolución de ejericicios utilizando diferentes
técnicas.– Problema 1
– Problema 2
– Problema Extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 3/75
Búsqueda no informada 3
Introducción
● Queremos encontrar una secuencia de operadores que,partiendo del estado inicial, obtenga un estado final.
● La exploración del grafo de estados:
– En cada momento se analiza un estado actual.
– Si el estado actual es final, acabar. En caso contrario,obtener los sucesores del estado actual.
– Elegir un nuevo estado actual.
– Repetir el proceso mientras haya estados por analizar.
● La elección del estado actual en cada momento determina unaestrategia de búsqueda.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 4/75
Búsqueda no informada 4
Introducción●
El nodo de un árbol de búsqueda contiene el estado y lasecuencia de operadores que conducen al estado desde elinicial.
● El nodo raíz del árbol de búsqueda contiene: el estado inicial +la secuencia vacía.
● Los nodos hoja del árbol de búsqueda contienen: nodos cuyaexpansión no ha producido sucesores nuevos y nodospendientes de considerar.
● Hay 3 tipos de nodos:
– Nodo visitado: hemos chequedado si es estado final.– Nodo abierto: generado pero no visitado.
– Nodo cerrado: visitado y expandido.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 5/75
Búsqueda no informada 5
Búsqueda en anchura
● Es completo, si existe solución, la encuentra.
● Es óptimo para operadores de coste constante. Pues siempreencontraría la solución de menor número de niveles del árboldesde la raíz.
● Complejidad exponencial tanto en tiempo como en espacioincluso en el mejor caso.
● No es óptimo para operadores cualesquiera.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 6/75
Búsqueda no informada 6
Búsqueda en anchura
● Los nodos se visitan y se expanden por niveles.
●
La estructura para los nodos abiertos es una cola (FIFO).● Un nodo es visitado cuando todos los nodos de los niveles
superiores y sus hermanos precedentes han sido visitados.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 7/75
Búsqueda no informada 7
Búsqueda en profundidad
● Los nodos se visitan y se expanden buscando los de mayor profundidad y retrocediendo cuando no se encuentran nodos
sucesores.● La estructura para los nodos abiertos es una pila (LIFO).
● Para garantizar que el algoritmo acaba debe imponerse unlímite en la profundidad de exploración.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 8/75
Búsqueda no informada 8
Búsqueda en profundidad
● No es completa: el algoritmo encuentra una solución si seimpone un límite de profundidad y existe una solución dentro dedicho límite.
●
La complejidad temporal es exponencial.● La complejidad espacial es lineal, si no se controlan los nodos
repetidos, y exponencial en el peor caso ya que solo se guardael camino hasta el nodo solución.
●
No se garantiza que la solución sea óptima.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 9/75
Búsqueda no informada 9
Búsqueda de coste uniforme
● Guía la búsqueda por el coste de los operandos visitados.
●
Expande primero el nodo de menor coste.● Es completa al ser los costes números enteros positivos.
● Es óptima al expandir los nodos de estados por valorescrecientes del coste. El primer nodo meta será el de menor coste.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 10/75
Búsqueda no informada 10
Ejercicio 1
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas:
a) Los algoritmos de búsqueda no informada requierende información heurística para que sean óptimos.
b) La búsqueda en amplitud es óptima y completasiempre y cuando el coste de los operadores seaconstante.
c) La búsqueda en profundidad es óptima y completasiempre que el coste de los operadores seaconstante.
d) La complejidad en espacio de la búsqueda enamplitud es mayor que en el caso de la búsqueda enprofundidad.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 11/75
Búsqueda no informada 11
Ejercicio 1
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas:
a) Los algoritmos de búsqueda no informada requierende información heurística para que sean óptimos.
b) La búsqueda en amplitud es óptima y completasiempre y cuando el coste de los operadores seaconstante.
c) La búsqueda en profundidad es óptima y completasiempre que el coste de los operadores seaconstante.
d) La complejidad en espacio de la búsqueda enamplitud es mayor que en el caso de la búsqueda enprofundidad.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 12/75
Búsqueda no informada 12
Ejercicio 2
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas si el coste delos operadores puede ser cualquier número entero positivo:
a) Si existe una solución, la búsqueda en amplitud la
encuentra.b) Si la búsqueda en amplitud encuentra una solución,
ésta debe ser igual a la que encontraría la búsquedade coste uniforme.
c) Si la búsqueda de coste uniforme encuentra unasolución, esta debe ser óptima.
d) La lista abierta en el algoritmo de búsqueda enamplitud funciona como una estructura LIFO.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 13/75
Búsqueda no informada 13
Ejercicio 2
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas si el coste delos operadores puede ser cualquier número entero positivo:
a) Si existe una solución, la búsqueda en amplitud la
encuentra.b) Si la búsqueda en amplitud encuentra una solución,
ésta debe ser igual a la que encontraría la búsquedade coste uniforme.
c) Si la búsqueda de coste uniforme encuentra unasolución, esta debe ser óptima.
d) La lista abierta en el algoritmo de búsqueda enamplitud funciona como una estructura LIFO.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 14/75
Búsqueda no informada 14
Ejercicio 3
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas:
a) La complejidad en tiempo del algoritmo de búsquedaen amplitud es directamente proporcional a la longitudde la lista abierta.
b) La complejidad del algoritmo de búsqueda enamplitud es exponencial en el peor caso, mientrasque es logarítmica en el mejor de ellos.
c) La complejidad en tiempo y en espacio del algoritmo
de búsqueda en amplitud es exponencial en amboscasos.
d) Los algoritmos de búsqueda en profundidad paraoperadores de coste distinto a uno pero constanteson óptimos.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 15/75
Búsqueda no informada 15
Ejercicio 3
Cuál o cuáles de las siguientes afirmaciones acerca de losalgoritmo de búsqueda no informada son ciertas:
a) La complejidad en tiempo del algoritmo de búsquedaen amplitud es directamente proporcional a la longitudde la lista abierta.
b) La complejidad del algoritmo de búsqueda enamplitud es exponencial en el peor caso, mientrasque es logarítmica en el mejor de ellos.
c) La complejidad en tiempo y en espacio del algoritmo
de búsqueda en amplitud es exponencial en amboscasos.
d) Los algoritmos de búsqueda en profundidad paraoperadores de coste distinto a uno pero constanteson óptimos.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 16/75
Búsqueda no informada 16
Ejercicio 4
En el algoritmo de búsqueda de coste uniforme:
a) La búsqueda está guiada por el coste de losoperadores.
b) La lista abierta siempre está ordenada de mayor amenor coste.
c) Es completo y óptimo.
d) En el peor caso su complejidad es exponencial.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 17/75
Búsqueda no informada 17
Ejercicio 4
En el algoritmo de búsqueda de coste uniforme:
a) La búsqueda está guiada por el coste de losoperadores.
b) La lista abierta siempre está ordenada de mayor amenor coste.
c) Es completo y óptimo.
d) En el peor caso su complejidad es exponencial.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 18/75
Búsqueda no informada 18
Problema 1
El grafo que se muestra a continuación determina un problemade búsqueda. Cada nodo representa un estado; los arcosmodelan la aplicación de los operadores. Si A es estado inicialy K y E son los estados meta:
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 19/75
Búsqueda no informada 19
Problema 1
a) Desarrolla el árbol de búsqueda en amplitud. Indica el ordenen que se expanden los nodos. ¿Cuál de los nodos meta seexpande primero?
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 20/75
Búsqueda no informada 20
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 21/75
Búsqueda no informada 21
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 22/75
Búsqueda no informada 22
Problema 1
Primero se expande el nodo meta E.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 23/75
Búsqueda no informada 23
Problema 1
b) Instancia el algoritmo de búsqueda general para que realiceuna búsqueda en amplitud. Escribe el estado de la lista abierta
en cada paso del algoritmo.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 24/75
Búsqueda no informada 24
Problema 1
Algoritmo Busqueda General
Est_abiertos insertar(Estado inicial) Estados abiertos implementado como FIFO
Actual=Est_abiertos.primero()
mientras no es_final(Actual) y no Est_abiertos.vacia() hacer
Est_abiertos.borrar_primero()Est_cerrados.insertar(Actual)
Hijos=generar_sucesores(Actual)
Hijos=tratar_repetidos(Hijos.Est_cerrados, Est_abiertos)
Actual=Est_abiertos.primero()fmientras
fAlgoritmo
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 25/75
Búsqueda no informada 25
Problema 1
Antes de entrar en el bucle la lista de estados abiertos contieneal estado inicial, en esta caso A.
Est_abiertos: D, F, G
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 26/75
Búsqueda no informada 26
Problema 1
Est_abiertos: F, G, C, H
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 27/75
Búsqueda no informada 27
Problema 1
Est_abiertos: G,C, H, E
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 28/75
Búsqueda no informada 28
Problema 1
Est_abiertos: C, H, E
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 29/75
Búsqueda no informada 29
Problema 1
Est_abiertos: H, E, K
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 30/75
Búsqueda no informada 30
Problema 1
Est_abiertos: E, K, B
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 31/75
Búsqueda no informada 31
Problema 1
c) La búsqueda en profundidad se diferencia de la búsqueda enamplitud en que al expandir un nodo, los nodos hijo se insertanal inicio de la lista abierta. Resuelva el problema usando estealgoritmo.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 32/75
Búsqueda no informada 32
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 33/75
Búsqueda no informada 33
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 34/75
Búsqueda no informada 34
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 35/75
Búsqueda no informada 35
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 36/75
Búsqueda no informada 36
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 37/75
Búsqueda no informada 37
Problema 1
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 38/75
Búsqueda no informada 38
Problema 1
d) ¿Qué ventaja presenta un algoritmo de búsqueda enprofundidad con respecto a un algoritmo de búsqueda enamplitud?
La complejidad en espacio es lineal.
e) ¿Qué desventajas existen?
No es completo, ni óptimo.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 39/75
Búsqueda no informada 39
Problema 2
Aplica la búsqueda de coste uniforme para encontrar la rutamás corta de Pitesti (P) a Fagaras (F). Desarrolla el árbol de
búsqueda generado por el algoritmo, asumiendo que se evitanlos ciclos simples. Indica el valor g de cada nodo así como elorden en que se expanden.
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 40/75
Búsqueda no informada 40
Problema 2
P bl 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 41/75
Búsqueda no informada 41
Problema 2
P bl 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 42/75
Búsqueda no informada 42
Problema 2
P bl 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 43/75
Búsqueda no informada 43
Problema 2
P bl 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 44/75
Búsqueda no informada 44
Problema 2
P bl 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 45/75
Búsqueda no informada 45
Problema 2
Problema 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 46/75
Búsqueda no informada 46
Problema 2
Problema 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 47/75
Búsqueda no informada 47
Problema 2
Problema 2
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 48/75
Búsqueda no informada 48
Problema 2
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 49/75
Búsqueda no informada 49
Problema extra
Resolución ejercicio del laberinto planteado en el tema“Busqueda heurística” con los siguientes métodos:
– A*
– Profundidad
– Greedy
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 50/75
Búsqueda no informada 50
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 51/75
Búsqueda no informada 51
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 52/75
Búsqueda no informada 52
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 53/75
Búsqueda no informada 53
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 54/75
Búsqueda no informada 54
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 55/75
Búsqueda no informada 55
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 56/75
Búsqueda no informada 56
Problema extra
●
A*
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 57/75
Búsqueda no informada 57
Problema extra
●
Profundidad:
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 58/75
Búsqueda no informada 58
Problema extra
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 59/75
Búsqueda no informada 59
Problema extra
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 60/75
Búsqueda no informada 60
Problema extra
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 61/75
Búsqueda no informada 61
ob e a e t a
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 62/75
Búsqueda no informada 62
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 63/75
Búsqueda no informada 63
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 64/75
Búsqueda no informada 64
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 65/75
Búsqueda no informada 65
●
Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 66/75
Búsqueda no informada 66
● Profundidad
Problema extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 67/75
Búsqueda no informada 67
● Profundidad
Problema extraP f did d
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 68/75
Búsqueda no informada 68
● Profundidad
Problema extraP f did d
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 69/75
Búsqueda no informada 69
● Profundidad
Problema extraP f did d
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 70/75
Búsqueda no informada 70
● Profundidad
Problema Extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 71/75
Búsqueda no informada 71
●
Greedy
Problema Extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 72/75
Búsqueda no informada 72
●
Greedy
Problema Extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 73/75
Búsqueda no informada 73
●
Greedy
Problema Extra
5/13/2018 Presentaci n-BNI-IA - slidepdf.com
http://slidepdf.com/reader/full/presentacion-bni-ia 74/75
Búsqueda no informada 74
●
Greedy
Problema Extra