La casa de pepita

Añadir en las propiedades del proyecto a la variable de entorno PATH la siguiente ruta: C:\Program Files\EclipseARM\sourcery-g++-lite-arm-2011.03\bin


Añadir en las propiedades de debug la misma ruta a la variable de entorno
D  I ´
U C III  M
Ingenier´ıa en Informatica ´
Inteligencia Artificial
Octubre 2007
Hoja de Ejercicios 1:
Espacio deEstados
Comentarios generales sobre los ejercicios
• Asumiendo que se conocen los contenidos teoricos, el tiempo estimado para ´
realizar los ejercicios es de 2 horas
• Describir las soluciones a los ejercicios de una manera lo mas formal posible ´
Ejercicio 1
1. Definir el tamano del espacio de estados del problema de las garrafas, asumi ˜ endo que en el estado inicial las dos
garrafasestan vac ´ ´ıas.
2. ¿Son las acciones reversibles?
3. Se dice que un espacio de estados es conexo, si para cualquier par de estados x e y hay un camino hx, . . . , yi entre ellos.
¿El espacio de estados de este problema es conexo? Razonar la respuesta.
Ejercicio 2
Se pide:
1. Calcular el tamano del espacio de estados del 8-Puzle. ˜
2. Calcular el tamano del espacio de estados del 15-Puzle. ˜Considerese ahora el caso del N-Puzle: ´
3. ¿Cual es la expresi ´ on general para el tama ´ no del espacio de estados del N-Puzle? ˜
4. ¿Cual es el factor de ramificaci ´ on medio? ´
En vez de la version popular del N-Puzle en la que el blanco es desplazado ´ unicamente a posiciones inmediatamente ´
adyacentes, considerese ahora el caso en el que el blanco puede desplazarse a cua ´ lquierposicion de la misma fila o columna ´
en la que se encuentra. El juego resultante se conoce como Macro N-Puzle. Por lo tanto, para el Macro N-Puzle:
5. ¿Cual es la expresi ´ on general para el tama ´ no del espacio de estados? ˜
6. ¿Cual es el factor de ramificaci ´ on medio? Comp ´ aralo con el obtenido en la secci ´ on 4 y discute su relaci ´ on con el ´
obtenido ahora.8 1 6
3 5 7
4 9 2
(a) n= 3
3 6 12 13
10 15 1 8
5 4 14 11
16 9 7 2
(b) n = 4
Figura 1: Ejemplos de cuadrados magicos ´
Ejercicio 3
Un cuadrado magico consiste en una distribuci ´ on de n ´ umeros en filas y columnas, formando un cuadrado, de forma que ´
los numeros de cada fila, columna y diagonal suman lo mismo. Aunque ´ es posible recrear diferentes tipos de cuadrados
magicos, tradicionalmente se forman conlos n ´ umeros naturales desde el 1 hasta ´ n
2 donde n es el lado del cuadrado.
Se pide:
1. Representar el problema de generacion autom ´ atica de cuadrados m ´ agicos de tama ´ no˜ n como un espacio de problemas.
2. ¿Cual ser ´ ´ıa el factor de ramificacion y la profundidad de un ´ arbol de b ´ usqueda desarrollado en el espacio de problemas ´
identificado en el apartado anterior?
3. Apartir de un cuadrado vac´ıo, representar un arbol de b ´ usqueda que muestre la aplicaci ´ on de operadores para ´ n = 2
Ejercicio 4
Considerense dos tri ´ angulos que comparten un lado, de modo que cada estado del puz ´ le consiste en cuatro piezas, una en
cada esquina de los dos triangulos, como se muestra en la figura 2(a), donde los dos tri ´ angulos ser ´ ´ıan h1, 3, 4i y h2, 3, 4i.
4
1 23
(a) Posicion de ejemplo ´
1
3 2
4
(b) Un posible vecino
2
1 3
4
(c) Otro vecino factible
Figura 2: Configuraciones validas del puzle ´
Un movimiento en este juego consiste en la rotacion de las tres esquinas de un ´ unico tri ´ angulo. Por ejemplo, a partir de la ´
posicion de la figura 2(a), dos movimientos legales dispondr ´ an el puzle como se muestra en las figuras 2(b) y 2(c).´
Se pide:
1. Dibujar el espacio de estados del problema.
2. Si ahora solo se permitieran giros a favor de las agujas del reloj, ¿c ´ omo es el espacio de estados resultante? ´
Ejercicio 5
Mi monovolumen nuevo es muy versatil. En principio, pueden montarse hasta 7 personas: 2 dela ´ nte, 3 detras, y 2 en una
tercera fila de asientos. Todos los asientos son individuales e independientes....