2.10.2 IS/Búsqueda y Satisfacción de la Restricción. (5 horas)

Tópicos

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

Objetivos

• 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.
• Describir el problema de explosión combinatoria y sus consecuencias.
• Seleccionar un algoritmo apropiado de búsqueda de fuerza bruta para un problema, implementarlo y caracterizar sus complejidades de tiempo y espacio.
• 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.
• Describir bajo que condiciones los algoritmos de heurística garantizan una solución óptima.
• Implementar la búsqueda mínima con poda alfa-beta para juegos de dos.
• Formular un problema en español utilizando un algoritmo de backtracking cronológico.