« Sobre los espacios de… « || Inicio || » Búsquedas No Informad… »

Ejercicios de Búsqueda no Informada

Última modificación: 30 de Septiembre de 2016, y ha tenido 1493 vistas

Etiquetas utilizadas: || || || ||

Muchos de los ejercicios que se plantean a continuación se pueden (y deben) resolver por diversos procedimientos de búsqueda, por lo que se propone que, a medida que se vayan estudiando otros medios de resolución, se apliquen sobre estos mismos ejercicios para adquirir en toda su plenitud las diferencias y similitudes entre los metodos estudiados.

  1. A partir del modelo del 8-puzle de NetLogo y del modelo que incluye el método de resolución general con BFS, generar un jugador automático del 8-puzle, de forma que dada un situación inicial, muestre la sucesión de movimientos necesaria para resolverlo.
  2. Basándose en el método de resolución general con BFS que se ha proporcionado, construir uno equivalente pero que haga uso de DFS (con límite de profundidad).
  3. Adaptar el algoritmo DFS de resolución general para que trabaje con agentes en vez de con listas, y aplicarlo sobre algunos de los ejemplos.
  4. Implementar el algoritmo de Profundidad iterada en NetLogo.
  5. Problema de las jarras: Se tienen dos jarras de agua, una de 4 litros y otra de 3 litros sin escala de medición.  Se desea tener 2 litros de agua en la jarra de 4 litros. Las siguientes operaciones son válidas: llenar las jarras, tirar agua de las jarras, pasar agua de una jarra a otra. Expresa el problema como un problema búsqueda en un espacio de estados correctamente formalizado, y resuelvelo por medio de alguno de los modelos que se hayan visto en clase.
  6. Monjes y Caníbales: Se tienen 3 monjes y 3 caníbales en el margen oeste de un río. Existe una canoa con capacidad para dos personas como máximo. Se desea que los seis pasen al margen este del río, pero hay que considerar que no debe haber más caníbales que monjes en ningún sitio porque entonces los caníbales se comen a los monjes. Además, la canoa siempre debe ser conducida por alguien. Expresa el problema como un problema búsqueda en un espacio de estados correctamente formalizado, y resuelvelo por medio de alguno de los modelos que se hayan visto en clase.
  7. El Granjero: Hace mucho tiempo un granjero fue al mercado y compró un lobo, una cabra y una col. Para volver a su casa tenía que cruzar un río. El granjero dispone de una barca para cruzar a la otra orilla, pero en la barca solo caben él y una de sus compras.Si el lobo se queda solo con la cabra se la come, si la cabra se queda sola con la col se la come. El reto del granjero era cruzar él mismo y dejar sus compras a la otra orilla del río, dejando cada compra intacta. ¿Cómo puede hacerlo?
  8. Torres de Hanoi: Se hallan N discos de distinto tamaño apilados sobre una base A de manera que cada disco se encuentra sobre uno de mayor radio. Existen otras dos bases vacías B y C. El objetivo es llevar todos los discos de la base A hasta la base C, para lo cual puede usarse la base B. Considerar que se puede mover sólo un disco a la vez, y cada disco puede descansar solamente en las bases y no en el suelo. Recordar que los discos deben situarse siempre sobre uno de mayor radio. Expresa el problema como un problema búsqueda en un espacio de estados correctamente formalizado, y resuelvelo por medio de alguno de los modelos que se hayan visto en clase para el caso de 3 y 4 discos.
  9. Problema de las N reinas: situar N reinas en un tablero de ajedrez de NxN sin que se amenacen entre ellas. Una reina amenaza a otra si está en la misma fila, columna o diagonal.
  10. Criptoaritmética: Las letras representan dígitos. El objetivo es determinar el valor de cada una de las letras de tal manera que la operación sea correcta aritméticamente. Letras iguales - dígitos iguales, letras diferentes - dígitos diferentes. Ningún número inicia con cero. Por ejemplo:
  11. Cuadrados latinos 3 X 3 (cuadrados mágicos): Tenemos un tablero 3 X 3, en cada posición colocamos un número del 1 al 9, ninguno de estos números puede repetirse; el objetivo es tener el tablero completo, es decir, un número en cada posición del mismo y es necesario que el valor de la suma de las filas, columnas y diagonales sea siempre el mismo valor: 15. Diseñad algunas heurísticas que puedan aplicarse a la resolución de este juego y haced un modelo de NetLogo que pueda resolverlo con el algoritmo A* usando estas estrategias.

« Sobre los espacios de… « || Inicio || » Búsquedas No Informad… »