Download 4.EjerciciosClase

Búsquedas informadas [10 minutos]
Aplicar el algoritmo A* al siguiente grafo. El nodo inicial es A y hay un solo
nodo objetivo, que en este caso es Z. A cada arco se le ha asociado un coste y
a cada nodo la estimación de la menor distancia de ese nodo al nodo objetivo
(hay que asumir que se trata de una heurística admisible). Se pide el orden en
que los nodos son expandidos y el orden de la solución. Justifica tu solución
dibujando en la siguiente página el árbol que se genera en la búsqueda
indicando: f’, g y h’, así como el nº de orden en que los nodos son visitados.
80 A
4
10
27 B
10
60 C
65 D
5
5
10
50 F
35
30
50 G
50 H
2
0 Z
15
70 E
3
30
Búsqueda en juegos [7 min.]
Considerar el árbol de juego mostrado abajo. Asumir que el nodo de arriba es
un nodo max. Las etiquetas de los arcos son los movimientos. Los números en
el nivel de abajo son los valores heurísticos de esas posiciones.
max
min
3
7
8
10
4
8
2
7
5
1. Completa el árbol de juego anterior utilizando una búsqueda mini-max.
2. ¿Qué movimiento debería hacer el jugador Max?: ____________
3. Indica las ramas podadas con una poda alfa-beta con una búsqueda de
izquierda a derecha. Indica también los valores que van tomando alfa y beta
en cada nodo.
max
min
3
7
8
10
4
8
2
7
5
4. Reordena las hojas de los nodos de forma que resultara en el máximo
número de nodos podados en una poda alfa-beta de izquierda a derecha
(indica también las ramas podadas). Reordena los hijos pero preserva las
relaciones padre-hijo.
max
min
Búsqueda en juegos [10 min.]
Dado el árbol de la figura, recorre el árbol de izquierda a derecha, siguiendo el
método de poda alfa-beta, indicando claramente (tachando con una x) los nodo
en que se produce poda. Encuadra /marca los nodos terminales que no ha sido
necesario recorrer. Señala el valor de la decisión más acertada para MAX.
MAX
4
6
7 6
8
9 5
1
6
7
8
6
8
4