Capítulo 01: Búsqueda: resolver problemas como espacio de estados

Entrando en el tema

A mediados de los años cincuenta, Allen Newell, J. C. Shaw y Herbert Simon mostraron que un programa podía demostrar teoremas explorando sistemáticamente el espacio de posibles deducciones. Poco después formalizaron el General Problem Solver como intento de solucionador general mediante búsqueda en espacios de estados.¹ No usaba redes neuronales. No usaba aprendizaje. Usaba búsqueda.

Siete décadas después, la búsqueda sigue siendo el corazón de sistemas que usas a diario. Un sistema de navegación puede encontrar rutas explorando un espacio donde cada estado es una ubicación y cada acción es una carretera. Un videojuego puede mover personajes con A*, un algoritmo de búsqueda de 1968. Y cuando diseñamos un agente LLM que decide qué herramienta llamar a continuación, podemos modelar esa decisión —de forma implícita y heurística— como un problema de búsqueda.

Este capítulo empieza por el principio: ¿qué es exactamente un problema de búsqueda? ¿Cómo se modela? ¿Y por qué algo tan simple es, al mismo tiempo, tan poderoso y tan peligrosamente costoso?

El vocabulario de la búsqueda

Todo problema de búsqueda empieza con cuatro ideas operativas: estado, acción, meta y coste.² Luego, cuando lo escribimos con notación formal, esas ideas se descomponen un poco más para que no quede nada en el aire.

Estado

Una descripción suficiente de la situación actual. «Estoy en Madrid». «El robot está en la coordenada (3,7) mirando al norte». «El puzzle tiene las piezas en esta configuración».

El estado debe contener todo lo necesario para decidir qué hacer a continuación. Si falta información, el algoritmo tomará decisiones incorrectas. Piensa en el estado como una fotografía del problema en un instante: debe capturar todo lo relevante y nada de lo irrelevante.³

Un error clásico es incluir información redundante en el estado —«la temperatura ambiente», «el color del coche»— que no afecta a las decisiones pero multiplica el número de estados posibles. Cada bit innecesario en el estado duplica el espacio de búsqueda.

Acción

Una operación que transforma un estado en otro. «Viajar de Madrid a Barcelona» (coste: 620 km). «Avanzar una casilla hacia el norte» (coste: 1 paso). «Mover la pieza A a la posición B» (coste: 1 movimiento).

No todas las acciones están disponibles en todos los estados. Desde Madrid puedes viajar a Barcelona, pero no a Buenos Aires (no hay carretera). Esta restricción —llamada precondición— es lo que diferencia un problema bien modelado de uno imposible. Las acciones definen la topología del espacio de búsqueda: qué estados están conectados y a qué precio.⁴

Meta

La condición que queremos alcanzar. Puede ser un estado concreto («estar en Berlín») o una propiedad («tener todas las cajas en la zona de carga, da igual en qué orden»). La meta puede ser única o múltiple; puede ser un estado exacto o una condición abstracta.

Lo crucial es que la meta sea verificable. Dado un estado, debes poder responder «sí» o «no» a la pregunta «¿es este el objetivo?» sin ambigüedad. Si no puedes verificarlo, no puedes saber cuándo has terminado.⁵

Coste

El precio de cada acción o del camino completo. Distancia, tiempo, dinero, consumo de combustible, tokens de API: cualquier magnitud que queramos minimizar. El coste es lo que convierte «encuentra un camino cualquiera» en «encuentra el mejor camino».

Sin coste, cualquier camino sirve. Con coste, la búsqueda se convierte en optimización: no solo encontrar una solución, sino encontrar la mejor. Esta distinción —satisfacer vs optimizar— es una de las más importantes de la IA.⁶

La explosión combinatoria: por qué la búsqueda es difícil

El espacio de estados crece de forma aterradora. Imagina un problema donde cada estado tiene, de media, 10 acciones posibles (factor de ramificación $b = 10$). A profundidad 1, tienes 10 estados. A profundidad 2, 100. A profundidad 5, 100 000. A profundidad 10, diez mil millones.⁷

La forma compacta de verlo es esta:

$$N(d) = \sum_{i=0}^{d} b^i = \frac{b^{d+1} - 1}{b - 1}$$

Símbolo	Significado	Ejemplo
$N(d)$	Número total de nodos que aparecen hasta profundidad $d$, contando la raíz.	Si exploramos hasta profundidad 5, $N(5)$.
$b$	Factor de ramificación medio: cuántas acciones nuevas aparecen desde cada estado.	$b = 10$.
$d$	Profundidad máxima explorada: cuántas acciones tiene el camino más largo considerado.	$d = 5$.
$i$	Nivel concreto del árbol de búsqueda.	$i = 0$ es el estado inicial; $i = 5$, los estados a cinco acciones.

Con números:

$$N(5) = 1 + 10 + 100 + 1\,000 + 10\,000 + 100\,000 = 111\,111$$

Cinco decisiones encadenadas ya generan más de cien mil nodos. Con profundidad 10:

$$N(10) = \frac{10^{11} - 1}{9} = 11\,111\,111\,111$$

Más de once mil millones. Por eso no basta con decir «probemos todas las opciones». La búsqueda clásica consiste, en buena medida, en decidir qué opciones no merece la pena mirar.

Esto es la explosión combinatoria: el número de estados crece exponencialmente con la profundidad. No es un problema de hardware: aunque tuvieras un ordenador mil millones de veces más rápido, solo podrías explorar unos pocos niveles adicionales. La explosión combinatoria es el obstáculo central de la búsqueda.

Por eso los algoritmos de búsqueda no intentan explorar todo el espacio. Usan la frontera para decidir qué explorar a continuación, ignorando la mayor parte del espacio. La diferencia entre un algoritmo que encuentra la solución en segundos y uno que no la encuentra nunca está en cómo gestiona esa frontera.

Árbol de búsqueda vs grafo de estados

Aquí hay una distinción sutil pero crítica. El grafo de estados es el mapa real: todas las configuraciones posibles y cómo se conectan. Es la realidad física del problema. El árbol de búsqueda es lo que el algoritmo construye mientras explora: un registro de los caminos que ha probado.⁸

Imagina un laberinto. El grafo de estados es el laberinto completo —cada casilla es un estado, cada pasillo es una acción—. El árbol de búsqueda es el recorrido que haces al explorar: empiezas en la entrada, pruebas un pasillo, vuelves atrás si no lleva a ningún sitio, pruebas otro. El árbol crece a medida que avanzas, pero nunca ves el grafo completo. Si lo vieras, ya habrías resuelto el problema.

¿Por qué importa esta diferencia? Porque el grafo puede tener ciclos: puedes ir de A a B y de B a A, dando vueltas. El árbol, si no tienes cuidado, puede crecer infinitamente reflejando esos ciclos una y otra vez. Los buenos algoritmos de búsqueda mantienen un conjunto de estados visitados y evitan reexplorarlos. Sin esta precaución, BFS y UCS pueden quedar atrapados en bucles infinitos.⁹

Cómo funciona un algoritmo de búsqueda

Todos los algoritmos de búsqueda clásicos comparten la misma estructura.¹⁰ Mantienen una frontera: el conjunto de estados que han sido descubiertos pero aún no explorados. El bucle es:

1. Extraer un estado de la frontera.
2. Comprobar si es la meta. Si lo es, reconstruir el camino y terminar.
3. Expandir: generar todos los estados alcanzables desde este estado mediante las acciones disponibles.
4. Añadir los nuevos estados a la frontera, siempre que no hayan sido visitados antes.
5. Repetir desde el paso 1.

Eso es todo. Cuatro pasos y un bucle. La diferencia entre BFS, DFS, coste uniforme, greedy y A* está exclusivamente en el paso 1: qué estado extraemos de la frontera. La estructura de datos que usemos —cola, pila, cola de prioridad— determina completamente el comportamiento del algoritmo.

Definición formal del problema

Conviene fijar la notación con precisión. Un problema de búsqueda se define formalmente como una tupla:¹¹

$$\text{Problema} = (S, A, f, s_0, G, c)$$

Símbolo	Significado	Ejemplo
$S$	Espacio de estados: conjunto de todas las configuraciones posibles.	En un mapa, todos los cruces y ciudades que podrían visitarse.
$A(s)$	Acciones aplicables desde el estado $s$.	Desde Zaragoza, tomar la carretera hacia Barcelona o hacia Madrid.
$f(s, a)$	Función de transición: el estado que aparece al aplicar una acción.	$f(\text{Zaragoza}, \text{ir a Barcelona}) = \text{Barcelona}$.
$s_0$	Estado inicial.	Madrid.
$G$	Conjunto de estados meta.	$\{\text{Barcelona}\}$.
$c(s, a)$	Coste de aplicar la acción $a$ en el estado $s$.	Kilómetros, minutos, euros o tokens consumidos.

La fórmula dice algo bastante sencillo: para resolver el problema necesitamos saber dónde podemos estar, qué podemos hacer, qué ocurre al hacerlo, dónde empezamos, qué cuenta como llegar y cuánto cuesta cada paso. Si falta una de esas piezas, la búsqueda queda coja.

Una solución es una secuencia de acciones:

$$\pi = (a_1, a_2, \ldots, a_n)$$

La letra $\pi$ se lee «pi» y aquí representa un plan: una lista ordenada de acciones. No es todavía «la mejor» solución; solo es una candidata. Para comprobar si realmente sirve, aplicamos cada acción una detrás de otra:

$$s_i = f(s_{i-1}, a_i), \quad i = 1, 2, \ldots, n$$

Símbolo	Significado	Ejemplo
$\pi$	Plan o secuencia de acciones.	$(\text{Madrid} \to \text{Zaragoza}, \text{Zaragoza} \to \text{Barcelona})$.
$a_i$	Acción número $i$ del plan.	$a_1 =$ ir de Madrid a Zaragoza.
$s_i$	Estado alcanzado después de ejecutar $i$ acciones.	$s_1 =$ Zaragoza; $s_2 =$ Barcelona.
$f$	Función de transición que calcula el siguiente estado.	Aplicar «ir a Zaragoza» desde Madrid produce Zaragoza.
$n$	Número total de acciones del plan.	$n = 2$.

El plan es una solución si el último estado pertenece al conjunto de metas:

$$s_n \in G$$

En nuestro ejemplo, $s_2 = \text{Barcelona}$ y $G = \{\text{Barcelona}\}$. Por tanto, el plan llega a la meta.

Ahora falta saber cuánto cuesta. El coste total de un plan es la suma de los costes de cada acción:

$$C(\pi) = \sum_{i=1}^{n} c(s_{i-1}, a_i)$$

Símbolo	Significado	Ejemplo
$C(\pi)$	Coste total del plan $\pi$.	Kilómetros totales recorridos.
$c(s_{i-1}, a_i)$	Coste de ejecutar la acción $a_i$ desde el estado anterior.	$c(\text{Madrid}, \text{ir a Zaragoza}) = 315$ km.
$i$	Índice de la acción dentro del plan.	$i = 1$ para el primer tramo; $i = 2$ para el segundo.
$n$	Número de acciones del plan.	$n = 2$.

Con números:

$$C(\pi) = 315 + 300 = 615$$

Si existe otro plan Madrid → Valencia → Barcelona con coste $720$, ambos llegan a la meta, pero el primero es mejor. Una solución es óptima si minimiza $C(\pi)$ entre todas las soluciones posibles.

Esta formalización permite razonar sobre propiedades como la completitud (¿el algoritmo siempre encuentra solución si existe?), la optimalidad (¿encuentra la mejor?) y la complejidad (¿cuánto tarda y cuánta memoria consume en función del tamaño del problema?).¹²

Búsqueda no informada vs informada

Los algoritmos de búsqueda se dividen en dos familias, y la línea que las separa es la información disponible:

No informados (ciegos). No tienen ninguna pista sobre qué acciones son mejores. Solo conocen el coste de las acciones ya realizadas y la definición de la meta. Son como explorar un laberinto a oscuras, tanteando las paredes. BFS, DFS y coste uniforme pertenecen a esta familia. Su gran ventaja es que no necesitan conocimiento específico del dominio: funcionan para cualquier problema bien definido. Su gran desventaja es la ineficiencia: exploran a ciegas, sin priorizar.¹³

Informados (heurísticos). Disponen de una función heurística $h(n)$ que estima lo lejos que está un estado de la meta. Es una estimación diseñada para ser barata de calcular y suficientemente informativa para ordenar la búsqueda; no sustituye al coste real ni a la prueba de optimalidad. Greedy y A* usan heurísticas para priorizar estados prometedores. Su gran ventaja es la eficiencia: pueden encontrar soluciones explorando órdenes de magnitud menos estados. Su gran desventaja es que necesitan una buena heurística, y diseñar una heurística admisible —que nunca sobreestime el coste real— no siempre es fácil.¹⁴

El resto de este bloque de búsqueda se estructura alrededor de esta división: el capítulo 2 explora los algoritmos ciegos; el capítulo 3, los informados; y el capítulo 4 tiende el puente hacia los agentes modernos.

En el día a día

La búsqueda en espacios de estados no es una reliquia académica. Aparece en sistemas reales constantemente:

• Navegación GPS: encontrar una ruta útil entre dos puntos. Cada cruce puede modelarse como un estado. Cada calle es una acción con un coste, normalmente distancia, tiempo o una combinación de ambas. A* y sus variantes ayudan porque una heurística geométrica permite mirar antes las rutas prometedoras, aunque los sistemas reales añaden tráfico, restricciones de giro, cierres, peajes y optimizaciones de ingeniería.¹⁵
• Planificación logística: una empresa con 50 paquetes y 5 furgonetas. El espacio de estados es astronómico —combinatorio, con un factor de ramificación enorme— y sin embargo los algoritmos de búsqueda heurística encuentran soluciones casi óptimas en segundos. La diferencia entre una ruta óptima y una subóptima son miles de euros al mes en combustible.
• Agentes LLM: cuando un agente decide si llamar a search_database o a check_calendar, podemos leer esa decisión como una evaluación de acciones en un espacio de estados implícito. El LLM puede actuar como heurística: «dado el contexto actual, ¿qué herramienta parece más prometedora?». El sistema alrededor debe añadir costes, permisos, observación y criterio de parada.

Antes del algoritmo: auditar el modelo

Un error muy común es discutir si usar BFS, A* o una heurística sofisticada antes de haber comprobado que el problema está bien definido. En ingeniería, el primer paso no es elegir algoritmo: es validar el contrato de búsqueda.

Pregunta	Qué comprueba	Fallo típico
¿$s_0$ pertenece a $S$?	Que el estado inicial existe en el modelo.	Arrancar desde un identificador que no está en el grafo.
¿$G \subseteq S$?	Que todas las metas son estados válidos.	Definir como meta una etiqueta textual que ninguna transición alcanza.
¿Toda acción tiene origen, destino y coste?	Que $f(s,a)$ y $c(s,a)$ están definidos.	Acción sin coste o transición a estado inexistente.
¿Los costes son no negativos?	Que UCS y A* puedan razonar correctamente.	Costes negativos que rompen garantías de optimalidad.
¿Hay ciclos?	Que el algoritmo necesitará visitados.	Madrid → Zaragoza → Madrid repitiéndose para siempre.
¿Cuál es $b$ y hasta qué profundidad buscarías?	Estimación de explosión combinatoria.	Descubrir tarde que $b^d$ no cabe en memoria.

Esta auditoría parece humilde, pero es exactamente el tipo de trabajo que evita sistemas frágiles. Si el contrato está mal, el algoritmo puede estar perfectamente implementado y aun así devolver basura.

