015 — Costo uniforme, búsqueda voraz y A*

← Clase anterior · Índice de la parte · Clase siguiente →

Parte: 01 — IA simbólica, búsqueda, lógica y planificación
Nivel: fundamentos · Horas estimadas: 4
Laboratorio: search · Estado: EXECUTABLE_CORE

🎯 Propósito

Comprender costo uniforme, búsqueda voraz y a* dentro de la evolución de la inteligencia artificial, implementar un experimento mínimo verificable y distinguir qué parte constituye evidencia frente a una afirmación todavía no comprobada.

📚 Resultados de aprendizaje

Al finalizar podrás:

1. Explicar costo uniforme, búsqueda voraz y a* usando los conceptos UCS, greedy, A*, heurística.
2. Ejecutar el laboratorio con una semilla explícita y revisar su contrato JSON.
3. Identificar al menos un supuesto, una limitación y un riesgo de aplicación.
4. Comparar el enfoque con la etapa anterior de la ruta de aprendizaje.
5. Producir una evidencia reproducible y una conclusión que no exceda los datos.

🧩 Conceptos centrales

UCS, greedy, A*, heurística

🗺️ Ubicación en el mapa de la IA

Esta clase da el salto de la búsqueda ciega (clase 014) a la búsqueda informada: usar conocimiento del dominio, empaquetado en una función heurística, para expandir menos nodos. A (Hart, Nilsson y Raphael, 1968, desarrollado para el robot Shakey) es probablemente el algoritmo más influyente de la IA clásica: sigue siendo el estándar en videojuegos, robótica y planificación (los planificadores tipo Fast Downward son A sobre espacios STRIPS). Prepara directamente la clase 016 (qué hace buena a una heurística).

📖 Fundamentos

🧭 Un solo algoritmo, tres funciones de evaluación

Los tres métodos son best-first search con frontera de prioridad ordenada por una función f(n); solo cambia f:

donde g(n) es el costo acumulado desde el inicio hasta n, y h(n) es una estimación del costo desde n hasta el objetivo, con h(objetivo) = 0.

función BEST-FIRST(problema, f):
    nodo ← Nodo(problema.s0, g=0)
    frontera ← cola de prioridad ordenada por f, con [nodo]
    alcanzados ← {problema.s0: nodo}
    mientras frontera no vacía:
        nodo ← frontera.pop_min()
        si IS-GOAL(nodo.estado): devolver nodo    # test al EXPANDIR
        para cada hijo en EXPANDIR(problema, nodo):
            s ← hijo.estado
            si s ∉ alcanzados o hijo.g < alcanzados[s].g:
                alcanzados[s] ← hijo               # re-apertura por camino mejor
                frontera.push(hijo)
    devolver FALLO

Dos detalles no negociables: el test de objetivo se hace al expandir (al sacar de la cola), no al generar — de lo contrario UCS y A pierden la optimalidad —; y un estado ya alcanzado se reabre* si aparece un camino más barato.

💰 Costo uniforme: optimalidad sin información

UCS expande siempre el nodo de menor g. Cuando extrae un nodo de la frontera, ya no puede existir camino más barato hasta él (todos los costos son ≥ 0): por eso es óptimo y completo si los costos de acción son ≥ ε > 0. Es la generalización de BFS a costos arbitrarios y equivale al algoritmo de Dijkstra con un solo destino. Su complejidad se expresa en función del costo óptimo C*: O(b^(1+⌊C*/ε⌋)), que puede ser mucho peor que O(b^d) si hay acciones muy baratas.

🎯 Voraz: rápida y ciega al pasado

La búsqueda voraz expande el nodo que parece más cercano al objetivo (f = h). Suele llegar rápido, pero ignora lo gastado: puede tomar caminos largos que "apuntan bien" y, con búsqueda en árbol, entrar en bucles. No es óptima ni completa (en árbol); su interés es que expande muy pocos nodos cuando la heurística es razonable.

⭐ A*: lo mejor de ambos

