4.45.4.2 IS/Búsqueda y Satisfacción de la Restricción. (4 horas) [Nivel Bloom 3]

Referencias Bibliográficas: [,]

Tópicos

1. Problemas de espacio.
2. Búsqueda de fuerza bruta (respiro primero, profundidad primero, profundidad primero con profundización iterativa).
3. Búsqueda del mejor primero (mejor genérico primero, algoritmo de Dijkstra, A*, admisibilidad de A*).
4. Juegos de dos jugadores (búsqueda mínima, poda alfa-beta).
5. Satisfacción de la restricción (backtracking métodos de búsqueda local y seguimiento).

Objetivos

1. Formular un eficiente problema expresado en el idioma español, caracterizando este problema en términos de estados, operadores, estado inicial y una descripción del estado final.
2. Describir el problema de explosión combinatoria y sus consecuencias.
3. Seleccionar un algoritmo apropiado de búsqueda de fuerza bruta para un problema, implementarlo y caracterizar sus complejidades de tiempo y espacio.
4. Seleccionar un algoritmo de búsqueda heurística para un problema, implementarlo por medio del diseño de la función de evaluación heurística necesaria.
5. Describir bajo que condiciones los algoritmos de heurística garantizan una solución óptima.
6. Implementar la búsqueda mínima con poda alfa-beta para juegos de dos.
7. Formular un problema en español utilizando un algoritmo de backtracking cronológico.