Ejercicios Prolog

UNIVERSIDAD CÉSAR VALLEJO – PIURA FACULTAD DE INGENIERÍA ESCUELA: INGENIERÍA DE SISTEMAS CURSO: INTELIGENCIA ARTIFICIAL

EJERCICIOS SOBRE MÉTODOS DE BÚSQUEDA 1. Dado el siguiente grafo, donde A es el nodo inicial y G el nodo meta, generar el árbol de búsqueda mediante los siguientes métodos: a) Búsqueda en amplitud b) Búsqueda en profundidad
B D H

A

E

I

C

F

G

2. Dado elsiguiente grafo, donde A es el nodo inicial y H el nodo meta, generar el árbol de búsqueda mediante los siguientes métodos: a) Búsqueda en amplitud b) Búsqueda en profundidad
A

B

C

D H F

E

G

3. 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 deaquellos 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 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.

A

D

F

G

H

J

C

E

B

K

Z

W

L

4. A partir del siguiente árbol, donde losnodos B y E son los dos únicos nodos solución y A es el nodo raíz, indique la cantidad y secuencia de los nodos visitados en el proceso de búsqueda de la solución para el procedimiento de búsqueda Primero en Amplitud.
A

D

F

G

H

J

C

E

P

Q

K

Z

W

B

Si la mejor solución es aquella a la que se accede en la menor cantidad de pasos, ¿cuál de los nodos es elegidopor el algoritmo como solución al problema? ¿Sería el mismo nodo que el algoritmo Primero en Profundidad identificaría como solución? Nota: Suponemos que en cada nivel del árbol los nodos se recorren de izquierda a derecha y que el límite de profundidad es 5. 5. Resolver el problema del 8-puzzle descrito en la figura mediante el algoritmo A* suponiendo un coste uniforme de 1 de aplicación de cadauno de los operadores disponibles y considerando la heurística siguiente: Número de fichas mal colocadas 2 1 7 8 6 3 4 5

6. Resolver el problema del 8-puzzle descrito en la figura mediante el algoritmo A* suponiendo un coste uniforme de 1 de aplicación de cada uno de los operadores disponibles y considerando la heurística siguiente: Número de fichas mal colocadas 1 3 4 8 6 2 7 5

7. Aplicar elalgoritmo A* para hallar el camino que une las ciudades 1 y 8. Las distancias por carretera entre las distintas ciudades vienen especificadas por la siguiente tabla: 1 1 2 3 4 5 6 7 8 200 150 350 450 2 200 3 150 4 350 5 450 400 300 6 7 8

225 250 450

400 225

300 250 450

125 125

Además, se dispone de la distancia aérea en línea recta que existe entre todas las ciudades con la ciudadde destino: 1 800 2 650 3 500 4 650 5 325 6 375 7 125

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

Santander 111 203 Palencia 368 Cáceres 299 Madrid 350 239 322

Bilbao Barcelona 299

323

Zaragoza

352

Valencia

a) Describa el grafo correspondiente a la búsqueda del camino más cortoentre 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:
Bilbao Barcelona Cáceres Madrid Palencia Santander Valencia Zaragoza

502

850

550

580

605

303

2759. Aplicar el algoritmo A * al grafo de la figura. El nodo inicial es A y el nodo meta I. Cada arco lleva asociado su coste y en cada nodo aparece la estimación de la menor distancia

desde ese nodo a la meta. Dibujar en cada etapa del algoritmo el subgrafo parcial creado, el árbol parcial de costes mínimos desde la raíz al resto de nodos generados y la situación de las listas ABIERTA y...