Un plan candidato también se puede comprobar antes de hablar de optimalidad:

$$\text{válido}(\pi) \Leftrightarrow s_0 \xrightarrow{a_1} s_1 \xrightarrow{a_2} \cdots \xrightarrow{a_n} s_n \land s_n \in G$$

Y su coste se compara con otros planes:

$$C(\pi) = \sum_{i=1}^{n} c(s_{i-1}, a_i)$$

Una práctica útil es mantener en tus sistemas una salida trazable: qué estados se recorrieron, qué acción llevó a cada estado, qué coste se acumuló y por qué el plan termina o no en meta. Eso conecta este capítulo con planificación, agentes y evaluación: no basta con “llegó”; hay que poder explicar cómo.

Por qué debería importarte

La búsqueda es el paradigma más antiguo de la IA y, paradójicamente, uno de los más vigentes. No ha sido sustituido por el deep learning: ha sido aumentado por él. Los LLMs no reemplazan la búsqueda; la hacen más inteligente, proporcionando heurísticas donde antes había que diseñarlas a mano.

Entender la búsqueda te da un marco mental para razonar sobre problemas secuenciales: aquellos donde la solución no es una respuesta única, sino una secuencia de decisiones. Y te prepara para los capítulos siguientes: sin entender el vocabulario de estados, acciones y fronteras, no puedes entender CSP, planificación ni juegos. Todo el facsímil 2 se construye sobre este capítulo.

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Confundir el grafo de estados con el árbol de búsqueda	El grafo es el mapa completo; el árbol es lo que el algoritmo explora. Tratar el árbol como si fuera el grafo lleva a reexplorar estados innecesariamente y a no detectar ciclos.	Mantén un conjunto visited y nunca reexpandas un estado ya visitado. Es la optimización más rentable en búsqueda.
No definir bien el estado	Si el estado no contiene toda la información necesaria para decidir la siguiente acción, el algoritmo tomará decisiones basadas en información incompleta.	Pregúntate: «con esta información, ¿puedo generar todas las acciones posibles y evaluar si he llegado a la meta?». Si la respuesta es no, tu estado está incompleto.
Subestimar la explosión combinatoria	Un espacio con b=10 y d=10 tiene 10^10 estados. Explorarlos todos es inviable en cualquier hardware. La búsqueda ciega solo funciona para espacios pequeños.	Calcula b y d antes de elegir algoritmo. Si b^d es mayor que unos pocos millones, necesitas una heurística o una poda.
Olvidar el coste	Sin coste, cualquier camino sirve. Con costes variables, el camino más corto en pasos no es necesariamente el más barato. BFS encuentra el primero; UCS encuentra el mejor.	Define el coste de cada acción. Si los costes no son uniformes, usa UCS o A*, no BFS.

Manos a la obra

La práctica real de este capítulo está en kit descargable. El kit valida un problema de rutas como tupla de búsqueda, calcula factor de ramificación, detecta ciclos, estima explosión combinatoria y evalúa planes candidatos.

# Descomprime el ZIP del capítulo y ejecuta estos comandos dentro de esa carpeta
python3 ops/audit_search_problem.py --write
cat output/search_model_decision.md

Qué deberías ver. El informe distingue tres cosas: si el modelo del problema es válido, qué planes candidatos llegan a meta y qué coste tiene cada uno. También marca por qué un plan puede ser inválido: acción inexistente, transición imposible o final fuera de $G$.

Archivo	Papel
data/search_problem.json	Estados, acciones, estado inicial, metas y planes candidatos.
contracts/search_policy.json	Umbrales de explosión combinatoria y reglas de validación.
ops/audit_search_problem.py	Auditor ejecutable sin dependencias externas.
output/search_model_report.json	Resultado estructurado para revisar o automatizar.
output/search_model_decision.md	Informe legible para entregar.

Cómo lo adaptas a tu caso. Cambia las ciudades por estados de un flujo real: pasos de onboarding, estados de un pedido, pantallas de una app, acciones de un agente o rutas de logística. Después añade dos planes: uno que llegue a meta y otro que falle. La entrega interesante no es que el plan “funcione”: es que puedas explicar por qué funciona.

Puedes complementar el kit con recursos visuales:

• Pathfinding visualizer: dibuja obstáculos, elige BFS, DFS o A* y observa cómo cada algoritmo explora el espacio de estados de forma radicalmente distinta. La diferencia visual entre BFS (explora en ondas concéntricas) y DFS (se lanza por un camino hasta el fondo) es imposible de transmitir solo con texto.
• Ejercicio mental: modela el problema de «ir de tu casa al trabajo» como un espacio de estados. Define el estado, las acciones, la meta y el coste. ¿Cuál es el factor de ramificación aproximado? ¿Qué profundidad tiene una solución típica? ¿Qué algoritmo usarías?

Qué entregaría un alumno. El Markdown generado, una versión propia de search_problem.json, un plan válido, un plan inválido explicado y una estimación honesta de si el espacio de búsqueda es pequeño, manejable o explosivo.

Cómo encaja todo

Este mapa se lee de izquierda a derecha: primero defines el problema, después eliges cómo gestionar la frontera, y solo entonces aparecen las garantías de completitud, optimalidad y coste. Los capítulos siguientes cambian la política de frontera, añaden heurísticas o convierten estados en asignaciones, planes y decisiones con otros actores.

La conexión con sistemas modernos no es decorativa: un agente con herramientas también necesita estado, acciones, coste, meta y trazabilidad. Cambia la forma de representar el problema, pero no desaparece el patrón.

graph TD
    subgraph "Capítulo 1: Fundamentos de búsqueda"
        direction TB
        PROBLEMA["Problema = (S, A, f, s₀, G, c)"]
        S_ESPACIO["S: espacio de estados<br/>finito o infinito, discreto o continuo"]
        A_ACCIONES["A(s): acciones aplicables en s<br/>f: S × A → S (función de transición)"]
        S0_INICIAL["s₀ ∈ S: estado inicial"]
        G_META["G ⊆ S: conjunto de estados meta"]
        C_COSTE["c: S × A → ℝ⁺: función de coste"]
        SOLUCION["Solución: secuencia (a₁,…,aₙ) tal que<br/>s₀ →^a₁ s₁ →^a₂ … →^aₙ sₙ ∈ G"]
        OPTIMA["Solución óptima: minimiza Σ c(sᵢ, aᵢ₊₁)"]
    end
    subgraph "Propiedades formales"
        COMPLETITUD[Completitud: ¿encuentra solución si existe?]
        OPTIMALIDAD[Optimalidad: ¿encuentra la de menor coste?]
        COMPLEJIDAD["Complejidad: O(b^d) tiempo, O(b·d) espacio"]
        ADMISIBILIDAD["Admisibilidad: h(s) ≤ h*(s) ∀s"]
    end
    subgraph "Frontera: el núcleo algorítmico"
        FRONTERA[Frontera: estados descubiertos, no expandidos]
        COLA["Cola FIFO → BFS: O(b^d)"]
        PILA["Pila LIFO → DFS: O(b·d)"]
        PRIORIDAD["Cola prioridad por g → UCS"]
        HEURISTICA["Cola prioridad por g+h → A*"]
    end
    subgraph "Conexiones en el facsímil 2"
        CSP["CSP: variables + restricciones<br/>la búsqueda con backtracking"]
        PLANIFICACION["Planificación: PDDL<br/>acciones con precondiciones y efectos"]
        JUEGOS["Juegos: minimax, MCTS<br/>búsqueda con otros actores"]
    end
    subgraph "Conexiones modernas"
        AGENTES_LLM["Agentes LLM: búsqueda implícita<br/>el modelo como heurística aprendida"]
        RAG["RAG: retrieval = búsqueda<br/>en espacio de documentos"]
    end

    PROBLEMA --> S_ESPACIO
    PROBLEMA --> A_ACCIONES
    PROBLEMA --> S0_INICIAL
    PROBLEMA --> G_META
    PROBLEMA --> C_COSTE
    S_ESPACIO --> SOLUCION
    A_ACCIONES --> SOLUCION
    S0_INICIAL --> SOLUCION
    G_META --> SOLUCION
    SOLUCION --> OPTIMA
    C_COSTE --> OPTIMA
    SOLUCION -->|"se encuentra mediante"| FRONTERA
    FRONTERA -->|"implementada como"| COLA
    FRONTERA -->|"implementada como"| PILA
    FRONTERA -->|"implementada como"| PRIORIDAD
    FRONTERA -->|"implementada como"| HEURISTICA
    COLA -->|"garantiza"| COMPLETITUD
    PRIORIDAD -->|"garantiza"| OPTIMALIDAD
    HEURISTICA -->|"con h admisible"| OPTIMALIDAD
    HEURISTICA -->|"requiere"| ADMISIBILIDAD
    COLA -->|"complejidad"| COMPLEJIDAD
    PILA -->|"complejidad"| COMPLEJIDAD
    COMPLETITUD -->|"hereda"| CSP
    OPTIMALIDAD -->|"extiende a"| PLANIFICACION
    FRONTERA -->|"fundamento de"| JUEGOS
    HEURISTICA -->|"inspira"| AGENTES_LLM
    COLA -->|"análogo a"| RAG

    style PROBLEMA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style FRONTERA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style HEURISTICA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style CSP stroke-dasharray: 5 5
    style PLANIFICACION stroke-dasharray: 5 5
    style JUEGOS stroke-dasharray: 5 5
    style AGENTES_LLM stroke-dasharray: 5 5
    style RAG stroke-dasharray: 5 5

Vocabulario aprendido

Término	Definición
Estado	Descripción suficiente de la situación actual del problema en un momento dado.
Espacio de estados	Conjunto de todas las configuraciones posibles que puede alcanzar el problema.
Árbol de búsqueda	Estructura que el algoritmo construye al explorar, donde cada nodo es un estado y cada rama una acción.
Frontera	Conjunto de estados descubiertos pero aún no explorados. Su estructura determina el algoritmo.
Factor de ramificación	Número medio de acciones disponibles en cada estado. Determina la explosión combinatoria.
Heurística	Función que estima la distancia de un estado a la meta, guiando la búsqueda informada.
Contrato de búsqueda	Definición verificable de estados, acciones, transición, estado inicial, metas y costes.
Plan candidato	Secuencia de acciones que debe poder ejecutarse desde $s_0$ y terminar en $G$ para ser solución.
Estado visitado	Estado ya revisado para evitar ciclos y reexpansiones innecesarias.

Antes de pasar página

• ¿Puedo definir los cuatro ingredientes de un problema de búsqueda y poner un ejemplo concreto de cada uno? (Si no, vuelve a «El vocabulario de la búsqueda».)
• ¿Entiendo por qué la explosión combinatoria hace que la búsqueda ciega sea inviable para espacios grandes? (Si no, vuelve a «La explosión combinatoria».)
• ¿Sé diferenciar el grafo de estados del árbol de búsqueda y explicar por qué importa la diferencia? (Si no, vuelve a «Árbol de búsqueda vs grafo de estados».)
• ¿Puedo explicar el bucle genérico de un algoritmo de búsqueda? (Si no, vuelve a «Cómo funciona un algoritmo de búsqueda».)
• ¿Entiendo la diferencia entre búsqueda no informada e informada? (Si no, vuelve a «Búsqueda no informada vs informada».)
• ¿Puedo auditar si un problema está bien definido antes de elegir algoritmo? (Si no, vuelve a «Antes del algoritmo: auditar el modelo».)
• ¿He ejecutado kit descargable y puedo explicar un plan válido y uno inválido? (Si no, vuelve a «Manos a la obra».)

En resumen

Idea fuerza	Detalle
Todo problema de búsqueda se define con estados, acciones, meta y coste.	Si no puedes definir estos cuatro elementos, no tienes un problema de búsqueda. Si tu estado contiene información irrelevante, tu espacio de búsqueda explota innecesariamente.
La explosión combinatoria es el obstáculo central.	El espacio crece exponencialmente con la profundidad. Más hardware ayuda poco si el modelo explora ramas inútiles. La defensa es modelar mejor, podar, usar heurísticas y medir costes.
La frontera es el corazón del algoritmo.	Qué estado extraes de la frontera determina si estás haciendo BFS, DFS, UCS o A*. Todo lo demás es el mismo bucle.
El contrato del problema va antes del algoritmo.	Si estados, acciones, transición, meta o coste están mal definidos, ningún algoritmo arregla el modelo.
La búsqueda no ha muerto: ha evolucionado.	Los LLMs no reemplazan la búsqueda; pueden aportar heurísticas aprendidas dentro de sistemas con estado, acciones, validación y trazas. El patrón viene de la IA clásica.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Newell, A., Shaw, J. C. y Simon, H. A. (1959). Report on a general problem-solving program. En Proceedings of the International Conference on Information Processing (pp. 256-264). UNESCO.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Newell, A., Shaw, J. C. y Simon, H. A. (1959). Report on a general problem-solving program. En Proceedings of the International Conference on Information Processing (pp. 256-264). UNESCO. ↩

2. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. Los capítulos 3 y 4 abordan la resolución de problemas mediante búsqueda, estableciendo el marco conceptual de estados, acciones, metas y costes que sigue siendo la base de la IA moderna. ↩

3. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta los fundamentos de la búsqueda en espacios de estados, incluyendo la distinción entre búsqueda ciega y búsqueda heurística. ↩

4. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. El capítulo 2 describe cómo modelar problemas como espacios de estados, enfatizando la importancia de definir correctamente las precondiciones de cada acción. ↩

5. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. La sección 3.3 analiza cómo definir metas verificables y su papel en la terminación correcta de los algoritmos de búsqueda. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. El capítulo 3 desarrolla la distinción entre búsqueda de cualquier solución y búsqueda de la solución óptima, y cómo el coste transforma el problema. ↩

7. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.3 introduce el concepto de complejidad de la búsqueda y analiza cómo el factor de ramificación y la profundidad determinan la viabilidad de los algoritmos. ↩

8. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.3 detalla la diferencia entre el grafo de estados y el árbol de búsqueda. ↩

9. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. El capítulo 3 aborda la detección de ciclos como una optimización crítica para la viabilidad práctica de los algoritmos de búsqueda. ↩

10. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta un marco unificado donde la única diferencia entre algoritmos es la política de extracción de la frontera. ↩

11. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.1 introduce la definición formal del problema de búsqueda, incluyendo la notación de espacios de estados, función de transición, y función de coste. ↩

12. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 2 formaliza las propiedades de los algoritmos de búsqueda en términos de completitud, admisibilidad y optimalidad. ↩

13. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.4 clasifica los algoritmos de búsqueda no informada y analiza sus propiedades de completitud, optimalidad y complejidad. ↩

14. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl estableció las bases teóricas de la búsqueda heurística, incluyendo las propiedades de admisibilidad y consistencia que garantizan la optimalidad de A*, y el concepto de poder heurístico que permite comparar la eficiencia de distintas heurísticas. ↩

15. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. ↩

Capítulo 02: BFS, DFS y coste uniforme: los algoritmos ciegos

Entrando en el tema

En el capítulo anterior definiste el problema: estados, acciones, meta y coste. Construiste el vocabulario. Ahora necesitas algoritmos que resuelvan ese problema sin pistas del dominio y sin función heurística. A ciegas.

Tres algoritmos compiten por el título de «mejor búsqueda ciega». Los tres usan exactamente el mismo bucle —extraer, comprobar, expandir, añadir—. La única diferencia entre ellos es la estructura de datos de la frontera.¹ Una cola produce BFS. Una pila produce DFS. Una cola de prioridad produce UCS. El resto es el mismo código.

