Transcript
Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial
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 afi a firmaciones 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 coste uniforme encuentra una solución, esta debe ser óptima. d. La lista abierta en el algoritmo algor itmo de búsqueda en amplitud funciona comouna estructura LIFO.
3.
Cuál o cuáles de las siguientes afirmaciones acerc a 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.
1
Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial
4.
En el algoritmo de búsqueda de coste uniforme: a. b. c. d.
5.
a.
La búsquedaestá guiada por el coste de los operadores. La lista abierta siempre está or denada de mayor a menor coste. Es completo y óptimo. En el peor caso su complejidad es exponencial.
El grafo que se muestra a continuación determina un problema de búsqueda. Cada nodo representa un estado; los arcos modelan la aplicación de los operadores. Si A es el estado inicial y K y E son los estados meta:
Desarrolla el árbol de búsqueda en amplitud. Indica el orden en que se expandenlos nodos. ¿Cuál de los nodos meta se expande primero? b. Instancia el algoritmo de búsqueda general para que realice una búsqueda en amplitud. Escribe el estado de la lista abierta en cada paso del algoritmo. c. ¿Qué ventajas presenta un algoritmo de búsqueda en profundidad con respectoa un algoritmo de búsqueda en amplitud? d. ¿Qué desventajas existen?
2
Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial SOLUCION 1.
La afirmación que es correcta para este punto es: b. La complejidad en espacio de la búsqueda en amplitud es mayor que en el caso de la búsqueda en profundidad. ρ
Ya que para la búsqueda en amplitud la complejidad será del orden O(n ), la complejidad espacial también es de este mismo orden, lo que hace difícil la utilización en problemas reales. 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, la complejidad para el mismo camino ρ será este valor más el factor de ramificación (r), es decir O(ρ+r). 2. Las afirmaciones correctas son : a.
Si existe una solución, la búsqueda en amplitud la encuentra.
Porque la búsqueda en amplitud es un procedimiento completo ya que garantiza encontrar una solución si esta existe. c.
Si la búsqueda de coste uniforme encuentra una solución, esta debe ser óptima. 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.
3. 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. Ya que la búsqueda en amplitud tiene complejidad exponencial tanto temporal tanto temporal como espacial. La complejidad temporal depende del factor de ramificación y de la profundidad de la solución.
d. Las afirmaciones correctas son: a.
La búsqueda está guiada por el coste de los operadores. Porque cada cambio de estado tiene asociado un costo.
b. Es completo y óptimo.
3
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. c.
En el peor caso su complejidad es exponencial. Porque:
La Complejidad temporal y espacial son Exponenciales respecto al factor d+1 de ramificación y la profundidad de la solución O(b ).
e. a.
TIEMPO T0 T1 T2 T3 T4 T5 T6 T7 T8 T9
LISTA ABIERTA A D,F,G F,G,H,C G,H,C,E H,C,E C,E,B E,B,K B,K,Z,W K,Z,W
LISTA CERRADA φ A A,D A,D,F A,B,F,G A,B,F,G,H A,B,F,G,H,C A,B,F,G,H,C,E A,B,F,G,H,C,E,B A,B,F,G,H,C,E,B,K
LISTA HIJOS φ D,F,G H,C E Φ B K Z,W Φ φ
El nodo que se expande primero es e l E b. Algoritmo búsqueda en anchura 1 método BFS (Grafo, 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.
Ventajas
Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha
4
Fundación Universitaria de Popayán Programa de Ingeniería de Sistemas Inteligencia Artificial encontrado una solución posible con determinada valoració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. Además, el requerimiento de memoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual. d. 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. • 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. • se pueden encontrar soluciones que están más alejadas de la raíz que otras.
5