A ordena por f(n) = g(n) + h(n): el costo estimado de la mejor solución que pasa por n*. Sus garantías dependen de la heurística (definiciones formales en la clase 016):

• Con h admisible (nunca sobreestima): A con búsqueda en árbol es óptimo*.
• Con h consistente (h(n) ≤ c(n, a, n′) + h(n′)): A* con búsqueda en grafo es óptimo y nunca necesita reabrir nodos; los valores f a lo largo de cualquier camino son no decrecientes.
• A es óptimamente eficiente*: ningún algoritmo óptimo que use la misma h puede evitar expandir los nodos con f(n) < C*.

Su límite práctico es la memoria: guarda toda la frontera y los alcanzados, exponencial en el peor caso. Variantes como IDA y SMA cambian tiempo por memoria.

🧮 Ejemplo trabajado

Grafo dirigido con costos; inicio S, objetivo G. Heurística entre paréntesis:

S(6) --2--> A(4)     S --3--> B(2)
A --3--> C(1)        B --4--> C(1)
C --2--> G(0)        B --6--> G(0)

Verificación de admisibilidad: los costos reales al objetivo son h(S)=7, h(A)=5, h(B)=6, h(C)=2; cada h está por debajo ✔.

Traza de A* (f = g + h; la frontera muestra estado: g+h=f):

• Voraz habría hecho: S → B (h=2) → G (h=0): devuelve S→B→G con costo 9 ≠ óptimo.
• UCS expande S(0), A(2), B(3), C(5), G(7): mismo resultado que A pero ordenando por g puro; en grafos grandes expande muchos más nodos que A.
• El paso 3 muestra la re-apertura: C se había alcanzado vía B con g=7 y se sustituye al hallar g=5. Esta h es admisible pero no consistente: h(S)=6 > c(S,B)+h(B)=3+2=5, y esa subestimación relativa de B hizo que B se expandiera "demasiado pronto"; por eso hubo reapertura.

📊 Propiedades y comparación

flowchart TD
    P["Cola de prioridad por f(n)"] --> U["UCS: f = g<br/>ondas concéntricas de costo"]
    P --> V["Voraz: f = h<br/>flecha hacia el objetivo"]
    P --> A["A*: f = g + h<br/>elipse dirigida"]
    U --> UO["✔ óptimo<br/>✘ expande de más"]
    V --> VO["✔ rápido<br/>✘ subóptimo"]
    A --> AO{"¿h admisible?"}
    AO -- sí --> OK["✔ óptimo y<br/>óptimamente eficiente"]
    AO -- no --> NO["puede devolver<br/>solución subóptima"]

⚠️ Errores conceptuales frecuentes

1. Testear el objetivo al generar el nodo (como en BFS). UCS y A deben testearlo al expandir*; el primer camino que genera el objetivo puede no ser el más barato (véase el paso 2 vs. 5 del ejemplo).
2. "A* siempre es más rápido que UCS." Solo si h aporta información; con h = 0, A es UCS. Y una h cara de calcular puede hacer que A pierda en tiempo de reloj aunque expanda menos nodos.
3. "Greedy no sirve porque no es óptimo." En problemas donde cualquier solución razonable vale y el tiempo apremia, voraz (o weighted A*, f = g + w·h) es la elección correcta consciente del trade-off.
4. Ignorar la re-apertura de nodos. Con heurística admisible pero no consistente, marcar estados como "cerrados para siempre" rompe la optimalidad de A* en grafo.
5. Confundir el costo del camino con la profundidad. UCS con costos uniformes degenera en BFS; la diferencia solo aparece cuando c varía por acción.

🚀 Del aprendizaje a la operación

Entre este laboratorio y un A de producción (navegación, videojuegos, ruteo logístico) median: heurísticas específicas del dominio validadas empíricamente (clase 016), estructuras de datos afinadas (montículos con decrease-key o cubetas), preprocesamiento del grafo (contraction hierarchies en mapas reales, que dejan a Dijkstra puro obsoleto a escala continental), replanificación incremental cuando el mundo cambia (D Lite en robótica) y límites de memoria explícitos con degradación a variantes anytime. Además, el grafo real viene de datos con errores: un costo mal cargado invalida la "optimalidad" sin que el algoritmo lo detecte.

