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

Referencias Bibliográficas: [Nilsson, 2001,Ponce-Gallegos et al., 2014]

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.

Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad Católica San Pablo, Arequipa-Peru
basado en el modelo de la Computing Curricula de IEEE-CS/ACM