UBV Algoritmos Heurísticos 2022 II

  Ejercicios de Algoritmos. 1.- Tenemos un tablero de 3x3 casillas como el de la figura. En cada esquina tenemos un caballa de ajedrez, dos caballos negros y dos blancos. Deseamos inter- cambiar los caballos negros con los blancos. a ) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades ha de cumplir. Estima el tamaño del espacio de estados. b ) ¿Importa el camino o sólo el estado final?¿la solución ha de ser óptima? 2.- Dispones de dos jarras de agua, una de 4 litros y otra de 3 litros. Tiene un grifo que te permite llenar totalmente las jarras de agua, necesitas obtener exactamente 2 litros en la jarra de cuatro litros a ) Define que elementos forman el estado, el estado inicial y cual es estado final o que propiedades ha de cumplir. Estima el tamaño del espacio de estados. b ) ¿Importa el camino o sólo el estado final?¿la solución ha de ser óptima?

 Ejercicio número dos                                                                        Descargar         

Ejercicios de búsqueda Informada

 Búsqueda No informada

 Espacio  de estados

 Aproximación Conceptual

  Ejercicio 1 Se pide: 1. Calcular el tama ñ o del espacio de estados del 8-Puzle. 2. Calcular el tamaño del espacio de estados del 15-Puzle. Considérese ahora el caso del N-Puzle: 3. ¿Cual es la expresión general para el tamaño del espacio de estados del N-Puzle? En vez de la versión popular del N-Puzle en la que el blanco es desplazado unicamente a posiciones inmediatamente adyacentes, considérese ahora el caso en el que el blanco puede desplazarse a cualquier posición 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. ¿Cu á l es la expresión general para el tamaño del espacio de estados?

 Búsqueda no Informada

  Los algoritmos de búsqueda ciega  o no informada P roporcionan métodos generales para recorrer los árboles de búsqueda asociados a la representación del problema, por lo que se pueden aplicar en cualquier circunstancia. Se basan en la estructura del espacio de estados y determinan estrategias sistemáticas para su exploración, es decir, que siguen una estrategia fija a la hora de visitar los nodos que representan los estados del problema. Se trata también de algoritmos exhaustivos, de manera que, en el peor de los casos, pueden acabar recorriendo todos los nodos del problema para hallar la solución Caracterización de las búsquedas ciegas o no informada. La búsqueda ciega o no informada sólo utiliza información acerca de si un estado es o no objetivo para guiar su procesu de búsqueda. Los métodos de búsqueda ciega se pueden clasificar en dos grupos básicos: Métodos de búsqueda en anchura . Son procedimientos de búsqueda nivel a ni...

 Referencias electrónicas 1.- Una aproximación a la heurística y metaheurísticas                 https://core.ac.uk/download/pdf/236383515.pdf         trabajo a consultar 2.- 

  Plan de evaluación Tres(3) trabajas escritos y presentación de una síntesis de cada trabajo en diapositivas. Cada uno tiene una nota con Ponderación de 25% de la nota final Una (1) evaluación presencial   Ponderación de 25% Los  trabajos se presentan en software libre. NO se aceptan trabajos en software propietario.

    Introducción Tema 1: Arboles. 1.1 Arboles. Definición. Tipo de operaciones. Recorridos ( preorden, inorden,  postorden). 1.2 Solución de problemas mediante la búsqueda. Conceptos básicos (metas,  acciones,  estados, espacio de estados..) Tipos de problemas.  Formulación de problemas  bien definidos. Estrategias de búsquedas.  Algoritmo genérico de búsqueda en grafos. Tema 2: Algoritmos de búsqueda a ciegas. 2.1  Introducción . 2.2  Búsqueda en profundidad.  Algoritmo de búsqueda primero en profundidad.        Características. 2.3  Búsqueda en anchura.  Algoritmo de búsqueda primero en anchura.       Características. Tema 3: Algoritmos de búsqueda heurísticas. 3.1  Introducción .    ¿Qué  es una heurística?.  Búsqueda heurística. 3.2  Algoritmo de búsqueda primero el mejor (algoritmo A*).  Características. Tema 4: Algoritmos Gené...