🧪 Laboratorio

python lab.py

El laboratorio llama a ai_evolution.labs.run_lab("search"). Esta decisión evita 183 implementaciones divergentes: cada clase tiene un entrypoint propio, pero los motores didácticos se prueban como una biblioteca común.

🔍 Evidencia esperada

• tipo de laboratorio y semilla;
• entradas o decisiones observables;
• resultado estructurado;
• lista evidence con hechos que pueden inspeccionarse;
• lista limitations que impide presentar la demo como producción.

📓 Notebooks

• 📓 notebook.ipynb: recorrido guiado con la materia resumida.
• ✍️ notebook_student.ipynb: ejercicios para resolver.
• ✅ notebook_solution.ipynb: solución de referencia explicada.

📝 Evaluación

Consulta assessment.md para preguntas y criterio de aceptación.

⚠️ Errores comunes

❓ Preguntas frecuentes

¿Debo usar una API comercial?
No. El núcleo funciona localmente. Las extensiones LIVE se documentan por separado.

¿El laboratorio representa una implementación industrial?
No por sí solo. Enseña el contrato y el patrón; producción exige integración, seguridad, observabilidad, pruebas y operación.

¿Dónde profundizo?
Revisa las especializaciones enlazadas en el README raíz y la ruta siguiente.

🔗 Referencias

• Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Trans. on Systems Science and Cybernetics, 4(2). https://doi.org/10.1109/TSSC.1968.300136 — uso: fuente primaria del mecanismo estudiado
• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik, 1. https://doi.org/10.1007/BF01386390 — uso: fuente primaria del mecanismo estudiado
• Russell, S. y Norvig, P. (2021). AIMA (4.ª ed.), §3.5 "Informed (Heuristic) Search Strategies". https://aima.cs.berkeley.edu/ — uso: desarrollo extendido del tema
• Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley — análisis formal de A* y sus variantes.

📜 Papers que fundamentan esta clase

Bloque generado por python scripts/link_papers_to_classes.py. La fuente es papers/catalog/papers.json.

Cada ficha explica el problema anterior, la matemática mínima, los límites y los errores de atribución más frecuentes. Para leerlas con método: cómo leer un paper de IA · anexos matemáticos.

📚 Bibliografía de apoyo

Bloque generado por python scripts/link_sources_to_classes.py. Cada obra lleva su localizador verificado en sources/bibliography.json.

Los papers dicen de dónde salió el mecanismo. Estas obras lo desarrollan con el espacio que una clase no tiene: teoría completa, demostraciones y ejercicios.

⬅️ Clase anterior

014 — Búsqueda en anchura y profundidad

➡️ Siguiente clase

016 — Diseño y validación de heurísticas

📝 Evaluación completa

❓ Preguntas

1. Define costo uniforme, búsqueda voraz y a* sin usar una marca o framework como definición.
2. Explica la relación entre UCS, greedy, A*, heurística.
3. Ejecuta lab.py dos veces con la misma semilla. ¿Qué debe conservarse?
4. Identifica una afirmación permitida y una afirmación exagerada sobre el resultado.
5. Propón una prueba negativa o un caso límite.

🏆 Reto verificable

Amplía el resultado del laboratorio con una clave student_extension que incluya:

• el supuesto que estás probando;
• una medición o comprobación;
• la conclusión;
• una limitación.

✅ Criterio de aceptación

• [ ] lab.py termina con código 0.
• [ ] El resultado contiene kind, seed, evidence y limitations.
• [ ] La extensión no modifica el comportamiento de otras clases.
• [ ] La interpretación referencia datos impresos por el laboratorio.
• [ ] Se declara al menos un riesgo o condición de no uso.