Download Ejemplo 2 - Grupo de Inteligencia Artificial

Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Ejercicio 1
Ejercicio 1:
Ejercicio 2
Ejercicio 3
Ejercicio 4
TOTAL
NOTA
[XX puntos: respuesta acertada = +2, respuesta incorrecta = –2]
Complete las siguientes frases y conteste a cada una con verdadero o falso:
1. ¿Cúales de las siguientes afirmaciones acerca de los algorítmos de búsqueda son
VERDADERAS y cúales son FALSAS?
a) La función de coste pertenece al conjunto de componentes que definen un
problema VERDADERO
b) La normalidad es una característica para evaluar un algoritmo de búsqueda
FALSO
c) La complejidad en espacio del algoritmo de búsqueda en profundidad es
inferior a la complejidad en espacio del algoritmo de búsqueda en amplitud
VERDADERO
d) El árbol expanido por el algoritmo A*, si el coste de cada acción es 1 y la
heurística h*(n) es 0 para todo nodo n, es el mismo árbol que expandiría el
algoritmo de búsqueda en amplitud VERDADERO
e) El algoritmo A*, utilizando la heurística h*(n)=0 para todo nodo n
encuentra la solución óptima VERDADERO
2. ¿Cuales de las siguientes afirmaciones son VERDADERAS y cuales son FALSAS?
a) El algoritmo Minimax recomienda siempre la jugada que tiene mayores
probabilidades de llevar a ganar el juego. FALSO
b) El algoritmo Minimax calcula la mejor jugada para un jugador, suponiendo
que el jugador contrario es un jugador de nivel medio. FALSO
c) En algunos casos, usando el algoritmo minimax con poda α-β se expande
el mismo número de nodos que en el minimax simple. VERDADERO
d) Un estado de creencia de un agente es el estado del juego que el agente
cree que es el más probable en una determinada situación. FALSO
e) En un juego en el que dos jugadores tiran un dado cada uno y gana aquel
jugador que tiene el número más alto, el algoritmo expectminimax puede
determinar cuál es la mejor acción de un jugador. FALSO
Pág. 1 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
3. Sea H = { h1* , …, hk*} un conjunto de funciones heurísticas optimistas. ¿Cuál(es)
de las siguientes afirmaciones son verdaderas y cuáles falsas?
*
V (a) h (n) = max
{h*j (n)} es una función heurística optimista
h ∈H
*
j
F
(b) El algoritmo A* con función heurística hi*∈H es óptimo, si y sólo si hi* es
la función más informada de todas las funciones de H
(c) Dada cualquier instanciación de un problema, el algoritmo A* siempre
expandirá un numero menor o igual de nodos si utiliza la función heurística
V
h*(n) = min
{h*j (n)} en comparación con utilizar cualquiera de las
*
h j ∈H
funciones heurísticas individuales hi*∈H .
F
(d) Suponiendo una función heurística optimista, el algoritmo A* siempre
expande menos nodos que el algoritmo de búsqueda en amplitud.
Ejercicio 2:
[XX puntos]
Dado el siguiente espacio de estados, donde el coste de cada acción es 1.
1. Considera el problema de búsqueda donde el estado inicial es A y el estado final
es F.
a. Aplica el algoritmo de búsqueda de profundización iterativa, sin
eliminar los estados repetidos y generando los nodos en orden
alfabéticos. Muestra el árbol generado, indicando el orden de expansión
de los nodos
b. ¿La solución encontrada es óptima?
Pág. 2 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
c. ¿Cuántos nodos se han generado?
2. Considera la heurística h*(s)= distancia alfabética entre s y el estado F (por
ejemplo, h*(D)=2, ya que D está “lejos” dos letras de F).
a. ¿Es h* optimista?
b. Aplica el algoritmo de búsqueda A*, eliminando los estados repetidos.
Muestra el árbol generado, indicando el orden de expansión de los nodos,
el valor de f* de cada nodo, la solución encontrada y si ésta es óptima o
no.
Pág. 3 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
SOLUCIÓN
Límite 0
A
Límite 1
1º
A
2º
3º
B
D
Límite 2
1º
A
2º
4º
B
D
3º
5º
C
E
Pág. 4 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Límite 3
1º
A
2º
B
D
3º
C
4º
5º
B
F
La solución es óptima, los nodos que se han generados son 1 + 3 + 5 + 6 = 15
La heurística h* no es optimista ya que, por ejemplo, h*(C)=3, mientras que h(C)=1
f*=0+5=5
1º
A
f*=1+4=5
f*=1+2=3
2º
B
D
3º
f*=2+1=3
E
f*=3+3=6
f*=3+0=3
4º
C
F
Aunque h* no sea optimista, la solución encontrada es la solución óptima.
Pág. 5 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Ejercicio 3:
[XX puntos]
Considera el siguiente problema. Un agente tiene que realizar una carrera desde Madrid
a Bilbao (ver mapa de carreteras con ciudades y kilómetros). La peculiaridad de la
carrera consiste en que el agente no conoce el mapa. Una vez que el agente llega a una
ciudad, se le dice el nombre de esta ciudad, las carreteras que salen (N,S,E,O) y la
longitud de la carretera que acaba de recorrer. Además, el agente sabe que puede
recorrer todas las carreteras en las dos direcciones. Eso implica que si sabe que por una
carretera se llega de Madrid a Burgos, también sabe que por esta carretera puede llegar
de Burgos a Madrid).
BILBAO
A CORUÑA
E
S
E
O
160
500
600
E
O
BURGOS
O
BARCELONA
S
700
S
200
N
350
MADRID
400
N
O
E
N
E
VALENCIA
400
BADAJOZ
S
N
E
200
O
MURCIA
200
N
SEVILLA
500
O
E
1. Aplique el algoritmo de búsqueda A* con aprendizaje en tiempo real a este
problema. Si no hay ningún criterio mejor, el agente prefiere tomar carreteras
según el siguiente orden: N, O, E, S. Especifica
a. El recorrido del agente
b. El grafo del problema que está construyendo
c. Los valores de la función heurística aprendida y la evolución de estos
valores.
Pág. 6 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
SOLUCIÓN
MADRID
BURGOS
A CORUÑA
BADAJOZ
BADAJOZ
SEVILLA
MURCIA
MADRID
SEVILLA
MURCIA
VALENCIA
BARCELONA
BILBAO
BILBAO
A CORUÑA
E
S
500
600
500
E
O
BURGOS
O
0
BARCELONA
S
700
MADRID
O
N
400
E
400
200
350
0
E
N
VALENCIA
400
BADAJOZ
0
S
200
N
600
S
N
200
E
200
350
MURCIA
N
SEVILLA
500
E
O
0
200
200
500
Pág. 7 / 8
Fundamentos de Inteligencia Artificial
Mayo 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Ejercicio 4:
[XX puntos]
Contemple el siguiente árbol de juego, en cuyas hojas se indica el valor correspondiente
de la función de evaluación. Max (nodos con círculos) quiere saber cuál es la mejor
acción para él. Los nodos de min corresponden a los nodos con cuadrados.
a
c
b
e
f
l
m
7
6
n
5
g
o
5
p
6
d
h
q
3
r
7
j
i
s
–2
t
6
u
2
v
5
k
w
2
x
29
y
2
1. Suponiendo que siempre se expanden los sucesores de un nodo de izquierda
a derecha,
a. Indique el orden en que se expandirían los nodos aplicando el
algoritmo Minimax con poda alfa-beta. Obviamente, los nodos
podados no se expanden. ¿Cuál es la mejor jugada para Max?
b. Indique la evolución de los valores alfa y beta en todos los nodos que
no son nodos hoja.
Pág. 8 / 8