Aprenda a sobresalir

Ingenier´ en ıa Inform´tica a
Inteligencia Artificial
Noviembre 2007 ´ Departamento de Informatica Universidad Carlos III de Madrid

Hoja de Ejercicios 4: B´ squeda heur´ u ıstica y de dos agentes
Comentarios generales sobre los ejercicios
• Asumiendo que se conocen los contenidos te´ricos, el tiempo estimado o para realizar los ejercicios es de 2 horas • Describir las soluciones a losejercicios de una manera lo m´s formal a posible

Ejercicio 1
Aplicar el algoritmo de b´squeda A* sobre la representaci´n del problema de los misioneros y los can´ u o ıbales extra´ de la anterior hoja de problemas. Especifica cu´ndo un nodo del ´rbol de b´squeda es expandido y cu´ndo ıda a a u a es s´lo generado. A modo de resumen, se describen los siguientes elementos: o 1. Un estado es una terna(Mi , Ci , B, Mf , Cf ) en la que: B ∈ [i, f ] indica la posici´n de la barca, por lo que toma el valor i si est´ en el extremo inicial, o f si o a est´ en el final a Mi , Ci , Mf , Cf ∈ [0, . . . , 3] indican el n´mero de misioneros y can´ u ıbales que quedan en el extremo inicial y final del r´ respectivamente ıo, 2. El estado inicial se representa como (3, 3, i, 0, 0) y el final como (0, 0, f, 3,3) 3. Se dispone de cinco operadores: Mover1C(x,y), Mover2C(x,y), Mover1M(x,y), Mover2M(x,y), y Mover1M1C(x,y). 4. La heur´ ıstica a utilizar es: h2 (n) = 2 × (Ci + Mi ) − orilla(n) (1)

donde orilla(n)=1 si en el estado n la barca est´ en la orilla i (B = i), y orilla(n)=0 si la barca est´ en la a a orilla final (B = f ).

Ejercicio 2
Supongamos que tenemos un algoritmo de b´squeda de tipo elmejor primero que utiliza la siguiente funci´n u o de evaluzaci´n: f (n) = (2 − w) ∗ g(n) + wh(n) o ¿Qu´ tipo de b´squeda hace cuando w=0? ¿y cuando w=1? ¿y para w=2? e u ¿Para qu´ valores de w el algoritmo es admisible? e

Ejercicio 3
Hare & Hounds (Figura ??) es un juego de estrategia para 2 jugadores: la presa y el cazador. La presa decide los movimientos de la liebre mientras que elcazador, decide los movimiento de los perros. La presa gana el juego si consigue llegar de un extremo al otro del tablero. En cambio, el cazador gana si logra atrapar a la liebre, es decir si se alcanza una situaci´n del juego en la que la liebre no puede realizar ning´n movimiento. En cada turno cada o u jugador puede mover s´lo una ficha y siempre a una de las casillas adyacentes. Las fichas del cazadorno pueden o retroceder. El primer turno corresponde siempre al cazador. Se pide: Indica posibles representaciones de los estados. Describe los operadores del juego. ¿Qu´ funciones de evaluaci´n se te ocurren para programar un jugador autom´tico inteligente de Hare & e o a Hounds. En http://www.appletonline.com/JavaApplets/HoundsAndHare/ puede encontrarse un applet para jugar a Hare & Hounds.Figura 1: Posici´n inicial de la liebre y los perros en el juego de Hare & Hounds o

Ejercicio 4
Se tiene un robot aut´nomo en una habitaci´n cuadrada de 6x6 casillas (Figura ??). El robot es capaz de o o realizar desplazamientos verticales y horizontales y reconoce un obst´culo si esta en una de las casillas adyacentes. a Suponiendo que el robot utiliza algoritmos de b´squeda para planificar susmovimientos contesta a las siguientes u preguntas:

Figura 2: El Robot tiene que ir de una esquina de la habitaci´n a la otra o ¿Qu´ heur´ e ıstica podr´ utilizar el robot para guiarse desde su posici´n actual hasta el otro extremo de la ıa o habitaci´n? o

¿Qu´ camino tomar´ el robot si su movimiento estuviese determinado por un algoritmo de b´squeda en e ıa u escalada con la heur´ ısticadel apartado anterior? Suponer que los estados sucesores se generan aplicando los operadores de desplazamiento en este orden: [derecha, abajo, izquierda, arriba]? Y siguiesen el orden:[arriba, izquierda, abajo, derecha] ¿Qu´ camino tomar´ e ıa? Siguiendo el primer orden de operadores ¿Qu´ camino tomar´ el robot si sus movimientos estuviesen guiados e ıa por un algoritmo de b´squeda en haz con...