Este capítulo desmenuza los tres. Con pseudocódigo. Con análisis de complejidad. Con ejemplos trazados paso a paso. Porque si no entiendes por qué BFS consume memoria exponencial y DFS puede perderse para siempre, no entenderás por qué A* —el algoritmo del próximo capítulo— fue una revolución.

El bucle genérico

Antes de entrar en cada algoritmo, fijemos el pseudocódigo común.² Los tres algoritmos ejecutan exactamente esto:

función BÚSQUEDA(problema):
    frontera ← [s₀]                    // estructura depende del algoritmo
    visitados ← {s₀}
    
    mientras frontera no esté vacía:
        s ← EXTRAER(frontera)          // ← aquí está toda la diferencia
        si ES-META(s):
            return RECONSTRUIR-CAMINO(s)
        para cada acción a en A(s):
            s' ← f(s, a)
            si s' ∉ visitados:
                visitados ← visitados ∪ {s'}
                AÑADIR(frontera, s')
    
    return FRACASO

La línea s ← EXTRAER(frontera) es la única que cambia entre algoritmos.³ En BFS, EXTRAER es dequeue (el primero que entró). En DFS, es pop (el último que entró). En UCS, es extract-min (el de menor coste). Tres implementaciones. Tres comportamientos radicalmente distintos.

La forma matemática de decirlo es: en cada iteración elegimos un nodo de la frontera según una política $\pi$:

$$n_t = \operatorname{extraer}_{\pi}(F_t)$$

Símbolo	Significado	Ejemplo
$F_t$	Frontera en el instante $t$: nodos descubiertos pero no expandidos.	$[B, C, D]$.
$n_t$	Nodo elegido para expandir en la iteración $t$.	En BFS sería $B$; en DFS podría ser $D$.
$\pi$	Política de extracción de la frontera.	FIFO, LIFO o menor coste $g(n)$.
$\operatorname{extraer}_{\pi}$	Operación que aplica esa política.	dequeue, pop o extract-min.

Y el resto del bucle actualiza frontera y visitados:

$$F_{t+1} = \left(F_t \setminus \{n_t\}\right) \cup \left(\operatorname{Succ}(n_t) \setminus V_t\right)$$

Símbolo	Significado	Ejemplo
$\operatorname{Succ}(n_t)$	Sucesores generados al expandir $n_t$.	Si $n_t=B$, quizá $\{D,E\}$.
$V_t$	Estados ya visitados antes de la iteración $t$.	$\{A,B\}$.
$\setminus$	Diferencia de conjuntos: quitar elementos ya presentes.	No reañadir estados visitados.

Así que los tres algoritmos se reducen a tres políticas:

$$\pi_{\text{BFS}} = \text{FIFO}, \qquad \pi_{\text{DFS}} = \text{LIFO}, \qquad \pi_{\text{UCS}}(n) = \arg\min_{n \in F} g(n)$$

BFS: explorar por niveles

Algoritmo

BFS usa una cola (FIFO: first in, first out). Cuando expandimos un estado a profundidad $d$, sus sucesores se añaden al final de la cola, detrás de todos los estados de profundidad $d$ que aún no se han expandido. El resultado es una exploración por niveles concéntricos.⁴

Frontera: [A]           → dequeue A, enqueue(B, C)
Frontera: [B, C]        → dequeue B, enqueue(D, E)
Frontera: [C, D, E]     → dequeue C, enqueue(F)
Frontera: [D, E, F]     → ...

Propiedades formales

Para un espacio de búsqueda con factor de ramificación $b$ y profundidad de la solución más superficial $d$:⁵

Propiedad	Valor	Explicación
Completitud	Sí (si $b$ es finito)	Si existe solución, BFS la encuentra porque explora sistemáticamente todos los nodos por niveles.
Optimalidad	Sí (si coste = 1)	BFS encuentra el camino con menos pasos porque el primer nodo meta que descubre está a la profundidad mínima.
Tiempo	$O(b^d)$	En el peor caso, explora todos los nodos hasta profundidad $d$. Con $b=10, d=10$: $10^{10}$ expansiones.
Espacio	$O(b^d)$	Almacena todos los nodos del nivel actual en la frontera. Este es su talón de Aquiles.

El conteo de nodos de BFS sale de la suma de niveles del árbol:

$$N_{\text{BFS}}(d) = \sum_{i=0}^{d} b^i = \frac{b^{d+1}-1}{b-1}$$

Símbolo	Significado	Ejemplo
$N_{\text{BFS}}(d)$	Nodos generados hasta profundidad $d$.	Si $d=6$, todos los niveles de 0 a 6.
$b$	Factor de ramificación medio.	$b=10$.
$d$	Profundidad de la solución más superficial.	$d=6$.
$i$	Nivel del árbol de búsqueda.	$i=0$ es el estado inicial.

Con $b=10$ y $d=6$:

$$N_{\text{BFS}}(6) = 1 + 10 + 10^2 + 10^3 + 10^4 + 10^5 + 10^6 = 1\,111\,111$$

La memoria se aproxima por el tamaño del nivel más profundo que queda en la frontera:

$$M_{\text{BFS}}(d) \approx b^d$$

Con $b=10$ y $d=12$, BFS puede necesitar almacenar alrededor de $10^{12}$ nodos. A 1 KB por nodo, eso ronda $10^{15}$ bytes: aproximadamente 1 PB, no “un ordenador grande”. Imposible para la mayoría de problemas reales.⁶

DFS: lanzarse en profundidad

Algoritmo

DFS usa una pila (LIFO: last in, first out). Cuando expandimos un estado, sus sucesores se colocan en el tope de la pila, y el algoritmo explora inmediatamente el que queda arriba. El resultado es una inmersión profunda por la primera rama disponible.⁷

Convención: el tope de la pila está a la izquierda.

Frontera: [A]           → pop A, push(C), push(B)
Frontera: [B, C]        → pop B (tope de la pila), push(E), push(D)
Frontera: [D, E, C]     → pop D
Frontera: [E, C]        → ...

DFS es inherentemente recursivo. De hecho, la implementación más natural de DFS es recursiva, sin frontera explícita:

función DFS-RECURSIVO(s, visitados):
    si ES-META(s): return s
    visitados ← visitados ∪ {s}
    para cada acción a en A(s):
        s' ← f(s, a)
        si s' ∉ visitados:
            resultado ← DFS-RECURSIVO(s', visitados)
            si resultado ≠ FRACASO: return resultado
    return FRACASO

La pila de llamadas de la recursión es la frontera. Cada llamada anidada es un paso más en profundidad.⁸

Propiedades formales

Propiedad	Valor	Explicación
Completitud	No (sin límite)	En espacios infinitos, DFS puede perderse por una rama infinita sin retroceder nunca. Con límite de profundidad, es completo.
Optimalidad	No	Encuentra el primer camino, no el más corto. Puede devolver uno de 50 pasos cuando existe uno de 3.
Tiempo	$O(b^m)$	$m$ es la profundidad máxima. Peor que BFS si $m \gg d$.
Espacio	$O(b \cdot m)$	Solo almacena el camino actual y sus hermanos no explorados. Esta es su gran ventaja.

La diferencia entre tiempo y memoria se ve mejor separando las dos fórmulas:

$$T_{\text{DFS}}(m) = O(b^m)$$ $$M_{\text{DFS}}(m) = O(b \cdot m)$$

Símbolo	Significado	Ejemplo
$T_{\text{DFS}}(m)$	Trabajo máximo si DFS baja hasta profundidad $m$.	Puede ser enorme si la rama mala es muy profunda.
$M_{\text{DFS}}(m)$	Memoria necesaria para camino actual y alternativas pendientes.	Con $b=10, m=20$, unos $200$ nodos.
$m$	Profundidad máxima explorada.	$m=20$.

La ventaja de memoria de DFS es dramática. Con $b=10, m=20$, DFS mantiene del orden de:

$$b \cdot m = 10 \cdot 20 = 200$$

nodos de memoria. BFS para una frontera comparable podría necesitar $10^{20}$ nodos. DFS es el único algoritmo viable para espacios profundos sin heurística, pero esa frugalidad se paga con ausencia de optimalidad y riesgo de perderse.⁹

IDS: lo mejor de dos mundos

El Iterative Deepening Search (IDS) combina la optimalidad de BFS con la memoria de DFS.¹⁰ La idea es simple: ejecuta DFS con límite de profundidad $L = 0, 1, 2, \ldots$ hasta encontrar la solución:

función IDS(problema):
    para L = 0, 1, 2, ... hasta ∞:
        resultado ← DFS-LIMITADO(s₀, L)
        si resultado ≠ FRACASO: return resultado

Parece ineficiente —cada iteración reexplora los niveles anteriores—, pero el coste de la reexploración es sorprendentemente bajo: los niveles profundos dominan el coste total. El número aproximado de nodos expandidos por IDS hasta profundidad $d$ es:

$$N_{\text{IDS}}(d) = \sum_{\ell=0}^{d} (d-\ell+1)b^\ell$$

Símbolo	Significado	Ejemplo
$\ell$	Nivel del árbol que se reexplora en varias iteraciones.	El nivel 0 se toca $d+1$ veces.
$d-\ell+1$	Número de veces que IDS vuelve a visitar el nivel $\ell$.	Si $d=3$, el nivel 1 se visita 3 veces.
$b^\ell$	Nodos aproximados del nivel $\ell$.	Con $b=10$, el nivel 3 tiene $1\,000$ nodos.

Comparado con BFS:

$$\frac{N_{\text{IDS}}}{N_{\text{BFS}}} \approx \frac{b}{b-1}$$

Para $b=10$:

$$\frac{10}{9} \approx 1.11$$

IDS explora aproximadamente un 11 % más de nodos que BFS, pero con un consumo de memoria $O(b \cdot d)$ en lugar de $O(b^d)$.¹¹ Es el algoritmo preferido cuando el espacio de búsqueda es grande, la profundidad de la solución es desconocida y no hay heurística disponible.

UCS: cuando cada paso cuesta distinto

BFS asume que todos los pasos cuestan lo mismo. Pero en el mundo real, un paso puede costar 5 y otro 500. BFS encuentra el camino con menos pasos, no el más barato.

UCS generaliza BFS reemplazando la cola por una cola de prioridad ordenada por $g(n)$, el coste acumulado desde el estado inicial hasta $n$.¹² En cada paso, UCS expande el nodo con menor $g(n)$:

$$g(n) = \sum_{i=1}^{k} c(s_{i-1}, a_i)$$

Símbolo	Significado	Ejemplo
$g(n)$	Coste acumulado desde el estado inicial hasta el nodo $n$.	Llegar a $D$ cuesta 7.
$c(s_{i-1}, a_i)$	Coste de aplicar la acción $a_i$ desde el estado anterior.	Una carretera de 5 km o una acción con coste 5.
$k$	Número de acciones del camino hasta $n$.	Tres movimientos: $k=3$.
$s_0 \to s_1 \to \ldots \to s_k$	Secuencia de estados recorrida hasta llegar a $n$.	$A \to C \to D$.

La política de extracción queda así:

$$n_t = \arg\min_{n \in F_t} g(n)$$

Si dos caminos llegan al mismo estado, UCS conserva el de menor coste:

$$g_{\text{nuevo}}(s') = g(n_t) + c(n_t, a)$$ $$g(s') \leftarrow \min\left(g(s'), g_{\text{nuevo}}(s')\right)$$

Símbolo	Significado	Ejemplo
$n_t$	Nodo extraído de la frontera en la iteración $t$.	$C$, porque $g(C)=2$.
$F_t$	Frontera ordenada por coste acumulado.	$[(C,2), (B,5)]$.
$g_{\text{nuevo}}(s')$	Coste candidato para llegar a un sucesor.	Si $g(C)=2$ y $c(C,D)=5$, entonces $g_{\text{nuevo}}(D)=7$.
$\min$	Operación que se queda con el camino más barato conocido.	Si ya había $D=9$, se reemplaza por $D=7$.

Ejemplo concreto:

Frontera: [(A, g=0)]            → extraer A, añadir B(g=5), C(g=2)
Frontera: [(C, g=2), (B, g=5)]  → extraer C (menor coste), añadir D(g=7)
Frontera: [(B, g=5), (D, g=7)]  → extraer B, añadir E(g=11)

Observa que B se descubrió antes que C, pero C se expandió primero porque su coste acumulado era menor. UCS no discrimina por antigüedad: solo le importa el coste.

Propiedades formales

Propiedad	Valor	Condición
Completitud	Sí	Todos los costes $c(s,a) \geq \epsilon > 0$
Optimalidad	Sí	El primer nodo meta extraído es óptimo
Tiempo	$O(b^{1 + \lfloor C^*/\epsilon \rfloor})$	$C^*$ = coste solución óptima, $\epsilon$ = coste mínimo
Espacio	$O(b^{1 + \lfloor C^*/\epsilon \rfloor})$	Similar al tiempo en el peor caso

BFS es un caso especial de UCS donde $c(s,a) = 1$ para toda acción. En ese caso, $g(n) = \text{profundidad}(n)$ y UCS se comporta exactamente como BFS.¹³

Comparar búsquedas como ingeniero

Una comparación útil no se queda en “este algoritmo encuentra camino”. Debe registrar la traza de expansión y métricas mínimas. Si no las registras, no puedes explicar por qué BFS encontró una solución rápida pero cara, por qué DFS tuvo suerte o por qué UCS tardó más pero devolvió menor coste.

Métrica	Qué mide	Por qué importa
Estados expandidos	Cuántas veces sacaste un nodo de la frontera.	Aproxima trabajo computacional.
Estados generados	Cuántos sucesores se produjeron.	Mide cuánto crece el árbol aunque no todo se expanda.
Frontera máxima	Máximo tamaño de la frontera.	Aproxima presión de memoria.
Profundidad de solución	Número de acciones del camino devuelto.	BFS optimiza esto si los costes son uniformes.
Coste de solución	Suma de costes $g(n)$.	UCS optimiza esto si los costes son positivos.
Traza	Orden exacto de expansión.	Permite revisar empates, ciclos y decisiones de frontera.

También hay un detalle profesional que suele pasarse por alto: el desempate. Si dos nodos tienen el mismo coste, la implementación debe decidir cuál sale primero. Dos implementaciones correctas de UCS pueden expandir nodos en orden distinto si no fijan una regla estable de desempate. Para comparar runs, fija el orden de sucesores y el criterio de desempate.

Tabla comparativa

Algoritmo	Frontera	Completo	Óptimo	Tiempo	Espacio
BFS	Cola (FIFO)	Sí	Sí (costes = 1)	$O(b^d)$	$O(b^d)$
DFS	Pila (LIFO)	No (sin lím.)	No	$O(b^m)$	$O(b \cdot m)$
UCS	Cola prioridad ($g$)	Sí	Sí	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$	$O(b^{1+\lfloor C^*/\epsilon \rfloor})$
IDS	Pila (LIFO, repetido)	Sí	Sí (costes = 1)	$O(b^d)$	$O(b \cdot d)$

Donde $b$ = factor de ramificación, $d$ = profundidad de la solución más superficial, $m$ = profundidad máxima, $C^*$ = coste de la solución óptima, $\epsilon$ = coste mínimo de cualquier acción.

En el día a día

• BFS es la base del web crawling (explorar internet por niveles de enlaces), de los algoritmos de «seis grados de separación» en redes sociales, y de cualquier problema donde necesites garantizar el camino más corto en un grafo no ponderado.
• DFS aparece en analizadores sintácticos (recorrer el árbol de sintaxis en profundidad), en la resolución de laberintos con poca memoria, y como base del backtracking que veremos en el capítulo 7 sobre CSP. También es el algoritmo natural para generar permutaciones y combinaciones.
• UCS está en el corazón de los sistemas de navegación. Google Maps no usa BFS (las carreteras no miden todas lo mismo): usa UCS (o A*, que es UCS con heurística) para encontrar rutas óptimas en grafos con pesos.
• IDS es el algoritmo preferido en motores de ajedrez y otros juegos con espacio de búsqueda profundo y factor de ramificación alto, donde BFS se queda sin memoria y DFS sin garantías.

Por qué debería importarte

BFS, DFS y UCS no son algoritmos para memorizar: son patrones de diseño algorítmico. El patrón es «frontera + bucle». La elección de la estructura de datos para la frontera es la decisión de diseño que determina todas las propiedades del algoritmo resultante.

Este principio —una decisión de implementación aparentemente menor que determina propiedades asintóticas— es recurrente en informática. Y en IA, es la base sobre la que se construye A*: UCS con una heurística añadida a la prioridad. Si no entiendes por qué BFS explora por niveles y DFS se lanza en profundidad, no entenderás por qué A* es mejor que ambos.¹⁴

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Usar DFS sin límite en espacios infinitos	DFS se pierde por una rama infinita sin retroceder. El algoritmo nunca termina.	Usa IDS o establece un límite de profundidad basado en el conocimiento del dominio.
Asumir que BFS es siempre mejor que DFS	BFS garantiza optimalidad pero su consumo de memoria es exponencial. Para $b=10, d=15$, BFS necesita petabytes de RAM.	Evalúa $b$ y $d$ antes de elegir. Si $b^d$ supera la memoria disponible, usa IDS o DFS con límite.
Usar BFS con costes no uniformes	BFS optimiza el número de pasos, no el coste. Si las acciones tienen costes distintos, BFS no encuentra el camino óptimo.	Usa UCS. BFS es UCS con $c(s,a)=1$; fuera de ese caso, UCS es la herramienta correcta.
No detectar estados repetidos	Sin un conjunto visitados, los tres algoritmos pueden quedar atrapados en ciclos infinitos.	Mantén visitados y comprueba antes de añadir a la frontera. Es la optimización más rentable en búsqueda.

Manos a la obra

La práctica real está en kit descargable. Ejecuta BFS, DFS, UCS e IDS sobre el mismo grafo ponderado y genera un informe con camino, coste, profundidad, nodos expandidos, nodos generados, frontera máxima y traza.

# Descomprime el ZIP del capítulo y ejecuta estos comandos dentro de esa carpeta
python3 ops/compare_frontiers.py --write
cat output/frontier_decision.md

Qué deberías ver. BFS encuentra el camino con menos acciones, pero no necesariamente el más barato. UCS encuentra el menor coste porque ordena por $g(n)$. DFS puede encontrar una solución válida, pero depende mucho del orden de sucesores. IDS reexplora, pero mantiene memoria baja.

Archivo	Papel
data/weighted_graph.json	Grafo ponderado, estado inicial, meta y orden estable de sucesores.
contracts/frontier_policy.json	Límites y reglas de comparación.
ops/compare_frontiers.py	Implementación ejecutable sin dependencias externas.
output/frontier_report.json	Métricas estructuradas por algoritmo.
output/frontier_decision.md	Informe legible para revisión o entrega.

Cómo lo adaptas a tu caso. Cambia el grafo por un flujo real: navegación en una app, pasos de una herramienta, estados de un pedido o rutas de soporte. Mantén costes distintos para que BFS y UCS puedan diferir.

Qué entregaría un alumno. El Markdown generado, un grafo modificado, una explicación de por qué BFS no minimiza coste cuando los pesos cambian y una decisión técnica sobre qué política usaría según memoria, coste y garantías.

Cómo encaja todo

El capítulo anterior definió el contrato del problema. Este capítulo enseña que, una vez tienes estados y acciones, la decisión crítica es la política de frontera. Cambiar una cola por una pila o por una cola de prioridad cambia garantías, memoria y coste encontrado.

Esto prepara el salto al capítulo 3: A* no aparece de la nada. Es UCS con una estimación del coste restante. Primero entiendes $g(n)$; después podrás entender $g(n)+h(n)$.

graph TD
    subgraph "Capítulo 2: Algoritmos ciegos"
        GEN["Bucle genérico:<br/>extraer → comprobar → expandir → añadir"]
        FRONTERA["Frontera: núcleo del algoritmo"]
        COLA["Cola FIFO"]
        PILA["Pila LIFO"]
        CPRIOR["Cola prioridad por g(n)"]
    end
    subgraph "Propiedades formales"
        COMPLETITUD["Completitud: ¿siempre encuentra solución?"]
        OPTIMALIDAD["Optimalidad: ¿encuentra la mejor?"]
        COMPLEJIDAD["Complejidad: O(b^d) vs O(b·m)"]
    end
    subgraph "Algoritmos resultantes"
        BFS["BFS: completo, óptimo, O(b^d) espacio"]
        DFS["DFS: no completo, no óptimo, O(b·m) espacio"]
        UCS["UCS: completo, óptimo, generaliza BFS"]
        IDS["IDS: completo, óptimo, O(b·d) espacio"]
    end
    subgraph "Conexiones"
        CAP1["Espacio de estados (cap. 1)"]
        ASTAR["A* (cap. 3)"]
        BACKTRACK["Backtracking CSP (cap. 7)"]
    end

    GEN --> FRONTERA
    FRONTERA -->|"implementada con"| COLA
    FRONTERA -->|"implementada con"| PILA
    FRONTERA -->|"implementada con"| CPRIOR
    COLA -->|"produce"| BFS
    PILA -->|"produce"| DFS
    PILA -->|"con límites crecientes produce"| IDS
    CPRIOR -->|"produce"| UCS
    BFS -->|"garantiza"| COMPLETITUD
    BFS -->|"garantiza"| OPTIMALIDAD
    BFS -->|"tiene"| COMPLEJIDAD
    DFS -->|"tiene"| COMPLEJIDAD
    UCS -->|"garantiza"| OPTIMALIDAD
    CAP1 -.->|"define los"| GEN
    UCS -.->|"base de"| ASTAR
    DFS -.->|"base de"| BACKTRACK
    IDS -.->|"inspira"| ASTAR

    style CAP1 stroke-dasharray: 5 5
    style ASTAR stroke-dasharray: 5 5
    style BACKTRACK stroke-dasharray: 5 5
    style FRONTERA fill:#F5F5F5,stroke:#000000,stroke-width:2
    style UCS fill:#F5F5F5,stroke:#000000,stroke-width:2

Vocabulario aprendido

Término	Definición
BFS	Algoritmo de búsqueda por niveles con cola FIFO. Completo y óptimo para costes uniformes. $O(b^d)$ en tiempo y espacio.
DFS	Algoritmo de búsqueda en profundidad con pila LIFO. $O(b \cdot m)$ en espacio pero no es completo ni óptimo sin límite.
UCS	Algoritmo con cola de prioridad por $g(n)$. Generaliza BFS para costes no uniformes. Óptimo con costes positivos.
IDS	DFS repetido con límites crecientes. Combina optimalidad de BFS con bajo consumo de memoria de DFS.
Factor de ramificación ($b$)	Número medio de sucesores por estado. Determina la complejidad exponencial de la búsqueda.
Traza de expansión	Orden en el que el algoritmo extrae estados de la frontera. Permite auditar la búsqueda.
Frontera máxima	Tamaño máximo que alcanza la frontera durante la ejecución. Aproxima presión de memoria.
Coste acumulado	$g(n)$: suma de costes desde el estado inicial hasta el nodo actual.

Antes de pasar página

• ¿Puedo escribir el pseudocódigo del bucle genérico de búsqueda? (Si no, vuelve a «El bucle genérico».)
• ¿Sé qué estructura de datos usa la frontera en BFS, DFS y UCS? (Cola, pila, cola de prioridad.)
• ¿Puedo explicar las propiedades formales (completitud, optimalidad, complejidad) de cada algoritmo? (Si no, vuelve a las tablas de propiedades.)
• ¿Entiendo por qué IDS es preferible a BFS en espacios profundos? (Si no, vuelve a «IDS: lo mejor de dos mundos».)
• ¿He ejecutado kit descargable y puedo explicar camino, coste, expansiones y frontera máxima? (Si no, vuelve a «Manos a la obra».)

En resumen

Idea fuerza	Detalle
La frontera lo decide todo.	Una cola produce BFS. Una pila produce DFS. Una cola de prioridad por $g(n)$ produce UCS. El resto del bucle es idéntico.
BFS es óptimo en pasos pero devorador de memoria. DFS es frugal en memoria pero ni completo ni óptimo.	IDS combina lo mejor de ambos: optimalidad de BFS con memoria de DFS, a costa de reexplorar (~11 % más de nodos).
UCS es BFS generalizado: optimiza coste, no pasos.	Con costes uniformes, UCS = BFS. Con costes variables, solo UCS (o A*) garantiza optimalidad.
Una búsqueda seria deja traza.	Sin orden de expansión, frontera máxima y coste acumulado no puedes comparar algoritmos de forma profesional.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.4 demuestra que todos los algoritmos de búsqueda no informada comparten la misma estructura algorítmica y que su comportamiento queda completamente determinado por la política de extracción de la frontera. ↩

2. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 presenta el algoritmo genérico de búsqueda en grafos que unifica BFS, DFS y UCS. ↩

3. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. El capítulo 3 presenta este marco unificado y demuestra que encapsula toda la familia de algoritmos de búsqueda no informada. ↩

4. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. El capítulo 3 analiza BFS en detalle, incluyendo su implementación con cola y el análisis de complejidad. ↩

5. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. La sección 3.2 cuantifica el problema de memoria de BFS y motiva la necesidad de DFS e IDS. ↩

7. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

8. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. El capítulo 7 explica la equivalencia entre DFS con pila explícita y DFS recursivo, y analiza las implicaciones para el consumo de memoria. ↩

9. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. ↩

10. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. ↩

11. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

12. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136 ↩

13. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 2 demuestra formalmente que UCS es una generalización de BFS y que A* es a su vez una generalización de UCS. ↩

14. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 3 demuestra cómo A* emerge naturalmente de UCS al incorporar una heurística en la función de evaluación. ↩

Capítulo 03: Greedy, A* y heurísticas: buscar con estimaciones

Entrando en el tema

Hasta ahora has explorado a ciegas. BFS, DFS, UCS: algoritmos que no saben nada del problema salvo qué acciones existen y cuánto cuestan. Funcionan, pero son terriblemente ineficientes: exploran miles de estados que no llevan a ninguna parte.

Ahora imagina que tienes una estimación matemática barata. Una función $h(n)$ que, para cualquier estado $n$, estima cuánto falta para llegar a la meta. No es exacta —si lo fuera, ya habrías resuelto el problema—, pero es útil. Con esa estimación, puedes priorizar los estados que parecen más prometedores e ignorar los que se alejan. Puedes encontrar la solución explorando cientos de estados en vez de millones.

Esa función se llama heurística. Y los algoritmos que la usan —Greedy y A*— son piezas centrales de la búsqueda informada.¹ Sin heurísticas, muchos problemas de rutas, planificación y videojuegos tendrían que mirar demasiadas opciones antes de responder.

Greedy best-first: seguir solo la estimación

El algoritmo greedy best-first search es el más simple de los informados. Evalúa cada estado exclusivamente con la heurística $h(n)$ —la estimación de lo que falta hasta la meta— e ignora completamente el coste acumulado $g(n)$.²

Es como ir de Madrid a Berlín mirando exclusivamente la distancia en línea recta: «Barcelona está más cerca de Berlín que Lisboa, voy a Barcelona. París está más cerca que Roma, voy a París». Nunca mira hacia atrás. Nunca considera si el camino acumulado es bueno o si la ruta aparente esconde un desvío enorme.

Formalmente, Greedy usa esta función de evaluación:

$$f_{\text{Greedy}}(n) = h(n)$$

Y en cada iteración extrae de la frontera el nodo que parece más cercano a la meta:

$$n_t = \arg\min_{n \in F_t} h(n)$$

Símbolo	Significado	Ejemplo
$f_{\text{Greedy}}(n)$	Prioridad que Greedy asigna al nodo $n$.	Si $h(B)=3$, la prioridad de $B$ es 3.
$h(n)$	Estimación de coste desde $n$ hasta la meta.	Distancia Manhattan hasta la salida.
$F_t$	Frontera en la iteración $t$.	$\{B,C,D\}$.
$\arg\min$	Operación que devuelve el elemento con menor valor.	Si $h(C)=2$, Greedy elige $C$.

Mira el detalle peligroso: no aparece $g(n)$. Si llegar hasta $C$ ya te ha costado 40 pasos y llegar hasta $B$ solo 2, Greedy no lo ve. Solo pregunta: «¿cuál parece más cerca de la meta desde aquí?».

Ventaja: velocidad. Si $h(n)$ es razonablemente buena, Greedy encuentra una solución explorando muy pocos estados. En navegación con distancia euclídea, suele ir directo al destino.

Riesgo: no es ni completo ni óptimo. Puede quedarse atascado en un mínimo local, eligiendo repetidamente estados que parecen buenos según $h$ pero que no llevan a ninguna parte. Y el camino que encuentra rara vez es el mejor: la heurística puede empujarte hacia una montaña —porque en línea recta parece más corta— cuando el camino óptimo da un rodeo por el valle.³

En agentes LLM modernos, Greedy equivale a elegir la tool que parece obvia sin verificar restricciones: «¿cuál es la respuesta? Voy a buscar en la base de datos». Pero quizás antes necesitabas comprobar permisos. La heurística te empujó en una dirección que parecía correcta pero no lo era.

La tabla de propiedades queda así:

Propiedad	Valor	Por qué
Completitud	No en general	Puede entrar en ciclos o perseguir una rama infinita que parece prometedora.
Optimalidad	No	Ignora el coste acumulado $g(n)$.
Tiempo	$O(b^m)$ en el peor caso	Si la heurística engaña, puede explorar una rama profunda entera.
Espacio	$O(b^m)$ en el peor caso	Mantiene frontera y visitados como otros algoritmos de búsqueda en grafos.

A*: coste real + estimación

A* corrige el defecto fundamental de Greedy combinando dos piezas de información en una sola función de evaluación:⁴

$$f(n) = g(n) + h(n)$$

Símbolo	Significado	Cálculo
$f(n)$	Coste total estimado del camino óptimo que pasa por $n$	$g(n) + h(n)$
$g(n)$	Coste real acumulado desde el inicio hasta $n$	$\sum c(s_{i-1}, a_i)$
$h(n)$	Heurística: coste estimado desde $n$ hasta la meta	Específica del problema
$h^*(n)$	Coste real óptimo desde $n$ hasta la meta	Desconocido (es lo que buscamos)

$g(n)$ es lo que ya has pagado. $h(n)$ es lo que estimas que te queda. $f(n)$ es el total estimado. A* expande siempre el nodo con menor $f(n)$.⁵

La política de extracción de A* es:

$$n_t = \arg\min_{n \in F_t} \left(g(n) + h(n)\right)$$

Nodo	$g(n)$: coste ya pagado	$h(n)$: estimación restante	$f(n)=g(n)+h(n)$	Quién lo elegiría
$B$	8	2	10	Greedy, porque $h(B)$ es menor.
$C$	3	4	7	A*, porque $f(C)$ es menor.

Este ejemplo pequeño captura toda la diferencia. Greedy ve $2 < 4$ y elige $B$. A* ve $10 > 7$ y elige $C$, porque entiende que lo que ya has pagado también cuenta.

Esto resuelve el problema de Greedy. Si la heurística te empuja hacia un camino que parece corto pero es caro, $g(n)$ —el coste real acumulado— penaliza esa decisión. A* no solo mira lo prometedor: también penaliza los caminos que ya han costado demasiado.⁶

Propiedades formales de A*

Admisibilidad. Una heurística $h(n)$ es admisible si nunca sobreestima el coste real hasta la meta. Formalmente:

$$0 \leq h(n) \leq h^*(n)$$

Símbolo	Significado	Ejemplo
$h(n)$	Estimación que calculas rápido.	Distancia en línea recta: 12 km.
$h^*(n)$	Coste real óptimo desde $n$ hasta la meta.	Mejor carretera real: 15 km.
$0 \leq h(n)$	La heurística no puede ser negativa.	No tiene sentido decir “faltan -3 km”.
$h(n) \leq h^*(n)$	La heurística no promete más de lo que existe.	12 km no sobreestima 15 km.

La distancia en línea recta es admisible porque ningún camino por carreteras puede ser más corto que la línea recta. Una heurística que estime tiempos ignorando semáforos, cuestas o peajes puede dejar de ser admisible si promete rutas demasiado optimistas.⁷

Teorema de optimalidad. En búsqueda en árbol, si $h(n)$ es admisible, A* encuentra un camino de coste mínimo. En búsqueda en grafo, la garantía requiere además gestionar correctamente reaperturas de estados o trabajar con una heurística consistente. La demostración se basa en que A* no termina hasta haber descartado los nodos que podrían tener $f(n) < C^*$ (el coste óptimo) y, cuando encuentra la meta, su $f$ es igual a $g$ porque $h(\text{meta}) = 0$.

Consistencia (monotonicidad). Una propiedad más fuerte que la admisibilidad:

$$h(n) \leq c(n,a,n') + h(n')$$

Símbolo	Significado	Ejemplo
$c(n,a,n')$	Coste de ir de $n$ a $n'$ aplicando $a$.	Moverte una casilla cuesta 1.
$h(n)$	Estimación antes de moverte.	Faltan 8 pasos estimados.
$h(n')$	Estimación después de moverte.	Faltan 7 pasos estimados.

La lectura es sencilla: la estimación desde $n$ no puede ser mayor que «lo que cuesta dar un paso» más «lo que estimas desde el siguiente estado». Si $h$ es consistente, entonces $f(n)$ nunca baja a lo largo de un camino:

$$f(n') = g(n) + c(n,a,n') + h(n') \geq g(n) + h(n) = f(n)$$

Por eso A* con heurística consistente puede tratar los estados como cerrados la primera vez que los expande: no necesitará reabrirlos más tarde con un coste mejor.⁸

Heurísticas: el arte de saber qué ignorar

Una heurística es una función $h: S \to \mathbb{R}^+_0$ que, dado un estado, devuelve una estimación. Diseñar una buena heurística exige escoger información que aporte señal, sea barata de calcular y no rompa las garantías que quieres conservar.⁹

En una rejilla, dos heurísticas clásicas son:

$$h_{\text{Manhattan}}(n) = |x_n - x_{\text{meta}}| + |y_n - y_{\text{meta}}|$$ $$h_{\text{Euclidea}}(n) = \sqrt{(x_n - x_{\text{meta}})^2 + (y_n - y_{\text{meta}})^2}$$

Símbolo	Significado	Ejemplo
$x_n, y_n$	Coordenadas del estado actual.	$n=(2,3)$.
$x_{\text{meta}}, y_{\text{meta}}$	Coordenadas de la meta.	$\text{meta}=(7,6)$.
$	x_n-x_{\text{meta}}	$
$	y_n-y_{\text{meta}}	$

Con esos números:

$$h_{\text{Manhattan}}(n) = 5 + 3 = 8$$ $$h_{\text{Euclidea}}(n) = \sqrt{5^2 + 3^2} = \sqrt{34} \approx 5.83$$

Si solo puedes moverte en horizontal y vertical, Manhattan suele ser más informativa. Si puedes moverte en cualquier dirección, la euclídea encaja mejor.

Tipo	Ejemplo	Admisible	Informativa
Buena	Distancia euclídea en navegación	Sí	Alta
Aceptable	Distancia Manhattan en rejilla	Sí	Media
Mala	«Dificultad del examen = páginas del temario»	No	Baja
Engañosa	«Número de paquetes que faltan»	No	Engaña

La diferencia entre una heurística buena y una mala puede ser la diferencia entre explorar 100 estados y 100 000. Una heurística perfecta —$h(n) = h^*(n)$— haría que A* fuera directamente a la solución sin explorar nada más, pero calcular $h^*(n)$ es tan difícil como resolver el problema original. El arte está en aproximar $h^*(n)$ sin calcularla exactamente.

Una técnica clásica es relajar el problema: eliminar alguna restricción para crear una versión más fácil. La solución del problema relajado es una heurística admisible para el problema original.¹⁰ Por ejemplo, la distancia en línea recta es la solución al problema de navegación relajado donde ignoras los obstáculos y las carreteras.

También comparamos heurísticas por dominancia:

$$h_1 \succeq h_2 \quad \Longleftrightarrow \quad \forall n,\; h_1(n) \geq h_2(n)$$

siempre que ambas sigan siendo admisibles. Si $h_1$ domina a $h_2$, A* con $h_1$ no expande más nodos que A* con $h_2$. Dicho en castellano: cuanto más cerca esté $h(n)$ de $h^*(n)$ sin pasarse, menos trabajo hace A*.

Auditar una heurística antes de usarla

Una heurística no se acepta porque “suena razonable”. Se audita. Para problemas pequeños, puedes calcular $h^*(n)$, el coste óptimo real desde cada estado hasta la meta, y comparar.

Prueba	Fórmula	Qué detecta
No negatividad	$h(n)\geq0$	Estimaciones sin sentido.
Meta a cero	$h(\text{meta})=0$	Heurísticas que penalizan llegar.
Admisibilidad	$h(n)\leq h^*(n)$	Sobreestimaciones que rompen optimalidad de A*.
Consistencia	$h(n)\leq c(n,a,n')+h(n')$	Necesidad de reabrir nodos en grafos.
Dominancia	$h_1(n)\geq h_2(n)$ para todo $n$	Qué heurística informará más a A* sin perder garantías.

En producción no siempre puedes conocer $h^*(n)$; si pudieras, ya tendrías resuelto el problema. Pero en entornos pequeños, tests, mapas de juguete o fixtures, esta auditoría es oro: te permite validar que tu heurística no está metiendo una promesa falsa en el algoritmo.

También conviene medir el coste de calcular $h(n)$. Una heurística brillante pero carísima puede perder contra una heurística sencilla si cada evaluación tarda demasiado. A* no solo paga expansiones; también paga evaluaciones de heurística.

En el día a día

• GPS y navegación: A* con $h(n)$ = distancia euclídea es una simplificación útil para entender la idea. Los sistemas reales añaden datos de tráfico, restricciones de giro, jerarquías de carretera y cachés, pero el mecanismo permanece: una heurística buena reduce mucho el espacio que hay que mirar.
• Videojuegos: pathfinding de NPCs con A* y distancia Manhattan. Sin A*, los personajes se quedarían atascados contra las paredes.
• Agentes LLM: una decisión de tool puede modelarse como un paso de búsqueda. El LLM puede proponer qué herramienta parece más prometedora, pero el sistema debería añadir coste acumulado, riesgo, permisos y observación. Si penalizas caminos que ya han consumido demasiados tokens o llamadas caras, estás metiendo una idea parecida a $g(n)$ en el diseño.

Por qué debería importarte

A* es uno de los algoritmos centrales de la IA clásica: combina coste real y estimación futura de una forma sorprendentemente clara. La ecuación $f(n) = g(n) + h(n)$ resume décadas de investigación. Pero la lección más profunda no es memorizar el algoritmo: es aprender a diseñar heurísticas que ahorran búsqueda sin romper las garantías que necesitas.

Y este concepto trasciende la IA: en optimización, en diseño de algoritmos, en toma de decisiones, la habilidad de encontrar atajos informados que no comprometan la calidad de la solución es universal. A* formaliza esa tensión entre coste observado y estimación restante.

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Heurística no admisible con A*	Si $h(n)$ sobreestima el coste real, A* puede pasar de largo la solución óptima.	Verifica $0 \leq h(n) \leq h^*(n)$. La distancia euclídea y Manhattan son admisibles. Las heurísticas basadas en «coste medio» no lo son.
Confundir Greedy con A*	Greedy ignora $g(n)$: no garantiza optimalidad. A* usa $g(n) + h(n)$: sí la garantiza con $h$ admisible.	Usa A* si necesitas optimalidad. Greedy solo si necesitas una solución rápida y la calidad no es crítica.
Heurística demasiado cara de calcular	Evaluar $h(n)$ cuesta tiempo. Si calcular $h$ tarda más que expandir unos cientos de nodos extra con una heurística más simple, estás perdiendo eficiencia neta.	Mide el tiempo de $h(n)$. Si es más lento que expandir ~100 nodos, simplifica la heurística.

Manos a la obra

La práctica real está en kit descargable. Ejecuta UCS, Greedy, A*, A* con heurística nula y Weighted A* sobre el mismo grafo. Además audita heurísticas contra el coste óptimo real $h^*(n)$.

# Descomprime el ZIP del capítulo y ejecuta estos comandos dentro de esa carpeta
python3 ops/audit_heuristics.py --write
cat output/heuristic_decision.md

Qué deberías ver. La heurística nula convierte A* en UCS. Una heurística admisible y consistente conserva optimalidad y suele reducir expansiones. Greedy puede encontrar una solución rápida pero no tiene garantías. Weighted A* puede expandir menos, pero si $w>1$ ya no promete óptimo.

Archivo	Papel
data/heuristic_graph.json	Grafo ponderado y valores heurísticos candidatos.
contracts/heuristic_policy.json	Peso de Weighted A*, reglas de auditoría y límites de comparación.
ops/audit_heuristics.py	Auditor e implementaciones ejecutables sin dependencias externas.
output/heuristic_report.json	Resultados estructurados: admisibilidad, consistencia, dominancia y búsquedas.
output/heuristic_decision.md	Informe legible para entregar.

Cómo lo adaptas a tu caso. Cambia el grafo, añade una heurística nueva y mira si sigue siendo admisible. Después modifica el peso de Weighted A*. Si el coste baja o sube, explica por qué.

Qué entregaría un alumno. El Markdown generado, una heurística propia, una prueba de si es admisible/consistente y una comparación entre UCS, Greedy, A* y Weighted A*.

Cómo encaja todo

Este capítulo añade una pieza nueva a la frontera del capítulo 02: ya no ordenas solo por antigüedad o por coste real acumulado. Ahora introduces una estimación del futuro. Esa estimación puede ahorrar muchísimo trabajo, pero solo mantiene garantías si se comporta matemáticamente bien.

La idea seguirá viva en planificación, juegos y agentes: muchas decisiones inteligentes son una mezcla de coste pagado, coste esperado, riesgo y una función de evaluación.

graph TD
    subgraph "Capítulo 3: Búsqueda informada"
        FN["f(n) = g(n) + h(n)"]
        GREEDY["Greedy: solo h(n)"]
        ASTAR["A*: g(n) + h(n)"]
        ADM["Admisibilidad: 0 <= h(n) <= h*(n)"]
        CONS["Consistencia: h(n) <= c + h(n')"]
    end
    subgraph "Capítulos previos"
        UCS["UCS: f(n) = g(n) (cap. 2)"]
    end
    subgraph "Conexiones"
        PLAN["Planificación heurística (cap. 10)"]
        AGENTES["Agentes LLM (cap. 4, fasc. 5)"]
        JUEGOS["Juegos: evaluación heurística (cap. 11)"]
    end

    UCS -->|"añadir h(n)"| FN
    FN -->|"sin g(n)"| GREEDY
    FN -->|"con g(n) + h(n)"| ASTAR
    ASTAR -->|"requiere"| ADM
    CONS -->|"implica"| ADM
    ASTAR -->|"fundamento de"| PLAN
    GREEDY -->|"patron en"| AGENTES
    FN -->|"inspira evaluación en"| JUEGOS

    style UCS stroke-dasharray: 5 5
    style PLAN stroke-dasharray: 5 5
    style AGENTES stroke-dasharray: 5 5
    style JUEGOS stroke-dasharray: 5 5
    style FN fill:#F5F5F5,stroke:#000000,stroke-width:2

Vocabulario aprendido

Término	Definición
A*	$f(n)=g(n)+h(n)$. Óptimo si $h$ es admisible.
Heurística admisible	Nunca sobreestima: $0 \leq h(n) \leq h^*(n)$.
Greedy best-first	Solo $h(n)$. Rápido, no óptimo.
Consistencia	$h(n) \leq c(n,a,n') + h(n')$. Más fuerte que admisibilidad.
Relajación	Simplificar el problema para obtener una heurística admisible.
Dominancia heurística	Una heurística admisible domina a otra si estima siempre igual o más sin sobreestimar. Suele reducir expansiones.
Weighted A*	Variante $f(n)=g(n)+w h(n)$. Con $w>1$ puede ser más rápida, pero pierde optimalidad garantizada.

Antes de pasar página

• ¿Puedo escribir $f(n) = g(n) + h(n)$ y explicar cada término?
• ¿Entiendo qué significa que $h$ sea admisible?
• ¿Sé diferenciar Greedy de A*?
• ¿Puedo auditar una heurística con admisibilidad, consistencia y dominancia?
• ¿He ejecutado kit descargable y puedo explicar por qué Weighted A* puede perder optimalidad?

En resumen

Idea fuerza	Detalle
A* = UCS + heurística.	$g(n)$ garantiza optimalidad; $h(n)$ añade eficiencia.
Admisibilidad abre la puerta a la optimalidad.	$h(n) \leq h^*(n)$ es la condición suficiente que A* necesita en búsqueda en árbol; en grafos, la consistencia evita reexpansiones.
La heurística lo es todo.	De millones de estados a cientos. El arte está en el equilibrio entre precisión y coste.
Las heurísticas también se testean.	No basta con una estimación plausible: admisibilidad, consistencia, dominancia y coste de cálculo son parte del contrato.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl estableció las bases teóricas de la búsqueda heurística, formalizando conceptos como admisibilidad, consistencia y poder heurístico que permiten comparar rigurosamente distintas heurísticas. ↩

2. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.5 presenta greedy best-first como el primer algoritmo informado, destacando que su velocidad tiene como contrapartida la ausencia de garantías de optimalidad. ↩

3. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. La sección 8.2 analiza las limitaciones de Greedy y demuestra con ejemplos concretos por qué ignorar el coste del camino puede llevar a soluciones arbitrariamente malas. ↩

4. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. Este artículo presentó A* y demostró formalmente que, con heurística admisible, el algoritmo es óptimo y expande el mínimo número de nodos entre todos los algoritmos óptimos que usan la misma heurística. ↩

5. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

6. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. ↩

7. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. El capítulo 3 demuestra el teorema de optimalidad de A*: si $h$ es admisible, A* es óptimo en búsqueda en árbol. ↩

8. Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill. ↩

9. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. Pearl introdujo el concepto de poder heurístico: una heurística $h_1$ domina a $h_2$ si $h_1(n) \geq h_2(n)$ para todo $n$, y una heurística más informada produce una búsqueda más eficiente. ↩

10. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. La sección 3.6 explica cómo derivar heurísticas admisibles a partir de versiones relajadas del problema, siendo la distancia en línea recta el ejemplo canónico (ignorar obstáculos es la relajación). ↩

Capítulo 04: Búsqueda en agentes modernos y recapitulación

Entrando en el tema

Has aprendido a formular un problema como estados, acciones, meta y coste. Has visto qué ocurre cuando exploras a ciegas con BFS, DFS y UCS. Después has añadido estimaciones heurísticas con Greedy y A*. Ahora toca cerrar el bloque con una pregunta muy práctica: ¿por qué importa todo esto si hoy hablamos de LLMs, agentes y tools?

Porque muchas decisiones de un agente moderno pueden modelarse como decisiones en un espacio de posibilidades. Puede que no dibuje un árbol de búsqueda en pantalla. Puede que no tenga una cola de prioridad explícita llamada frontier. Pero cuando decide si debe leer un archivo, consultar una base de datos, llamar a una API, pedir aclaración o responder, está eligiendo una acción desde un estado, con costes, restricciones y una meta.¹

Este capítulo tiene dos trabajos. Primero, traducir la búsqueda clásica al lenguaje de los agentes actuales. Segundo, recapitular activamente los cuatro primeros capítulos del facsímil 2, igual que hicimos al cerrar el facsímil 1: concepto, recuerdo, ejemplo y punto exacto al que volver si algo no está asentado.

El agente como motor de búsqueda

Un agente LLM con herramientas puede leerse como un sistema de búsqueda que descubre el espacio mientras actúa.² La formulación mínima sería:

$$s_t = (m_t, o_t, r_t, q)$$

Símbolo	Significado	Ejemplo
$s_t$	Estado del agente en el instante $t$.	Lo que sabe después de dos llamadas a herramientas.
$m_t$	Memoria o historial disponible.	Mensajes previos, notas, resumen de contexto.
$o_t$	Observaciones recibidas del entorno.	Resultado de una búsqueda, salida de un test, respuesta de una API.
$r_t$	Restricciones activas.	Permisos, presupuesto de tokens, formato esperado.
$q$	Objetivo o pregunta que se intenta resolver.	“Encuentra por qué falla este test”.

Las acciones son las tools que puede ejecutar:

$$a_t \in A(s_t)$$

Símbolo	Significado	Ejemplo
$a_t$	Acción elegida en el paso $t$.	Leer un archivo, ejecutar un test, buscar documentación.
$A(s_t)$	Acciones disponibles desde el estado actual.	Si no hay red, “buscar online” no está disponible.

Después de actuar, el agente recibe una observación y actualiza su estado:

$$s_{t+1} = T(s_t, a_t, o_{t+1})$$

Esta es la lectura de búsqueda que nos interesa. El árbol no está escrito antes de empezar: aparece a medida que el agente actúa, observa y actualiza su estado.³

El mecanismo paso a paso

En búsqueda clásica, la frontera contiene nodos. En un agente, la frontera contiene siguientes acciones plausibles: “consultar docs”, “leer logs”, “ejecutar test”, “preguntar al usuario”, “responder ya”. Una política de extracción decide cuál probar primero.

Ejemplo de fórmula. Podemos escribir una versión operativa inspirada en la función de evaluación de A*. No es una ley universal de agentes ni un algoritmo estándar: es una plantilla de diseño para obligarnos a separar coste, avance esperado y riesgo antes de elegir una acción.

$$F(a \mid s_t) = G(a \mid s_t) + H(a \mid s_t) + R(a \mid s_t)$$

Símbolo	Significado	Ejemplo
$F(a \mid s_t)$	Prioridad total de una acción $a$ desde el estado actual.	Menor valor: acción más recomendable.
$G(a \mid s_t)$	Coste operativo esperado.	Tokens, latencia, dinero, complejidad.
$H(a \mid s_t)$	Estimación de distancia restante a la meta.	“Leer el error exacto probablemente acerca mucho”.
$R(a \mid s_t)$	Penalización por riesgo o incertidumbre.	Acción destructiva, datos sensibles, baja confianza.

Y la política de decisión sería:

$$a_t = \arg\min_{a \in A(s_t)} F(a \mid s_t)$$

Esto no significa que todos los agentes implementen literalmente esta ecuación. Significa que la ecuación te da un lenguaje para diseñarlos y auditar una política concreta. Los pesos, unidades y umbrales deben calibrarse con trazas reales: latencia, coste, errores, acciones bloqueadas y consecuencias. Un agente puramente Greedy minimiza solo $H$: elige lo que parece prometedor. Un agente más cuidadoso incluye $G$: evita gastar tokens y tiempo sin necesidad. Un agente robusto añade $R$: no ejecuta acciones arriesgadas solo porque parezcan útiles.⁴

Diseñar una política de agente que se pueda auditar

En ingeniería no basta con decir “el agente decide”. Una decisión de agente debería poder explicarse después: qué sabía, qué acciones podía ejecutar, cuáles estaban bloqueadas, qué coste esperaba pagar, qué riesgo aceptaba y por qué eligió una opción concreta. Si no puedes reconstruir esa historia, tienes una caja negra operativa.

Por eso conviene separar dos capas:

$$E(a \mid s_t) \in \{0,1\}$$ $$a_t = \arg\min_{a \in A(s_t),\; E(a \mid s_t)=1} F(a \mid s_t)$$

Capa	Pregunta	Ejemplo
Elegibilidad $E(a \mid s_t)$	¿Se puede ejecutar esta acción ahora?	No editar producción sin evidencia; no consultar datos personales sin permiso.
Ranking $F(a \mid s_t)$	Entre las acciones permitidas, ¿cuál conviene primero?	Leer consola cuesta poco y reduce incertidumbre: buena primera acción.
Parada	¿Cuándo dejo de buscar?	Responder si hay evidencia suficiente; pedir aprobación si la acción siguiente es destructiva.
Trazabilidad	¿Qué debería quedar registrado?	Estado inicial, acciones candidatas, puntuación, bloqueos, observaciones y decisión.

Esta separación evita dos errores frecuentes. El primero es usar una puntuación blanda para permitir acciones que deberían estar prohibidas. Si una acción requiere aprobación, no debería “ganar” por tener buen score: debería quedar bloqueada hasta tener autorización. El segundo es esconder las razones de la política dentro de un prompt. Puedes usar un LLM como parte del sistema, pero el contrato operativo —presupuestos, permisos, formato, evidencias mínimas y criterios de parada— debe existir fuera del texto improvisado.

En agentes con herramientas, esta trazabilidad también sirve para depurar. Si el agente gastó diez llamadas antes de leer el error principal, el problema no era “el modelo”: era la política. Si editó código antes de mirar una prueba mínima, el problema no era “la IA”: era que no había una precondición de evidencia.

En el día a día

Imagina un agente de código que recibe: “la página falla al cargar”. Puede hacer muchas cosas. Leer el error de consola. Abrir el navegador. Buscar en el repositorio. Ejecutar tests. Mirar el último commit. Preguntar al usuario. Todas son acciones válidas, pero no todas son igual de buenas.

Una política Greedy elegiría lo que parece más directo: “abrir el navegador”. Puede funcionar. Pero si no mira los logs, quizá pierda diez minutos en la pantalla equivocada. Una política tipo A* ponderaría el coste y la información esperada: “leer el error de consola cuesta poco y reduce mucho la incertidumbre; hagamos eso primero”.

En producción, esta diferencia se traduce en dinero y fiabilidad. Un agente que llama a diez herramientas para resolver una pregunta sencilla no solo es más lento: también introduce más puntos de fallo. Un agente que responde demasiado pronto parece rápido, pero puede inventar. El buen diseño está en equilibrar información, coste y riesgo.⁵

Por qué debería importarte

La búsqueda clásica te da un vocabulario para diseñar agentes modernos sin confundir una salida fluida con una decisión controlada. Si defines mal el estado, el agente se pierde. Si defines mal las acciones, no puede llegar a la solución. Si ignoras el coste, se vuelve caro. Si ignoras el riesgo, se vuelve peligroso. Si la heurística es mala, parece inteligente mientras da vueltas.

Esto es especialmente importante porque los LLMs son convincentes. Pueden explicar una decisión con mucha seguridad aunque la decisión sea mala. La estructura de búsqueda te obliga a preguntar: ¿qué estado tenía?, ¿qué acciones consideró?, ¿qué coste pagó?, ¿qué evidencia observó?, ¿por qué eligió esa acción y no otra?

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Llamar “agente” a cualquier prompt con herramientas	Tener tools no basta. Un agente necesita estado, acciones, criterio de decisión y actualización tras observar resultados.	Dibuja $s_t$, $A(s_t)$, $a_t$ y $s_{t+1}$. Si no puedes, todavía no hay diseño de agente.
Hacer tool selection puramente Greedy	La herramienta obvia puede ser cara, arriesgada o prematura.	Añade coste $G$ y riesgo $R$ al criterio de decisión.
No modelar el coste en tokens y latencia	Un agente puede ser correcto y aun así inviable si tarda demasiado o cuesta demasiado.	Define presupuesto antes de ejecutar: tokens máximos, llamadas máximas y tiempo máximo.
Confundir observación con verdad	Una tool puede devolver datos incompletos, antiguos o mal interpretados.	Guarda la fuente de cada observación y verifica las decisiones importantes.
Recapitular sin comprobar	Leer “ya lo entiendo” no equivale a poder reconstruirlo.	Usa las preguntas de revisión activa; si fallas una, vuelve al capítulo concreto.

Manos a la obra

La práctica real está en kit descargable. El kit simula un agente de ingeniería que recibe una incidencia: la página de checkout falla. Tiene varias acciones candidatas, pero no todas son elegibles. Algunas son baratas y aportan evidencia; otras son caras; otras requieren aprobación porque tocan datos o podrían modificar código sin pruebas.

# Descomprime el ZIP del capítulo y ejecuta estos comandos dentro de esa carpeta
python3 ops/rank_agent_actions.py --write
cat output/agent_action_decision.md

Como gate:

python3 ops/rank_agent_actions.py --write --fail-on-invalid

Qué deberías ver. El sistema separa acciones bloqueadas de acciones elegibles. Después ordena las elegibles con $F=G+H+R$. La mejor primera acción no es “editar rápido”, sino recoger evidencia barata: leer la consola del navegador. Eso enseña una regla práctica: un agente útil no solo elige lo que parece acercarle a la solución; también respeta precondiciones.

Archivo	Papel
data/agent_case.json	Incidencia, estado inicial y acciones candidatas.
contracts/action_policy.json	Pesos de coste, incertidumbre y riesgo; presupuestos y bloqueos duros.
ops/rank_agent_actions.py	Motor de ranking y auditoría sin dependencias externas.
output/agent_action_report.json	Resultado estructurado para revisión automática.
output/agent_action_decision.md	Decisión legible: acción recomendada, ranking y bloqueos.

Cómo lo adaptas a tu caso. Cambia las acciones candidatas por herramientas reales de tu proyecto: leer logs, ejecutar tests, consultar documentación interna, pedir aprobación, abrir un ticket o llamar a una API. Después ajusta pesos y bloqueos. Si una acción peligrosa gana el ranking, el contrato está mal: no deberías arreglarlo con un prompt, sino con una regla de elegibilidad.

Qué entregaría un alumno. El Markdown generado, una acción nueva añadida al caso, una justificación de sus valores $G$, $H$ y $R$, y una decisión escrita sobre qué acción ejecutaría primero y cuál quedaría bloqueada.

Recapitulación activa del bloque de búsqueda

Este cierre funciona como el capítulo 12 del facsímil 1: no es un resumen para leer rápido, sino una revisión activa. Si una sección no te sale, vuelve al capítulo indicado.

1. Búsqueda como espacio de estados

El concepto. Un problema de búsqueda se define con estado inicial, acciones, función de transición, prueba de meta y coste. Si una de esas piezas está borrosa, el algoritmo no tiene dónde agarrarse.⁶

Para recordar. El estado no es “todo lo que existe”: es solo la información necesaria para decidir la siguiente acción. Meter información irrelevante infla el espacio de búsqueda.

Ejemplo fresco. En un laberinto, el estado puede ser la coordenada $(x,y)$. No necesitas guardar el color de la pared ni la hora del día. En un agente de código, el estado puede incluir error, archivos leídos y tests ejecutados; no necesita recordar cada token de una conversación si ya tiene un resumen fiable.

Vuelve al capítulo 1 si: no puedes definir estado, acción, meta y coste para un problema cotidiano.

2. BFS, DFS, UCS e IDS

El concepto. La frontera determina el algoritmo. Cola FIFO produce BFS. Pila LIFO produce DFS. Cola de prioridad por $g(n)$ produce UCS. DFS con límites crecientes produce IDS.⁷

Para recordar. BFS es completo y óptimo con costes uniformes, pero consume memoria $O(b^d)$. DFS consume mucha menos memoria, $O(b \cdot m)$, pero no garantiza optimalidad. UCS generaliza BFS cuando las acciones cuestan distinto.

Ejemplo fresco. Si todas las calles pesan igual, BFS encuentra el camino con menos cruces. Si unas calles son autopistas y otras caminos lentos, necesitas UCS. Si el espacio es enorme y solo quieres no quedarte sin memoria, IDS es el puente.

Vuelve al capítulo 2 si: no puedes explicar por qué cambiar cola por pila cambia completamente el comportamiento.

3. Greedy, A* y heurísticas

El concepto. Greedy usa $f(n)=h(n)$. A* usa $f(n)=g(n)+h(n)$. La heurística $h(n)$ es una estimación de lo que falta, y su calidad decide cuántos estados se exploran.⁸

Para recordar. Greedy es rápido porque ignora el coste acumulado. A* es más disciplinado porque suma lo que ya pagaste y lo que estimas que falta. Con $h$ admisible, A* conserva garantías de optimalidad.⁹

Ejemplo fresco. En una rejilla, Manhattan puede decirte cuántos pasos mínimos faltan si solo te mueves en horizontal y vertical. Esa estimación no resuelve el problema, pero evita explorar media ciudad.

Vuelve al capítulo 3 si: no puedes explicar admisibilidad, consistencia y dominancia de heurísticas.

4. Agentes modernos

El concepto. Un agente moderno selecciona acciones en un estado parcialmente observado, ejecuta herramientas, recibe observaciones y actualiza su estado. La búsqueda puede ser implícita, pero sigue estando ahí.

Para recordar. “LLM + tools” no es automáticamente un buen agente. Hace falta una política: cuándo usar herramientas, cuáles priorizar, cuándo parar, cuándo pedir aclaración y cuándo responder.

Ejemplo fresco. Ante un fallo de build, un agente prudente no edita a ciegas. Primero lee el error, identifica el archivo probable, ejecuta el test mínimo, modifica, y vuelve a verificar. Eso es búsqueda guiada por evidencia.

Vuelve a este capítulo si: no puedes mapear un agente a $s_t$, $A(s_t)$, $a_t$, observación y $s_{t+1}$.

Cómo encaja todo

Este mapa cierra el primer bloque del facsímil. Los capítulos 1, 2 y 3 nos dieron el lenguaje clásico: estado, frontera, coste real y heurística. Aquí usamos ese lenguaje para leer un agente moderno sin caer en la fantasía de que todo ocurre dentro del modelo.

La decisión nueva es separar propuesta, elegibilidad, puntuación, ejecución y observación. Esa separación volverá en restricciones, planificación, agentes de software y operación.

graph TD
    subgraph "Capítulos 1-3: búsqueda explícita"
        C01["Cap. 1: estado, acción, meta y coste"]
        C02["Cap. 2: frontera FIFO, LIFO y g(n)"]
        C03["Cap. 3: h(n), admisibilidad y A*"]
    end
    subgraph "Capítulo 4: agente como búsqueda implícita"
        STATE["Estado s_t: memoria, observaciones, restricciones y objetivo"]
        CANDIDATES["A(s_t): acciones candidatas"]
        ELIGIBILITY["E(a|s_t): permisos, presupuesto y precondiciones"]
        SCORE["F(a|s_t)=G+H+R"]
        TOOL["Tool ejecutada"]
        OBS["Observación nueva"]
        STOP["Criterio de parada o siguiente iteración"]
    end
    subgraph "Lo que viene después"
        CSP["Cap. 5-8: restricciones y guardrails"]
        PLAN["Cap. 9-10: planificación"]
        GAMES["Cap. 11: otros actores eligen"]
        SYMBOLIC["Cap. 12: conocimiento simbólico"]
        AGENTS["Fasc. 5: agentes de software"]
    end

    C01 --> STATE
    C02 --> CANDIDATES
    C03 --> SCORE
    STATE --> CANDIDATES
    CANDIDATES --> ELIGIBILITY
    ELIGIBILITY --> SCORE
    SCORE --> TOOL
    TOOL --> OBS
    OBS --> STATE
    OBS --> STOP
    ELIGIBILITY --> CSP
    STOP --> PLAN
    SCORE --> GAMES
    OBS --> SYMBOLIC
    TOOL --> AGENTS

    style STATE fill:#F5F5F5,stroke:#000000,stroke-width:2
    style ELIGIBILITY fill:#F5F5F5,stroke:#000000,stroke-width:2
    style SCORE fill:#F5F5F5,stroke:#000000,stroke-width:2
    style CSP stroke-dasharray: 5 5
    style PLAN stroke-dasharray: 5 5
    style GAMES stroke-dasharray: 5 5
    style SYMBOLIC stroke-dasharray: 5 5
    style AGENTS stroke-dasharray: 5 5

Vocabulario aprendido

Término	Definición
Agente de búsqueda	Sistema que elige acciones para avanzar desde un estado hacia una meta.
Estado de agente	Representación compacta de lo que el agente sabe y de las restricciones activas.
Tool selection	Elección de la siguiente herramienta o acción que conviene ejecutar.
Coste operacional	Tokens, latencia, dinero, riesgo y complejidad acumulados al actuar.
Heurística aprendida	Estimación producida por un modelo o regla para priorizar acciones.
Política de decisión	Regla que transforma estado y acciones disponibles en una acción concreta.
Criterio de parada	Condición que decide si el agente responde, pide aprobación, sigue buscando o escala.
Trazabilidad de decisión	Registro de estado, acciones candidatas, bloqueos, puntuaciones y observaciones.

Antes de pasar página

• ¿Puedo explicar cómo un agente con tools se modela como búsqueda?
• ¿Puedo escribir qué representa $s_t = (m_t, o_t, r_t, q)$?
• ¿Sé diferenciar una política Greedy de una política que incluye coste y riesgo?
• ¿Puedo separar acciones bloqueadas de acciones elegibles antes de rankear?
• ¿Puedo recapitular BFS, DFS, UCS, Greedy y A* sin mirar?
• ¿Entiendo por qué el siguiente bloque, CSP, sigue siendo búsqueda pero con restricciones?

En resumen

Idea fuerza	Detalle
Los agentes modernos no eliminan la búsqueda: la esconden.	Cada decisión de tool es una elección entre acciones candidatas.
El estado decide lo que el agente puede razonar.	Si el estado omite información relevante, la política tomará malas decisiones.
$G + H + R$ es una brújula útil.	Coste, heurística y riesgo permiten diseñar agentes menos impulsivos que un Greedy puro.
La elegibilidad va antes que el ranking.	Una acción prohibida o sin permisos no debería ganar por tener buen score.
El bloque de búsqueda ya está cerrado.	Estados, frontera, coste, heurística y política quedan listos para CSP, planificación y juegos.

Para saber más

Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson.

Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rich, E., Knight, K. y Nair, S. B. (2009). Artificial intelligence (3.ª ed.). McGraw-Hill.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. https://aima.cs.berkeley.edu/

Notas

1. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. El capítulo 2 define los agentes racionales como sistemas que seleccionan acciones para maximizar una medida de rendimiento, una idea que conecta directamente con la búsqueda como selección de acciones. ↩

2. Nilsson, N. J. (1998). Artificial intelligence: a new synthesis. Morgan Kaufmann. Nilsson conecta búsqueda, planificación y agentes como variantes de un mismo problema de decisión secuencial. ↩

3. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. Su marco de búsqueda como transición entre estados permite modelar tanto algoritmos clásicos como agentes que intercalan percepción, acción y actualización de creencias. ↩

4. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. A* formalizó la combinación de coste acumulado y estimación restante; esa idea sigue siendo una plantilla útil para razonar sobre agentes con herramientas. ↩

5. Luger, G. F. (2008). Artificial intelligence: structures and strategies for complex problem solving (6.ª ed.). Pearson. El capítulo 3 insiste en que la eficiencia de una búsqueda depende tanto de la representación del problema como de la estrategia de control. ↩

6. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. ↩

7. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩

8. Pearl, J. (1984). Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley. ↩

9. Hart, P. E., Nilsson, N. J. y Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136. ↩

Capítulo 05: SAT y CSP: la IA como restricciones

Entrando en el tema

Imagina que tienes que organizar una semana de reuniones. Hay salas, franjas horarias, personas que no pueden coincidir, permisos, duraciones distintas y una regla sencilla: la agenda final no puede tener solapes. Un modelo generativo puede proponer una agenda bonita. Pero bonita no significa válida.

Aquí aparece una idea muy antigua y muy viva de la inteligencia artificial: no todo consiste en generar una respuesta; a veces consiste en encontrar una asignación que cumpla reglas exactas.¹ Si una sala no puede estar en dos reuniones a la vez, esa regla no es una sugerencia. Es una restricción.

SAT y CSP son dos formas clásicas de expresar ese tipo de problema. SAT trabaja con variables booleanas: verdadero o falso. CSP trabaja con variables que pueden tomar valores de dominios más ricos: horas, salas, personas, rutas, configuraciones. En ambos casos, la pregunta central es la misma: ¿existe una solución que cumpla todas las reglas?

No estamos buscando texto plausible

El malentendido habitual es pensar que SAT y CSP son algoritmos viejos para problemas académicos. En realidad, son una forma de disciplina. Te obligan a separar tres cosas que conviene no mezclar:

Capa	Qué hace	Ejemplo
Interpretar	Entender una petición ambigua.	“Busca una agenda para el equipo esta semana”.
Proponer	Construir candidatos posibles.	Tres horarios alternativos.
Verificar	Aceptar solo lo que cumple reglas.	Sin solapes, sala disponible, permisos correctos.

Un LLM puede ayudar en las dos primeras capas. Puede leer lenguaje natural, resumir preferencias y proponer candidatos. Pero la tercera capa debería ser verificable: un solver, un validador, un esquema JSON, una política de permisos, una regla de negocio o una combinación de todo eso.

La lección del capítulo es esta: cuando hay reglas duras, la aceptación no debe depender de si la respuesta suena convincente.

Antes de entrar en la notación, quédate con dos imágenes sencillas:

Problema cotidiano	Cómo lo ve SAT o CSP	Pregunta que responde
Activar o no activar opciones de una campaña.	SAT lo ve como interruptores: email sí/no, banner sí/no, aprobación legal sí/no.	¿Hay alguna combinación de interruptores compatible con todas las reglas?
Colocar reuniones en una agenda.	CSP lo ve como huecos que hay que rellenar: reunión 1 a las 9:00 o 10:00, reunión 2 a las 9:00 o 10:00.	¿Qué valor pongo en cada hueco para que no haya conflictos?
Aceptar una acción de un agente.	Un validador lo ve como una puerta: pasa si cumple permisos, formato, coste y estado.	¿Esta acción se puede ejecutar o debe rechazarse?

La matemática que viene ahora formaliza esa idea. SAT habla de interruptores. CSP habla de huecos con valores posibles. Los validadores hablan de puertas que se abren o se cierran.

SAT: verdadero, falso y contradicción

SAT, abreviatura de satisfacibilidad booleana, pregunta si existe una asignación de valores verdadero/falso que hace verdadera una fórmula lógica. Cook demostró en 1971 que SAT es NP-completo, convirtiéndolo en una piedra angular de la teoría de la complejidad.² Hoy SAT sigue siendo práctico porque los solvers modernos explotan estructura, propagación y aprendizaje de cláusulas.³

Piensa en una campaña muy simple. El equipo quiere publicar una oferta, pero hay reglas:

Variable	Significado cotidiano	Valor posible
$A$	Enviar la oferta por email.	Sí o no.
$B$	Mostrar la oferta como banner en la app.	Sí o no.
$C$	Tener el texto aprobado por legal.	Sí o no.

Las reglas son igual de simples:

1. La oferta debe salir por al menos un canal: email o banner.
2. Si sale por email, el texto debe estar aprobado.
3. Si sale por banner, el texto debe estar aprobado.

SAT convierte esas frases en lógica booleana. No está escribiendo la campaña. Solo comprueba si existe una combinación que respete las reglas.

La forma canónica se llama CNF: una conjunción de cláusulas. Cada cláusula es una disyunción de literales.

$$\varphi = \bigwedge_{j=1}^{m} C_j, \qquad C_j = \bigvee_{\ell \in L_j} \ell, \qquad \ell \in \{x_i, \neg x_i\}$$

Símbolo	Significado	Ejemplo
$\varphi$	Fórmula booleana completa que queremos satisfacer.	$(A \lor B) \land (\neg A \lor C)$.
$C_j$	Cláusula número $j$. Debe ser verdadera.	$C_1 = (A \lor B)$.
$m$	Número total de cláusulas.	$m = 3$.
$L_j$	Conjunto de literales dentro de la cláusula $j$.	$L_1 = \{A, B\}$.
$\ell$	Literal: variable afirmada o negada.	$A$ o $\neg A$.
$x_i$	Variable booleana.	$A=\text{verdadero}$: se envía email.

Una asignación es una función que da valor a cada variable:

$$\alpha : X \rightarrow \{0,1\}$$

Símbolo	Significado	Ejemplo
$\alpha$	Asignación concreta de valores.	$\alpha(A)=1, \alpha(B)=0, \alpha(C)=1$.
$X$	Conjunto de variables booleanas.	$X=\{A,B,C\}$.
$\{0,1\}$	Dominio booleano: falso o verdadero.	$0=\text{falso}, 1=\text{verdadero}$.

La fórmula es satisfacible si existe al menos una asignación que hace verdaderas todas las cláusulas:

$$\exists \alpha \; \forall j \in \{1,\dots,m\}: C_j(\alpha)=1$$

Símbolo	Significado	Ejemplo
$\exists \alpha$	Existe una asignación.	Probar $A=1,B=0,C=1$.
$\forall j$	Para toda cláusula.	$C_1, C_2, C_3$ deben cumplirse.
$C_j(\alpha)$	Valor de la cláusula $j$ bajo la asignación $\alpha$.	$C_2(\alpha)=1$.
$1$	Verdadero.	La cláusula queda satisfecha.

Veámoslo con la campaña anterior. Tomemos:

$$\varphi = (A \lor B) \land (\neg A \lor C) \land (\neg B \lor C)$$

La primera cláusula dice “usa email o banner”. La segunda dice “si usas email, legal debe estar aprobado”. La tercera dice “si usas banner, legal debe estar aprobado”.

Probamos la asignación $\alpha(A)=1$, $\alpha(B)=0$, $\alpha(C)=1$:

Cláusula	Sustitución	Resultado
$A \lor B$	$1 \lor 0$	$1$
$\neg A \lor C$	$0 \lor 1$	$1$
$\neg B \lor C$	$1 \lor 1$	$1$

Leído en castellano: enviamos email, no mostramos banner y legal sí ha aprobado el texto. Todas las cláusulas valen $1$. Por tanto, la fórmula es SAT y $\alpha$ es un modelo. Si ninguna asignación de las $2^3=8$ posibles funcionara, la fórmula sería UNSAT.

Cómo se pasa de frase a cláusula

La parte que más se suele subestimar no es ejecutar un solver, sino codificar bien el problema. Un solver SAT no entiende “legal debe aprobar si hay campaña”. Entiende literales y cláusulas. El trabajo de ingeniería está en traducir sin perder significado.

Frase de negocio	Lógica	CNF
“Debe haber email o banner.”	$A \lor B$	$A \lor B$
“Si hay email, legal aprueba.”	$A \rightarrow C$	$\neg A \lor C$
“Si hay banner, legal aprueba.”	$B \rightarrow C$	$\neg B \lor C$
“No pueden estar email y banner a la vez.”	$\neg(A \land B)$	$\neg A \lor \neg B$

La equivalencia más útil es esta:

$$p \rightarrow q \equiv \neg p \lor q$$

Símbolo	Lectura	Por qué importa
$p \rightarrow q$	Si $p$, entonces $q$.	Muchas reglas de negocio tienen esta forma.
$\neg p \lor q$	O no ocurre $p$, o sí ocurre $q$.	Es la forma que un solver SAT puede consumir en CNF.

Otra familia de reglas aparece continuamente: exactamente uno. Por ejemplo, “elige exactamente un plan”. Se suele partir en dos piezas:

$$\text{al menos uno: } x_1 \lor x_2 \lor \dots \lor x_n$$ $$\text{a lo sumo uno: } \bigwedge_{i<j}(\neg x_i \lor \neg x_j)$$

Esto enseña una lección práctica: a veces una frase sencilla genera muchas cláusulas. Si tienes 100 opciones y codificas “a lo sumo una” por pares, salen $100 \cdot 99 / 2 = 4950$ cláusulas. No es malo por sí mismo, pero conviene saber qué estás creando.

CSP: variables, dominios y restricciones

Un CSP, problema de satisfacción de restricciones, generaliza la idea. Ya no trabajamos solo con verdadero/falso. Una variable puede ser una sala, una hora, una persona, una ruta, un plan o una configuración. Los primeros trabajos sobre redes de restricciones formalizaron esta forma de representar problemas combinatorios como relaciones entre variables.⁴ Mackworth popularizó la consistencia de redes de relaciones como herramienta para reducir búsqueda antes de probar soluciones completas.⁵

CSP es parecido, pero ya no todo cabe en interruptores. Piensa en una agenda: una reunión no es “verdadera” o “falsa”; hay que ponerla a una hora. Una sala no es “verdadera” o “falsa”; hay que elegir cuál. Por eso CSP habla de variables con dominios.

Variable	Pregunta cotidiana	Dominio posible
$R_1$	¿A qué hora va la reunión de producto?	9:00 o 10:00.
$R_2$	¿A qué hora va la reunión con cliente?	9:00 o 10:00.
$R_3$	¿A qué hora va la revisión técnica?	9:00 o 10:00.

Formalmente, un CSP se puede escribir así:

$$\mathcal{P} = (X, D, C)$$

Símbolo	Significado	Ejemplo
$\mathcal{P}$	Problema completo de satisfacción de restricciones.	Agenda semanal del equipo.
$X$	Conjunto de variables que hay que asignar.	$X=\{R_1,R_2,R_3\}$, tres reuniones.
$D$	Dominios permitidos para esas variables.	Cada reunión puede ir a las 9:00 o 10:00.
$C$	Conjunto de restricciones que deben cumplirse.	Sin solapes para la misma persona.

Cada variable $X_i$ tiene su dominio:

$$X = \{X_1,\dots,X_n\}, \qquad X_i \in D_i$$

Símbolo	Significado	Ejemplo
$X_i$	Variable individual.	$R_1$: reunión de producto.
$n$	Número de variables.	$n=3$.
$D_i$	Dominio de valores posibles para $X_i$.	$D_1=\{9,10\}$.
$X_i \in D_i$	La variable debe tomar un valor permitido.	$R_1=9$.

Una restricción es una relación sobre una o varias variables:

$$C_k = (S_k, R_k)$$

Símbolo	Significado	Ejemplo
$C_k$	Restricción número $k$.	“Ana no puede estar en dos reuniones a la vez”.
$S_k$	Alcance de la restricción: variables afectadas.	$S_k=(R_1,R_2)$.
$R_k$	Relación permitida entre los valores de esas variables.	$R_1 \neq R_2$.

Una asignación $a$ es solución si asigna un valor permitido a cada variable y todas las restricciones se cumplen:

$$\forall X_i \in X:\; a(X_i) \in D_i \qquad \text{y} \qquad \forall C_k \in C:\; C_k(a)=\text{verdadero}$$

Símbolo	Significado	Ejemplo
$a$	Asignación de valores a variables.	$a(R_1)=9, a(R_2)=10, a(R_3)=9$.
$a(X_i)$	Valor elegido para la variable $X_i$.	$a(R_2)=10$.
$C_k(a)$	Evaluación de la restricción bajo la asignación $a$.	$R_1 \neq R_2$ es verdadero.
$\text{verdadero}$	La restricción queda satisfecha.	No hay conflicto.

Ejemplo mínimo:

Variable	Dominio	Significado
$R_1$	$\{9,10\}$	Reunión de producto.
$R_2$	$\{9,10\}$	Reunión con cliente.
$R_3$	$\{9,10\}$	Revisión técnica.

Restricciones:

1. $R_1 \neq R_2$, porque Ana participa en ambas.
2. $R_2 = 10$, porque el cliente solo puede a las 10:00.
3. $R_3 \neq R_2$, porque comparten sala.

Sin restricciones hay $2^3=8$ asignaciones. Con restricciones, una solución válida es:

$$a(R_1)=9,\qquad a(R_2)=10,\qquad a(R_3)=9$$

Comprueba:

Restricción	Sustitución	Resultado
$R_1 \neq R_2$	$9 \neq 10$	Verdadero
$R_2 = 10$	$10 = 10$	Verdadero
$R_3 \neq R_2$	$9 \neq 10$	Verdadero

Esta asignación no es “plausible”. Es válida. Esa diferencia es el corazón del capítulo.

Modelar CSP como ingeniería, no como decoración matemática

Un CSP bien modelado empieza con decisiones de representación. Si eliges mal las variables, el problema explota. Si eliges dominios demasiado grandes, el solver prueba demasiado. Si escondes restricciones globales como muchas restricciones pequeñas sin necesidad, pierdes estructura.

Decisión de modelado	Pregunta de ingeniería	Consecuencia
Variables	¿Qué estoy asignando realmente?	Reunión-franja, persona-turno, tarea-máquina.
Dominio	¿Qué valores son posibles antes de buscar?	Cuanto más limpio el dominio, menos combinatoria.
Restricciones duras	¿Qué no puede violarse nunca?	Filtran candidatos inválidos.
Restricciones blandas	¿Qué preferimos si se puede?	Definen coste entre soluciones válidas.
Granularidad	¿Una variable enorme o varias pequeñas?	Afecta a propagación, explicación y depuración.

En un sistema real conviene registrar también por qué falla una asignación. “No hay solución” puede ser correcto, pero no siempre es suficiente para operar. Si un horario no existe porque Ana, la sala 2 y el cliente tienen ventanas incompatibles, esa explicación permite corregir datos, relajar preferencias o pedir una decisión humana.

De validez a optimización

Hasta ahora solo hemos preguntado si existe una solución válida. Muchas veces queremos algo más: la mejor solución válida según un coste. Eso nos lleva a la optimización con restricciones, que se puede escribir así:

$$a^* = \arg\min_{a \in \mathcal{A}} J(a) \quad \text{sujeto a} \quad \forall C_k \in C:\; C_k(a)=\text{verdadero}$$

Símbolo	Significado	Ejemplo
$a^*$	Mejor asignación válida encontrada.	Agenda con menos cambios respecto a la semana anterior.
$\mathcal{A}$	Conjunto de asignaciones candidatas.	Todas las agendas posibles.
$J(a)$	Función de coste o penalización.	Número de cambios de sala + preferencias incumplidas.
$C_k$	Restricción dura.	Nadie puede estar en dos reuniones a la vez.
$C_k(a)=\text{verdadero}$	La asignación cumple la regla $k$.	El calendario no tiene solapes.

La parte importante es el orden mental: primero validez, después preferencia. Si mezclas reglas duras y preferencias blandas, puedes convertir un problema resoluble en uno imposible.

Ejemplo:

Agenda	Restricciones duras	Coste $J(a)$	Decisión
$a_1$	Cumple todas	5	Válida, pero mejorable
$a_2$	Incumple un solape	1	Rechazada aunque sea barata
$a_3$	Cumple todas	2	Mejor válida

La agenda $a_2$ no gana porque su coste sea menor. Si viola una restricción dura, queda fuera. Entre las válidas, elegimos la de menor coste: $a_3$.

En el día a día

SAT y CSP aparecen cada vez que un sistema debe decir “esto se puede” o “esto no se puede” de forma verificable.

En configuración de producto, un cliente puede activar módulos, planes, complementos y permisos. Algunas combinaciones son incompatibles: si plan_basic=true, quizá soporte_dedicado=false. Eso se parece mucho a SAT.

En planificación de turnos, cada persona tiene disponibilidad, descansos mínimos, habilidades, límites legales y preferencias. Eso se parece mucho a CSP: variables con dominios y restricciones entre ellas. Dechter lo trata precisamente como procesamiento de restricciones: reducir dominios, propagar consecuencias y buscar solo donde todavía puede existir solución.⁶

En sistemas con LLMs, la conexión es todavía más práctica. El modelo puede redactar un plan, pero el sistema debería validar permisos, formato, estados permitidos y acciones peligrosas antes de ejecutar. Ahí SAT y CSP se convierten en arquitectura: no son solo algoritmos, son una forma de separar creatividad y garantía.

Por qué debería importarte

Porque los LLMs son buenos generando candidatos, pero no son garantías. Si pides “haz un horario sin conflictos”, puede devolver algo que parece correcto y contiene un solape escondido. Si pides “crea una configuración compatible”, puede inventar una combinación que viola una regla comercial.

SAT y CSP te enseñan a diseñar sistemas donde la respuesta final no se acepta por estilo, sino por verificación. Esta idea conecta directamente con guardrails, validadores, permisos, planificación, agentes y evaluación. Poole, Mackworth y Goebel presentan esta separación entre representación, inferencia y búsqueda como una de las bases de la IA computacional.⁷

Dónde solía tropezar yo

Error	Por qué es un error	Antídoto
Tratar una preferencia como restricción dura	“Ana prefiere mañana” no es lo mismo que “Ana solo puede mañana”. Si lo endureces todo, el problema puede volverse imposible.	Marca cada regla como dura o blanda antes de modelar. Lo duro filtra; lo blando puntúa.
Pensar que SAT y CSP generan explicaciones	Un solver puede decir SAT, UNSAT o devolver una asignación. La explicación pedagógica es otra capa.	Usa el solver para validez y una capa aparte para explicar por qué una solución cumple o falla.
Validar después de actuar	Si ejecutas una acción y luego descubres que violaba una restricción, ya has convertido un problema lógico en un incidente operativo.	Valida antes de hacer commit: antes de enviar, reservar, desplegar o cobrar.
Modelar variables enormes	Una variable gigante tiene un dominio inmenso y restricciones difíciles de expresar.	Divide el problema en decisiones pequeñas: persona-día, reunión-franja, permiso-acción.

Manos a la obra

La práctica real está en kit descargable. El kit contiene dos problemas: una campaña codificada como SAT y una agenda codificada como CSP con restricciones duras y preferencias blandas. No usa librerías externas; enumera combinaciones para que se vea el mecanismo completo.

# Descomprime el ZIP del capítulo y ejecuta estos comandos dentro de esa carpeta
python3 ops/validate_constraints.py --write
cat output/constraint_decision.md

Como gate:

python3 ops/validate_constraints.py --write --fail-on-invalid

Qué deberías ver. La parte SAT devuelve modelos que satisfacen todas las cláusulas. La parte CSP enumera horarios válidos, rechaza candidatos inválidos con motivo concreto y elige la mejor agenda válida según preferencias blandas.

Archivo	Papel
data/constraint_case.json	Fórmula SAT, CSP de agenda y candidatos a validar.
contracts/constraint_policy.json	Número esperado de modelos, reglas mínimas y coste máximo aceptable.
ops/validate_constraints.py	Enumerador, validador y explicador sin dependencias externas.
output/constraint_report.json	Resultado estructurado para tests o revisión automática.
output/constraint_decision.md	Informe legible para entregar.

Cómo lo adaptas a tu caso. Cambia las variables SAT por flags reales de configuración y cambia el CSP por turnos, salas, rutas o permisos. Después añade un candidato inválido y comprueba que el validador explica qué regla falla.

Qué entregaría un alumno. El Markdown generado, una cláusula SAT nueva, una restricción CSP nueva, un candidato inválido con explicación y una decisión sobre qué reglas deberían ser duras y cuáles blandas.

Cómo encaja todo

Este mapa marca el cambio de fase del facsímil: dejamos de pensar solo en caminos y empezamos a pensar en reglas que una solución debe satisfacer. La búsqueda sigue estando debajo, pero ahora el criterio principal no es “qué nodo miro primero”, sino “qué combinaciones quedan permitidas”.

La decisión aprendida aquí es convertir frases del mundo en restricciones verificables. Esa idea se reutiliza en CSP, guardrails, planificación y sistemas con permisos.

graph TD
    subgraph "Capítulo 5: SAT y CSP"
        RESTR["Reglas duras"]
        SAT["SAT<br/>sí / no"]
        CSP["CSP<br/>huecos con valores"]
        VAL["Validador<br/>acepta o rechaza"]
        OPT["Mejor solución<br/>válida"]
    end
    subgraph "Capítulos anteriores"
        BUSQ["Estados<br/>(cap. 1)"]
        FRON["Frontera<br/>(cap. 2)"]
        HEUR["Heurísticas<br/>(cap. 3)"]
        AGENTES["Agentes<br/>(cap. 4)"]
    end
    subgraph "Capítulos siguientes"
        VARS["Modelar CSP<br/>(cap. 6)"]
        PROP["Propagar<br/>(cap. 7)"]
        GUARD["Guardrails<br/>(cap. 8)"]
        PLAN["Planning SAT<br/>(cap. 10)"]
    end

    BUSQ -->|"formular"| RESTR
    FRON -->|"explorar"| CSP
    HEUR -->|"priorizar"| OPT
    AGENTES -->|"validar"| VAL
    RESTR -->|"booleanas"| SAT
    RESTR -->|"dominios"| CSP
    SAT -->|"modelo / UNSAT"| VAL
    CSP -->|"asignación"| VAL
    CSP -->|"coste"| OPT
    CSP -->|"prepara"| VARS
    VARS -->|"permite"| PROP
    VAL -->|"base de"| GUARD
    SAT -->|"horizonte"| PLAN

    style BUSQ stroke-dasharray: 5 5
    style FRON stroke-dasharray: 5 5
    style HEUR stroke-dasharray: 5 5
    style AGENTES stroke-dasharray: 5 5
    style VARS stroke-dasharray: 5 5
    style PROP stroke-dasharray: 5 5
    style GUARD stroke-dasharray: 5 5
    style PLAN stroke-dasharray: 5 5
    style RESTR fill:#F5F5F5,stroke:#000000,stroke-width:2

Vocabulario aprendido

Término	Definición
SAT	Problema de decidir si una fórmula booleana tiene alguna asignación que la haga verdadera.
UNSAT	Resultado que indica que ninguna asignación cumple todas las cláusulas.
Modelo SAT	Asignación concreta que satisface la fórmula.
CSP	Problema definido por variables, dominios y restricciones.
Dominio	Conjunto de valores permitidos para una variable.
Restricción dura	Regla que no se puede violar. Si se viola, la solución se rechaza.
Restricción blanda	Preferencia que puede incumplirse pagando un coste o penalización.
Validador determinista	Componente que decide validez aplicando reglas comprobables.

Antes de pasar página

• ¿Puedo explicar la diferencia entre SAT y CSP sin usar jerga?
• ¿Sé escribir una fórmula CNF pequeña y probar una asignación?
• ¿Puedo formular un CSP como $\mathcal{P}=(X,D,C)$?
• ¿Distingo una restricción dura de una preferencia blanda?
• ¿He ejecutado kit descargable y puedo explicar por qué un candidato válido no tiene por qué ser el mejor?
• ¿Entiendo por qué un LLM puede proponer, pero no debería ser quien garantice la validez final?

En resumen

Idea fuerza	Detalle
SAT pregunta por verdad booleana.	Busca una asignación de verdadero/falso que satisfaga todas las cláusulas.
CSP amplía la idea a dominios ricos.	Variables, valores permitidos y restricciones describen horarios, permisos, recursos y configuraciones.
Validez y preferencia no son lo mismo.	Primero se descartan soluciones inválidas; después se optimiza entre las válidas.
La IA moderna necesita restricciones clásicas.	Un LLM puede generar candidatos, pero la aceptación debe pasar por reglas verificables.

Para saber más

Biere, A., Heule, M., van Maaren, H. y Walsh, T. (Eds.). (2009). Handbook of satisfiability. IOS Press.

Cook, S. A. (1971). The complexity of theorem-proving procedures. En Proceedings of the Third Annual ACM Symposium on Theory of Computing (pp. 151-158). ACM. https://doi.org/10.1145/800157.805047

Dechter, R. (2003). Constraint processing. Morgan Kaufmann.

Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99-118. https://doi.org/10.1016/0004-3702(77)90007-8

Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7, 95-132. https://doi.org/10.1016/0020-0255(74)90008-5

Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press.

Rossi, F., van Beek, P. y Walsh, T. (Eds.). (2006). Handbook of constraint programming. Elsevier.

Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson.

Notas

1. Russell, S. y Norvig, P. (2021). Artificial intelligence: a modern approach (4.ª ed.). Pearson. Los capítulos sobre búsqueda y satisfacción de restricciones presentan los problemas como asignaciones sometidas a condiciones verificables. ↩

2. Cook, S. A. (1971). The complexity of theorem-proving procedures. En Proceedings of the Third Annual ACM Symposium on Theory of Computing (pp. 151-158). ACM. https://doi.org/10.1145/800157.805047 ↩

3. Biere, A., Heule, M., van Maaren, H. y Walsh, T. (Eds.). (2009). Handbook of satisfiability. IOS Press. ↩

4. Montanari, U. (1974). Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7, 95-132. https://doi.org/10.1016/0020-0255(74)90008-5 ↩

5. Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99-118. https://doi.org/10.1016/0004-3702(77)90007-8 ↩

6. Dechter, R. (2003). Constraint processing. Morgan Kaufmann. ↩

7. Poole, D., Mackworth, A. y Goebel, R. (1998). Computational intelligence: a logical approach. Oxford University Press. ↩