Download Ejemplo 1 - Grupo de Inteligencia Artificial

Fundamentos de Inteligencia Artificial
Junio 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
[2 puntos: respuesta acertada = +0.2, respuesta incorrecta = –0.2]
Complete las siguientes frases y conteste a cada una con verdadero o falso:
3.1. Contemple el problema de búsqueda (grafo de
transiciones) de la figura 1. Sea b el factor de
ramificación efectivo del árbol de búsqueda,
¿Cuáles de las siguientes afirmaciones acerca de
complejidad de la búsqueda en amplitud son
correctas y cuales son falsas?
F
(a)
La complejidad en tiempo en el peor caso es
O(b*(|x|+|y|))
V
(b)
La complejidad en espacio en el peor caso es
O(b|x|+|y|)
. . .
Y
2
1
0 ...
...
−1
−2
. . .
−2
−1
0
1
2
X
Figura 1. Red 2D regular e infinito.
• Estado inicial (0,0).
• Estado meta (x,y); x,y∈Z.
3.2. Considerando la figura 1 y el algoritmo A*. Sea
• Movimiento entre estados directamente
conectados a coste 1
(u,v) la representación de un estado en el problema.
¿Cuales de las siguientes afirmaciones son verdaderas/falsas?
V
(a)
la función h*1 ((u,v)) = max(| u – x | , | v - y|) es optimista
V
(b)
la función h*2 ((u,v)) = min(| u – x | , | v - y|) es optimista
F
(c)
la función h*2 es más informado que la función h*1
(d)
La búsqueda A* ordena los nodos hojas según los valores de f(n) = g(n) +
F
h(n), donde g(n) es el coste real para llegar al nodo n y h(n) es el coste real
para llegar del nodo n hasta el nodo meta.
3.3. En la búsqueda por sub-ojetivos se consigue siempre una mejora de la
complejidad respecto a la búsqueda por amplitud.
F
Pág. 1 / 6
Fundamentos de Inteligencia Artificial
Junio 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
3.4. Respecto a los algoritmos de búsqueda no informados:
F
(a) Un algoritmo es completo si encuentra todos los posibles estados meta.
V
(b) Un algoritmo de búsqueda no informado puede ser óptimo.
F
(c) Suponiendo que se controlan (evitan) ciclos en la misma rama del árbol de
búsqueda, entonces la búsqueda por profundidad es completa.
Ejercicio 2:
[ 30 puntos]
Considera el siguiente subárbol de un problema de búsqueda. Los números asignados a
cada arco representan los costes de las operaciones/acciones correspondientes. Los
números en los nodos representan una estimación del coste del camino más corto de
este nodo a un nodo meta. Los nodos meta están marcados con doble circulo.
5
9
4
5
2
2
2
7
7
20
5
0
9
0
1
6
8
0
3
5
1
0
3
2
5
5
20
2
5
6
0
0
8
5
20
0
0
a.) Construye el árbol que expandiría el algoritmo A* aplicado a este problema,
indica el orden en el que se expandirían los nodos, los valores de la función f* y
el nodo meta que el algoritmo encontraría.
SOLUCION:
Pág. 2 / 6
Fundamentos de Inteligencia Artificial
Junio 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
1
5
9
5
2
2
f*=11+7=18
f*=0+5=5
2
4
5
f*=9+2=11
2
3
1 f*=9+1=10
6 f*=11+6=17
7
3
5
4
f*=4+5=9
2 f*=7+2=9
3
2
6
6
f*=17+0=17
8 f*=10+8=18
5 f*=11+5=16
5
0
7
0 f*=16+0=16
b.) Dado el mismo árbol, pero con los costes de cada operador/acción igual a 1
(los números en los arcos) y sin la información de la estimación del coste del
camino más corto de un nodo a un nodo meta (números en los nodos).
Construye los árboles que expandiría el algoritmo de profundización iterativa
para encontrar los nodos meta. Indica en cada árbol el orden en el que se
expandirían los nodos.
SOLUCION:
Árbol 2:
1
Árbol 1:
1
3
2
Árbol 3:
1
5
2
3
4
7
6
Pág. 3 / 6
Fundamentos de Inteligencia Artificial
Junio 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Árbol 4:
1
2
3
4
5
En este ejercicio los nodos en el límite de profundidad se han considerados
“nodos expandidos”. La razón es que, aunque de forma estricta estos nodos no se
expanden, sí se “tratan”, comprobando si son nodos méta.
Ejercicio 3:
[ 25 puntos]
Considera el siguiente juego de dos jugadores (max y min). Hay un montón de 6 fichas,
tres de valor 1 y tres de valor 3 y cuyo valor está oculto para los jugadores. El juego
tiene el siguiente desarrollo.
Primero, ambos jugadores ponen 1 euro en el bote para jugar. Después, cada jugador
obtiene 1 ficha del montón. A continuación el jugador max puede, si quiere, coger otra
ficha. A continuación, los dos jugadores enseñan sus fichas. Si la suma de los valores de
las fichas de ambos jugadores es par gana max el bote. Por otro lado, si la suma es
impar, gana min el bote.
Supón que un agente juega el papel de max y ambos jugadores han obtenido su primer
ficha. A max le ha tocado un 3 (y lo sabe) y, obviamente no sabe el valor de la ficha de
min. Realice el árbol completo del juego y aplique los algoritmos vistos en clase para
decidir si en esta situación a max le conviene coger una segunda ficha o no (indique
toda la información necesaria en el árbol para poder seguir el desarrollo del algoritmo).
¿Que decisión debería tomar max?
Pág. 4 / 6
Fundamentos de Inteligencia Artificial
Junio 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
SOLUCION:
<(({3},1),3/5),
(({3},3),2/5)>
U=1
no coger segunda
ficha
coger segunda
ficha
<(({3},1),3/5), U=3/5*-1 + 2/5*-1
(({3},3),2/5)>
=-1
coger 3:
p=2/5
coger 1:
p=3/5
<(({3},1),3/5),
(({3},3),2/5)>
U=3/5*1 + 2/5*1
=1
<(({3,1},1),1/2),
(({3,1},3),1/2)>
<(({3,3},1),3/4),
(({3,3},3),1/4)>
U=1/2*-1 + 1/2*-1
=-1
U=3/4*-1 + 1/4*-1
=-1
En este caso, como se puede observar en el árbol de juego en el que se han
calculado las utilidades de los nodos hoja, la mejor jugada para max es no coger
una segunda ficha.
Ejercicio 4.
(Puntuación total: 25 puntos)
Considera el siguiente árbol de un juego de dos personas.
Apliqua el algoritmo minimax con poda alfa-beta, propaga los valores de evaluación
hasta el nodo raíz, marca la mejor jugada para max (cuadrado), y marca todos los
subárboles que se podan.
20
0
30
-10
60
0
-20
60
Pág. 5 / 6
Fundamentos de Inteligencia Artificial
Junio 2014
APELLIDOS:
NOMBRE:
Duración: 2 h
No se permiten libros ni apuntes
Solución
a=-∝/20
b=∝
20
a=-∝
b=∝/20
20
20
a=-∝/20
b=∝20
a=-∝
b=∝/20
20
a=-∝/20
b=20
20
0
30
20
a=20
b=∝
0
a=20
b=∝/0
a=20
b=∝/0
a=-∝ 30
0
b=20
20
20
20
a=20
b=∝/20
0
-10
60
0
-20
60
Pág. 6 / 6