1Executive Summary
La clase repasó la clasificación de los algoritmos de búsqueda y comparó DFS y BFS; a partir de ahí se profundizó en el algoritmo de costo uniforme (UCS), sus estructuras (cola de prioridad, g(n), predecesores y conjunto explorado), su funcionamiento paso a paso con grafos de ejemplo, la poda de rutas dominadas y su implementación en Python. Se resolvieron ejemplos hasta obtener rutas óptimas como S-D-E-X (costo 11) y A-C-G-H (costo 5), y se relacionó UCS con el laberinto del laboratorio y los costos especiales de duchas y quesos.
Después, con la exposición estudiantil sobre diseño de heurísticas, se estudiaron h(n), h*(n), admisibilidad, consistencia, informatividad y costo de cálculo; se vieron aplicaciones en Sudoku (MRV), navegación de NPC con A* e itinerarios ponderados. El profesor complementó la búsqueda informada: diferencia con la no informada, componentes, f(n) = g(n) + h(n), búsqueda voraz, A*, distancia en línea recta y euclidiana, tipos de heurísticas y conteo de incorrectos. Al final se acordaron fechas de entrega, reposición y Proyecto 1, y se propuso una demostración de herramientas de IA para la próxima clase.
2Class Outline
Comparación entre DFS y BFSEl profesor contrasta pila y cola, estrategia de exploración, optimalidad y consumo de memoria con una tabla y un árbol de ejemplo.
Idea general del algoritmo UCSSe introduce la búsqueda por costo uniforme como la expansión del nodo con menor costo acumulado desde la raíz.
Ejemplo UCS: expansión desde SSe registran rutas con su costo (S^0, SA^5, SB^9, etc.) y se expande siempre el nodo más económico, mostrando empates y rutas alternativas.
Grafo A–H y ruta óptimaSe construye un grafo con costos entre A, B, C, D, F, G y H y se obtiene la ruta óptima A–C–G–H con costo 5.
Implementación de UCS en PythonSe presenta uniform_cost_search con dist, parent y frontier, y la representación del grafo como diccionario de tuplas (vecino, costo).
Exposición sobre diseño de heurísticasUn compañero define la heurística, la función h(n) frente a h*(n) y propiedades como admisibilidad, consistencia e informatividad.
Búsqueda informada vs. no informadaEl profesor complementa la exposición y explica cómo la heurística dirige la exploración frente a la búsqueda a ciegas.
Funciones g(n), h(n) y f(n)Se definen costo acumulado, estimación restante y función de evaluación f(n) = g(n) + h(n), con h = 0 en la meta.
Heurística de distancia euclidianaSe presenta el mapa de Rumania, se asignan coordenadas y se calcula la distancia en línea recta a Bucarest con la fórmula euclidiana.
Cronograma, entrega de BCU y Proyecto 1Se acuerdan fechas de entrega, reposición y presentación del proyecto, y se detallan los entregables del Proyecto 1.
3Important Dates & Deliverables
AssignmentEntrega complementaria de UCS/BCU y análisis comparativo
Implementar el algoritmo de costo uniforme en el laboratorio pendiente y complementar la entrega 2, sin una tercera entrega separada, con UCS, el análisis final, la comparación entre BFS, DFS y UCS, los resultados y un informe breve que explique qué se hizo, cómo se implementó y qué resultados se obtuvieron. En las conclusiones, analizar si BFS/DFS ignoran los costos y si UCS entrega la ruta más económica.
Mentioned at 00:53:57
NoticeExposición estudiantil sobre heurística
El grupo encargado expone el tema de heurística durante la sesión; se les da paso para compartir pantalla.
Mentioned at 01:06:21
NoticePausa de 20 minutos
El profesor hace una pausa para tomar café y pide regresar a las y 55 para ver el último ejemplo sobre la función de distancia.
Mentioned at 02:23:05
NoticePróxima clase: búsqueda informada II (voraz y A*)
La siguiente sesión será el 17 de octubre y se continuará con búsqueda informada II, incluyendo la implementación de los algoritmos voraz y A*.
Mentioned at 03:07:51
NoticeClase de reposición el 19 de octubre
Se repondrá la última clase pendiente (teoría de juegos) el 19 de octubre para que la presentación del proyecto del 24 se realice sin inconvenientes; si alguien no puede asistir, quedará la grabación.
Mentioned at 03:10:05
ProjectProyecto 1: algoritmos de búsqueda
Presentación del Proyecto 1 el 24 de octubre. Integra BFS, DFS, costo uniforme y A* con heurística propia en una aplicación en Python; grupos de máximo cuatro personas, sin exigencia de interfaz gráfica avanzada. Entregables: código fuente comentado, informe escrito con problema, modelado, algoritmos, heurística y resultados, y video de máximo 10 minutos.
Mentioned at 03:10:39
NoticeDemostración de herramientas de IA
Si todos están de acuerdo, el docente mostrará en la próxima clase herramientas de inteligencia artificial para generar mapas mentales, ayudas cognitivas y guías de estudio; los estudiantes deben recordárselo al inicio de esa clase.
Mentioned at 03:17:25
4Topics & Concepts Covered
Algoritmos de búsqueda en inteligencia artificial
Técnicas que recorren un espacio de estados hasta encontrar una solución; se clasifican en búsqueda no informada e informada. Se repasan sus familias y algoritmos representativos.
Comparación entre DFS, BFS y costo uniforme
DFS usa pila y explora en profundidad; BFS usa cola y explora por niveles, garantizando el camino con menos aristas a mayor costo de memoria. UCS expande por costo acumulado, minimiza el costo total y es el único que incorpora penalizaciones y beneficios del entorno.
Algoritmo de costo uniforme (UCS): concepto y estructuras
UCS selecciona siempre el nodo de menor costo acumulado desde la raíz mediante una cola de prioridad ordenada por g(n). Requiere distancias g(n), predecesores para reconstruir el camino y un conjunto de explorados o cerrados con costo mínimo confirmado; también necesita criterios de desempate.
Ejemplos de expansión y poda en UCS
Con grafos de ejemplo se muestra cómo se registran rutas con superíndice de costo (S^0, SA^5, SB^9, etc.), se expande el menor costo y se eliminan rutas dominadas hacia un mismo nodo. Se obtienen rutas óptimas como S-D-E-X con costo 11 y A-C-G-H con costo 5, y se aclara que encontrar la meta no detiene la búsqueda si puede aparecer una ruta más barata.
Implementación de UCS en Python
La función uniform_cost_search usa dist, parent y frontier para expandir por menor costo y reconstruir el camino solución. El grafo se representa como un diccionario de listas de tuplas (vecino, costo), guardando costos directos y no acumulados.
Laberinto de laboratorio y costos de transición
El laberinto con muros, duchas y quesos sirve para ilustrar costos de transición (1, 2 y fracciones) y analizar en el informe qué algoritmo encuentra rutas viables o económicas. La cuadrícula del ratón refuerza que el camino óptimo es el de menor costo/tiempo acumulado.
Diseño de heurísticas: definición y propiedades
Una heurística es una función o regla que usa información del problema para estimar qué tan lejos se está de la meta y orientar la exploración. Se estudian h(n) frente a h*(n), la admisibilidad (h(n) ≤ h*(n)), la consistencia, la informatividad y el costo de cálculo.
Aplicaciones prácticas de heurísticas: Sudoku, NPC e itinerarios
Se aplica el diseño de heurísticas a la selección de celdas en Sudoku con MRV, a la navegación de NPC con A* y penalizaciones por terreno, y a la elección de itinerarios de viaje con pesos de 40% costo, 35% tiempo y 25% preferencias. Se concluye que una heurística no es automáticamente admisible y que su calidad depende de comprender la estructura del problema.
Búsqueda informada: comparación, componentes y funciones
La búsqueda informada usa conocimiento del dominio para dirigir la exploración, a diferencia de la búsqueda a ciegas. Se repasan espacio de estados, función de sucesores, estado meta y costo g(n), y se añade h(n) y la función de evaluación f(n) = g(n) + h(n); la heurística vale 0 en la meta y se elige el nodo con menor h.
Búsqueda voraz, A* y heurística por distancia
La búsqueda voraz usa f(n)=h(n) y puede ser rápida pero no garantiza optimalidad; A* usa f(n)=g(n)+h(n) y puede garantizar optimalidad con una heurística admisible. Se ejemplifica con el mapa de Rumanía y la distancia en línea recta a Bucarest, y se discute el balance entre informatividad y costo computacional.
Tipos de heurísticas y distancia euclidiana
Se presentan familias de heurísticas: distancias Manhattan, Euclidiana y Chebyshev, conteo de incorrectos, relajación del problema, pattern databases, combinadas, aprendidas y específicas de dominio. Con coordenadas sobre el mapa de Rumania se calcula la distancia euclidiana y se aplica el conteo de incorrectos en piezas deslizantes, donde h=0 indica la meta.
Proyecto 1: integración de algoritmos de búsqueda
El Proyecto 1 integra BFS, DFS, costo uniforme y A* con heurística propia en una aplicación en Python sobre un problema elegido por el grupo. Se permiten grupos de máximo cuatro personas, sin exigencia de interfaz gráfica avanzada, con código comentado, informe y video de máximo 10 minutos.
Every board capture with what the teacher said while it was shown.
Open the full timeline →