Búsqueda Simple

“The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” — Edsger W. Dijkstra

Hemos modelado agentes que perciben y actúan. Hemos estudiado lógica, probabilidad y optimización. Pero hay una pregunta que todos estos marcos comparten: ¿cómo encuentra un agente el camino hacia su objetivo?

La respuesta es búsqueda. Y la idea central es sorprendentemente simple: un agente que busca tiene un espacio de estados — un grafo donde los nodos son configuraciones posibles del mundo y las aristas son acciones — y su tarea es encontrar un camino desde el estado inicial hasta un estado que satisfaga su objetivo.

Este módulo construye esa maquinaria desde cero: primero la teoría de grafos necesaria, luego la formulación de problemas como espacios de estado, y finalmente el algoritmo genérico del que BFS, DFS e IDDFS son instancias concretas.

Contenido

Materiales y flujo de trabajo

Paso	Material	Colab	Descripción
1	13.1 Grafos	—	Teoría: $G=(V,E)$, tipos, representaciones
2	13.2 Espacio de estados	—	Formulación de problemas como grafos
3	13.3 Algoritmo genérico	—	La abstracción central: frontera + explorado
4	Notebook 01 — Grafos		Construir, visualizar y representar grafos en Python
5	13.4 BFS	—	Búsqueda en amplitud: intuición, pseudocódigo, complejidad
6	13.5 DFS	—	Búsqueda en profundidad: intuición, pseudocódigo, complejidad
7	13.6 IDDFS y comparación	—	IDDFS, tabla comparativa, guía de uso
8	Notebook 02 — Búsqueda		BFS, DFS, IDDFS paso a paso en laberintos
9	Notebook de aplicación (elige uno)	—	Exploración profunda en un dominio

Notebooks de aplicación

Elige uno de los siguientes:

Notebook	Tema	Herramientas	Colab
03 — Laberintos	Generar y resolver laberintos perfectos; comparar BFS y DFS	numpy, matplotlib
04 — Coloreo de imagen	Flood fill y segmentación de regiones en grillas de píxeles	numpy, matplotlib

Objetivos de aprendizaje

Al terminar este módulo podrás:

1. Definir formalmente un grafo $G=(V,E)$, distinguir grafos dirigidos de no dirigidos, y simples de multigrafos
2. Comparar representaciones de grafos (lista de adyacencia vs. matriz) y elegir la apropiada según densidad
3. Formular cualquier problema de búsqueda como un espacio de estados $(S, s_0, A, T, \text{Goal})$ y construir el grafo correspondiente
4. Explicar el algoritmo genérico de búsqueda y por qué BFS y DFS son instancias del mismo algoritmo con fronteras distintas
5. Implementar QueueFrontier, StackFrontier y DepthLimitedFrontier como plug-ins del algoritmo genérico
6. Analizar BFS y DFS en términos de completitud, optimalidad y complejidad de tiempo y espacio
7. Aplicar IDDFS cuando se necesitan las garantías de BFS con la eficiencia de memoria de DFS
8. Seleccionar el algoritmo adecuado dado un problema concreto usando la tabla comparativa

Prerrequisitos

Mapa conceptual

graph TD
    A["Grafos G=(V,E)"] --> B[Tipos: dirigido / no dirigido]
    A --> C[Representación: listas / matrices]
    A --> D["Vocabulario: caminos, ciclos, conectividad"]
    D --> E[Espacio de estados como grafo]
    E --> F["Formulación: (S, s₀, A, T, Goal)"]
    F --> G[Algoritmo genérico de búsqueda]
    G --> H["Frontera = Cola → BFS"]
    G --> I["Frontera = Pila → DFS"]
    I --> J["DFS con límite de profundidad → IDDFS"]
    H --> K["Completo + Óptimo (sin pesos)"]
    J --> K
    I --> L["Eficiente en memoria, no óptimo"]

Cómo ejecutar el script de imágenes

cd clase/13_simple_search
python3 lab_search.py

Dependencias: numpy, matplotlib (ver requirements.txt).