Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial1 TALLER INTELIGENCIA ARTIFICIAL Selecciona la(s) respuesta(s) correcta(s) para las siguientes cuestiones: 1. Cuál o cuáles de las siguientes afirmaciones acerca de los algoritmos de búsqueda no informada son ciertas: a. Los algoritmos de búsqueda no informada requieren de información heurística para que sean óptimos. b. La búsqueda en amplitud es ´optima y completa siempre y cuando el costede los operadores sea constante. c. La búsqueda en profundidad es ´optima y completa siempre que el coste delos operadores sea constante. d. La complejidad en espacio de la búsqueda en amplitud es mayor que en el caso de la búsqueda en profundidad. 2. Cuál o cuáles de las siguientes afirmaciones acerca de los algoritmos de búsquedano informada son ciertas si el coste de los operadores puede ser cualquier númeroentero 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, ´esta debe ser igual ala que encontraría la búsqueda de coste uniforme. c. Si la búsqueda de coste uniforme encuentra una solución, esta debe ser óptima. d. La lista abierta en el algoritmo de búsqueda en amplitud funciona comouna estructura LIFO. 3. Cuál o cuáles de las siguientes afirmaciones acerca de los algoritmos de búsquedano informada son ciertas: a. La complejidad en tiempo del algoritmo de búsqueda en amplitud es directamente proporcional a la longitud de la lista abierta. b. La complejidad del algoritmo de búsqueda en amplitud es exponencial enel peor caso, mientras que 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 ambos casos. d. Los algoritmos de búsqueda en profundidad para operadores de coste distinto a uno pero constante son óptimos. Es completo y óptimo. Instancia el algoritmo de búsqueda general para que realice una búsqueda en amplitud. ¿Qué ventajas presenta un algoritmo de búsqueda en profundidad con respectoa un algoritmo de búsqueda en amplitud? d. 5. los arcos modelan la aplicación de los operadores. En el peor caso su complejidad es exponencial. Si A es el estado inicial y K y E son los estados meta: a. d. El grafo que se muestra a continuación determina un problema de búsqueda. Desarrolla el árbol de búsqueda en amplitud. Indica el orden en que se expandenlos nodos.Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial 2 4. c. Escribe el estado de la lista abierta en cada paso del algoritmo. ¿Qué desventajas existen? . En el algoritmo de búsqueda de coste uniforme: a. c. ¿Cuál de los nodos meta se expande primero? b. Cada nodo representa un estado. b. La búsquedaestá guiada por el coste de los operadores. La lista abierta siempre está ordenada de mayor a menor coste. Porque la búsqueda de costo uniforme garantiza encontrar la solución del costo menor siempre en cuando el costo nunca disminuya a lo largo del camino. Las afirmaciones correctas son : a. La complejidad temporal depende del factor de ramificación y de la profundidad de la solución. Es completo y óptimo. c. Ya que la búsqueda en amplitud tiene complejidad exponencial tanto temporal tanto temporal como espacial. Porque cada cambio de estado tiene asociado un costo. Ya que para la búsqueda en amplitud la complejidad será del orden O(nρ). La afirmación correcta es: c. La complejidad en tiempo y en espacio del algoritmo de búsqueda en amplitud es exponencial en ambos casos. d. La búsqueda está guiada por el coste de los operadores. 3 3. lo que hace difícil la utilización en problemas reales. Si existe una solución. la complejidad para el mismo camino ρ será este valor más el factor de ramificación (r). En la búsqueda en profundidad la complejidad espacial se reduce respecto a la búsqueda anterior ya que solo es necesario guardar constancia del camino construido hasta el momento. Las afirmaciones correctas son: a. Si la búsqueda de coste uniforme encuentra una solución. la búsqueda en amplitud la encuentra. b. .Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial SOLUCION 1. es decir O(ρ+r). La complejidad en espacio de la búsqueda en amplitud es mayor que en el caso de la búsqueda en profundidad. 2. la complejidad espacial también es de este mismo orden. Porque la búsqueda en amplitud es un procedimiento completo ya que garantiza encontrar una solución si esta existe. esta debe ser óptima. La afirmación que es correcta para este punto es: b. W LISTA CERRADA φ A A.Z.B.H. si se ha .G.E.B.B.F.F.B.H.G.D.E.K B.C.F.F. En el peor caso su complejidad es exponencial.B.F.C. c.H.E A.W K.F A.F.G.K LISTA HIJOS φ D. Algoritmo búsqueda en anchura 1 método BFS (Grafo.G H.G.Z.F.H.E H.C. Ventajas Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización.W Φ φ El nodo que se expande primero es el E b.C G. TIEMPO T0 T1 T2 T3 T4 T5 T6 T7 T8 T9 LISTA ABIERTA A D.C.H A.B.E. 4 e.Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial Es completa cuando existe una solución y optimo mientras el costo de ruta no disminuya siguiendo cualquier ruta.E C.B.C.C E Φ B K Z. Porque: La Complejidad temporal y espacial son Exponenciales respecto al factor de ramificación y la profundidad de la solución O(bd+1).B.G.K.B E.B A.F.C A. origen): 2 creamos una cola Q 3 agregamos origen a la cola Q 4 marcamos origen como visitado 5 mientras Q no este vacío: 6 sacamos un elemento de la cola Q llamado v 7 para cada vértice w adyacente a v en el Grafo: 8 si w no ha sido visitado: 9 marcamos como visitado w 10 insertamos w dentro de la cola Q c.G F.G A. Esto es. a.G.D A.H.H. ya que sólo hace falta guardar los datos de la rama actual. • si no se guarda constancia de los nodos que forman el camino recorrido se podría caer en ciclos y el proceso no acabaría. d. 5 . el requerimiento de memoria es limitado.Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial encontrado una solución posible con determinada valoración. aun si se garantiza que no cicle. • se pueden encontrar soluciones que están más alejadas de la raíz que otras. Además. Desventajas búsqueda en profundidad • solución no completa en espacios con ciclos puede haber bucles infinitos es necesaria una comprobación de estados repetidos • el algoritmo puede dedicarse a recorrer un camino demasiado largo que no conduzca a ninguna solución. no se admitirá expandir nodos con una valoración peor. y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas.