• Author / Uploaded
• Angel Garcia

• Categories
• Áreas de informática
• Algoritmos
• Conceptos matemáticos
• Informática teórica
• Algoritmos y Estructuras de Datos

Citation preview

UNIVERSIDAD FERMÍN TORO VICE RECTORADO ACADÉMICO FACULTAD DE INGENIERÍA CABUDARE – EDO LARA

EJERCICIOS RESUELTOS

Asignatura: Inteligencia Artificial Tutor: Edecio Freitez Autores: Angel García C.I.: 20.501.660 Sección: SAIA-A

EJERCICIO 1. Dado el árbol de la figura donde B y L son los dos únicos nodos meta y A es el nodo inicial, indicar el orden en que se visitan los nodos, distinguiendo los que sólo se han generado de aquellos que se han elegido en el proceso de búsqueda de la solución, para cada uno de los procedimientos siguientes: a) Búsqueda en amplitud b) Búsqueda en profundidad c) Búsqueda en retroceso Se supone que en cada nivel del árbol los nodos se recorren de izquierda a derecha y que el límite de profundidad es 5. SOLUCIÓN: a) Búsqueda en amplitud Se elige como contenido de la lista ABIERTA para resolver un algoritmo y usarlo como cola, es decir “primero en llegar, primero en salir condición FIFO”. Los pasos del algoritmo: Punto 1) ABIERTA: A 2.1) m = A 2.2) ABIERTA: D, F, G 2.1) m = D 2.2) ABIERTA: F, G, H, J 2.1) m = F 2.2) ABIERTA: G, H, J, C, E 2.1) m = G 2.2) ABIERTA: H, J, C, E 2.1) m = H -> “B” seguido al nodo meta, paso 2.2. (2) pone fin a la ejecución del algoritmo. Orden visitada de los nodos es: A, D, F, G, H, J, C, E, B. Los elementos comienzan de la lista ABIERTA y sus sucesores se añaden al final. De esta forma siempre se expanden primero los nodos más antiguos.

b) Búsqueda en profundidad Ahora se dice que: ABIERTA va a actuar como una pila es decir “ultimo en entrar en salir por la condición LIFO”. Se extra el prime nodo de ABIERTA y se añaden al principio de la misma todos sus sucesores, siendo el orden de la colocación irrelevante, este algoritmo es considerado no informado. Pasos del algoritmo: Punto 1) ABIERTA: A 2.(2) m = A 2.(4) ABIERTA: D, F, G 2.(2) m = D 2.(4) ABIERTA: H, J, F, G 2.(2) m = H 2.(4) ABIERTA: B, J, F, G Siendo B un nodo de inicio Finaliza su ejecución en el punto 2. (4.1) El orden para llegar al estado meta ha sido: A, D, H, B El proceso de ejecución se podría haber introducido en otro orden los nodos en la pila y como consecuencia de ello el camino no habría resultado tan directo c) Búsqueda en retroceso En este caso no se generan todos los sucesores de un nodo en cada paso del algoritmo, sino solo uno cualquiera de ellos. La eficiencia del algoritmo depende del orden en que se expanden los nodos (al ser no informado no se aplica ningún criterio para elegirlos). Pasos en seguir es: Punto 1) ABIERTA: A 2.(2) m = A 2.(4) m´ m D; ABIERTA: D, A 2.(2) m = D 2.(4) m´ = H; ABIERTA: H, D, A 2.(2) m = H 2.(4.1) Fin, por ser B un nodo meta

EJERCICIO 2: 1) Dado el siguiente mapa de carreteras en el que los caminos entre cada dos ciudades están etiquetados con sus distancias en kilómetros:

a. Describa el grafo correspondiente a la búsqueda del camino más corto entre Palencia y Barcelona. Aplica el algoritmo A* para encontrar ese camino suponiendo una estimación del coste del camino que resta nula para todos los nodos. b. Ver cómo cambia si tenemos en cuenta el siguiente cuadro de distancias aéreas estimadas desde cada ciudad a Barcelona 2)

SOLUCIÓN: a) El algoritmo apropiado para encontrar el camino más corto entre Palencia y Barcelona es el A*, siempre que la función heurística que estima la distancia a la meta desde cada nodo nunca supere la distancia real existente. En estas condiciones se garantiza que el algoritmo A* encontrará la solución óptima al problema. Una forma de asegurar la condición mencionada es suponer que la función de estimación vale 0 (este procedimiento se denomina de coste uniforme y es una variación de la búsqueda en amplitud, pero en lugar de obtener soluciones de menor longitud genera soluciones de menor coste). El grafo de búsqueda con líneas a trazos representado caminos alternativos que no son los mejores en cuanto a coste, parece más adelante. Los números al lado de cada nodo indican el orden de expansión de los mismo. En ningún momento hay redirigir ningún enlace, ya que en todos los casos los nuevos caminos que se abren hasta la raíz son de mayor coste que los anteriores

1.b) El camino que recorra el menor número de ciudades se puede encontrar aplicando el algoritmo de búsqueda en amplitud. 2) Se puede recurrir al algoritmo A* de manera que, aprovechando la nueva información sobre la distancia aérea estimada a la meta, se obtendrá el siguiente grafo de búsqueda: